C語言質數判斷：試除法實作與 √N 優化邊界分析

質數定義與試除法

大於 1 的自然數，除 1 與自身外無其他因子。
試除法：對 n，檢查 2 ~ √n 是否有因子。若無則為質數。

原始碼邊界問題

原程式迴圈 for(i=2; i<=num/2; i++)，上限 num/2 雖正確但非最優。
最佳上限為 √num（含），因若 a×b=n 且 a≤b，則 a≤√n。

優化版完整程式碼

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

int isPrime(int n)
{
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;  // 排除偶數
    for (int i = 3; i*i <= n; i += 2)  // 只檢查奇數
        if (n % i == 0) return 0;
    return 1;
}

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

複雜度對比

教學重點

1. i*i <= n 比 i <= sqrt(n) 更快且避免浮點誤差
2. 先處理 2、偶數等特例，主迴圈步進 2
3. 函式化 isPrime() 便於重複呼叫與單元測試

延伸：質數篩

若需找出 N 以內所有質數，用 埃拉托斯特尼篩法 O(N log log N) 遠快於逐一試除。