C語言找質數：列印 101~200 間所有質數並統計總數

題目需求

找出 101 到 200 之間所有質數，輸出每個質數並統計總個數。

演算法：試除法 + 旗標法

對每個候選數 i，設 flag=1，嘗試除以 2 ~ i/2，若整除則 flag=0。迴圈結束後 flag==1 即為質數。

完整程式碼（優化版）

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

int main()
{
    int primes[50], count = 0;

    for (int i = 101; i <= 200; i++) {
        int isPrime = 1;
        for (int j = 2; j*j <= i; j++) {  // √i 優化
            if (i % j == 0) { isPrime = 0; break; }
        }
        if (isPrime) primes[count++] = i;
    }

    printf("101~200 共有 %d 個質數：\n", count);
    for (int i = 0; i < count; i++) {
        printf("%d%s", primes[i], (i+1)%10==0 ? "\n" : " ");
    }
    printf("\n");
    return 0;
}

執行結果

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

優化要點總結

• j*j <= i 替代 j <= i/2，速度提升 ~√n 倍
• break 提早跳出，發現因子即停止
• 陣列儲存質數，最後統一格式化輸出（每行 10 個）
• 上界改為 <=200 含邊界

數學補充

質數定理：π(x) ~ x/ln(x)。
π(200) - π(100) ≈ 200/5.3 - 100/4.6 ≈ 37.7 - 21.7 = 16，實際 21 個，近似值尚可。