C語言判斷素數函數實現：試除法優化至平方根

C語言判斷素數函數實現：試除法優化至平方根

素數定義：大於 1 的自然數，除 1 和自身外無其他因數。試除法只需檢查至 √n，因若 n = a×b 且 a ≤ b，則 a ≤ √n。

代碼實現

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

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

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

測試結果

請輸入大於1的正整數：8
8 不是素數

請輸入大於1的正整數：17
17 是素數

進階優化

• 預先篩選 2，後續只檢查奇數（i += 2）。
• 使用 6k±1 優化：除 2、3 外，所有素數均鄰近 6 的倍數。
• 大數（> 32 位）建議使用 Miller-Rabin 概率測試。