C語言求 1-200 質數：試除法優化與厄拉托斯特尼篩法對比

方法一：優化試除法 (適合小範圍)

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

int is_prime(int n) {
    if (n < 2) return 0;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; i <= sqrt(n); i += 2)  // 只試奇數
        if (n % i == 0) return 0;
    return 1;
}

int main() {
    printf("1-200 質數：\n");
    int count = 0;
    for (int i = 2; i <= 200; i++) {
        if (is_prime(i)) {
            printf("%4d", i);
            if (++count % 10 == 0) putchar('\n');
        }
    }
    printf("\n共 %d 個質數\n", count);  // 46
    return 0;
}

方法二：埃拉托斯特尼篩法 (Sieve of Eratosthenes, O(n log log n))

void sieve(int n) {
    char *is_prime = calloc(n + 1, 1);  // 0=質數, 1=合數
    is_prime[0] = is_prime[1] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = 1;
        }
    }
    for (int i = 2; i <= n; i++)
        if (!is_prime[i]) printf("%d ", i);
    free(is_prime);
}

關鍵優化點

• i * i <= n 替代 i <= sqrt(n) 避免浮點運算。
• 篩法內層從 i*i 開始 (更小的倍數已被標記)。
• char 陣列節省記憶體，calloc 自動歸零。

複雜度對比