C語言判斷素數函數：優化至 sqrt(n) 試除法

算法優化

若 n 有因子，必有一因子 ≤ √n。只需試除 2 到 √n。

實現代碼

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

int is_prime(int n) {
    if (n <= 1) return 0;
    if (n <= 3) return 1;      // 2,3 是素數
    if (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;
}

int main(void) {
    int n;
    printf("請輸入大於 1 的整數: ");
    scanf("%d", &n);
    printf("%d %s素數\n", n, is_prime(n) ? "是" : "不是");
    return 0;
}

測試用例

進階優化方向

• 預計算小素數表（埃氏篩）加速大量查詢。
• Miller-Rabin 概率檢測適用 64 位大整數。
• 位運算優化模運算（Barrett reduction）。