C語言判斷素數：試除法優化至 √n、跳過偶數

C語言判斷素數：試除法優化至 √n、跳過偶數

判斷整數 n 是否為素數。優化：特判 2、排除偶數、只試除到 √n、步長 2。

優化算法

#include <stdio.h>
#include <math.h>

#define YES 1
#define NO 0

int is_prime(int n) {
    if (n == 2) return YES;
    if (n < 2 || n % 2 == 0) return NO;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return NO;
    }
    return YES;
}

int main() {
    int n;
    printf("輸入數字：");
    scanf("%d", &n);
    if (is_prime(n) == YES)
        printf("%d 是素數\n", n);
    else
        printf("%d 不是素數\n", n);
    return 0;
}

優化點對比

更優預計算版

int is_prime_fast(int n) {
    if (n == 2) return 1;
    if (n < 2 || n % 2 == 0) return 0;
    int limit = (int)sqrt(n);
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

測試用例

2   → 素數
3   → 素數
4   → 非素數
17  → 素數
100 → 非素數
9973 → 素數

大數素性測試提示

• 64 位整數：Miller-Rabin 確定性版本 (基數 {2,3,5,7,11,13})
• 任意大整數：Miller-Rabin 概率測試
• 篩法預計算小素數表加速試除