C語言質數判斷演算法：從暴力法到開方優化完整指南

質數定義與基本判斷邏輯

質數（Prime）指大於 1 的自然數，除 1 與自身外無其他因數。判斷邏輯：對 2 ~ n-1 試除，若皆有餘數則為質數。

階段一：朴素暴力法（教學用）

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

時間複雜度 O(n)，僅適合極小數值測試。

階段二：開方優化（標準寫法）

數學原理：若 n = a × b，則 a ≤ √n 或 b ≤ √n。故只需試除到 √n 即可。

int is_prime_sqrt(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;
}

時間複雜度 O(√n)，實務足夠應付 32 位整數範圍。

階段三：篩法（批量求質數）

若需找出 1 ~ N 所有質數，使用 埃拉托斯特尼篩法，複雜度 O(N log log N)。

void sieve(int N) {
    vector is_prime(N+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= N; i++)
        if (is_prime[i])
            for (int j = i * i; j <= N; j += i)
                is_prime[j] = false;
    // 輸出所有 is_prime[i] == true 的 i
}

常見錯誤避坑

• for (i=2; i<=sqrt(n); i++)：sqrt 每次迴圈重複計算，改用 i*i <= n 或預存 limit = sqrt(n)。
• 忘記處理 n <= 1、n == 2、偶數快速判斷。
• 篩法內層起始點應為 i*i 而非 2*i（較小倍數已被標記）。

應用範例：印出 100~200 間的質數

for (int m = 101; m <= 200; m += 2) { // 只檢查奇數
    int k = (int)sqrt(m);
    int i;
    for (i = 3; i <= k; i += 2)
        if (m % i == 0) break;
    if (i > k) printf("%d ", m);
}