C語言求素數：100-200 範圍內素數篩選實現

編輯：關於C語言

C語言求素數：100-200 範圍內素數篩選實現

打印 100 到 200 之間的所有素數。素數定義：大於 1 的自然數，除 1 和自身外無其他因數。

試除法判斷素數

檢查 2 到 √n 之間是否有因數。優化：先除 2，再檢查奇數。

完整代碼（修正原文語法錯誤）

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

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

int main() {
    printf("100-200 之間的素數：\n");
    int count = 0;
    for (int i = 101; i < 200; i += 2) {  // 只檢查奇數
        if (is_prime(i)) {
            printf("%d ", i);
            count++;
            if (count % 10 == 0) printf("\n");
        }
    }
    printf("\n共 %d 個素數\n", count);
    return 0;
}

運行結果

100-200 之間的素數：
101 103 107 109 113 127 131 137 139 149
151 157 163 167 173 179 181 191 193 197 199
共 21 個素數

優化版：埃拉托斯特尼篩法（範圍較大時）

void sieve_primes(int limit) {
    bool *is_prime = calloc(limit + 1, sizeof(bool));
    for (int i = 2; i <= limit; i++) is_prime[i] = true;
    
    for (int i = 2; i * i <= limit; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    for (int i = 100; i <= 200; i++) {
        if (is_prime[i]) printf("%d ", i);
    }
    free(is_prime);
}