C 語言素數篩選：101-200 區間素數枚舉與試除法優化

編輯：關於C語言

問題描述

找出 101 到 200 之間所有素數，並輸出總數與列表。核心考點：試除法判斷素性、√n 優化邊界、篩法思想引入。

原代碼：試除法至 n/2（可優化）


#include <stdio.h>

int main() {
    int i, j, flag, count = 0, primes[100];
    for (i = 101; i < 200; i++) {
        flag = 1;
        for (j = 2; j <= i/2; j++) {  // ❌ 優化空間：只需 √i
            if (i % j == 0) { flag = 0; break; }
        }
        if (flag) primes[count++] = i;
    }
    printf("有 %d 個素數:\n", count);
    for (i = 0; i < count; i++) printf("%d\n", primes[i]);
    return 0;
}

核心優化：試除上界從 n/2 降為 √n

定理：若 n 為合數，必有因子 ≤ √n。
證明：若所有因子 > √n，則最小因子乘積 > √n × √n = n，矛盾。


// 優化版
for (j = 2; j * j <= i; j++) {  // 避免 sqrt 浮點轉換
    if (i % j == 0) { flag = 0; break; }
}

進一步優化：跳過偶數、利用 6k±1 規律


bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;      // 2, 3 是素數
    if (n % 2 == 0 || n % 3 == 0) return false;  // 排除 2,3 的倍數

    // 所有素數 (除2,3) 形如 6k±1
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

篩法視角：埃拉托斯特尼篩 (適用於區間批量)

對於固定區間 [101, 200]，區間篩 比逐個試除更快：


void sieve_segment(int L, int R) {
    int n = R - L + 1;
    bool *is_prime = calloc(n, sizeof(bool));
    for (int i = 0; i < n; i++) is_prime[i] = true;

    // 用 √R 以內的素數篩除
    for (int p = 2; p * p <= R; p++) {
        if (!is_prime[p - L]) continue;  // 簡化：實際需預篩小素數
        // 找到區間內第一個 p 的倍數
        int start = (L + p - 1) / p * p;
        for (int j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }

    // 輸出
    for (int i = 0; i < n; i++)
        if (is_prime[i] && (L+i) >= 2) printf("%d ", L+i);
}

101-200 素數列表 (標準答案)

101 103 107 109 113 127 131 137 139 149
151 157 163 167 173 179 181 191 193 197 199
共 21 個素數

複雜度對比

方法	101-200 區間操作數	時間複雜度	適用場景
試除至 n/2	~5,000 次取模	O(N√N) 粗略	教學演示
試除至 √n	~1,500 次	O(N√N)	單個大數判斷
6k±1 優化試除	~500 次	O(N√N/3)	工程通用判斷
區間篩	~300 次標記	O(N log log N)	批量區間素數
米勒-拉賓 (確定性版)	O(k log³ n)	極快	64位大整數

工程化完整版：靈活區間 + 多種算法選擇


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

bool is_prime_6k(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

void find_primes(int L, int R) {
    int *primes = malloc((R-L+1) * sizeof(int));
    int count = 0;
    for (int i = L; i <= R; i++)
        if (is_prime_6k(i)) primes[count++] = i;

    printf("[%d, %d] 共有 %d 個素數:\n", L, R, count);
    for (int i = 0; i < count; i++) {
        printf("%d%c", primes[i], (i+1)%10==0 ? '\n' : ' ');
    }
    printf("\n");
    free(primes);
}

int main() {
    find_primes(101, 200);
    return 0;
}