C語言練習實例36：求100以內所有素數（質數）

本實例打印 100 以內所有素數，每行 5 個。

判斷邏輯

• 對每個數 i (2..100)，計算 k = sqrt(i)。
• 嘗試除以 2..k，若能整除則非素數。
• 若循環結束 j > k，說明無因數，為素數。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>
#include <math.h>

int main() {
    int i, j, k, n = 0;
    for (i = 2; i <= 100; i++) {
        k = (int)sqrt(i);
        for (j = 2; j <= k; j++)
            if (i % j == 0) break;
        if (j > k) {
            printf("%d ", i);
            n++;
            if (n % 5 == 0) printf("\n");
        }
    }
    return 0;
}

運行結果

2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97

優化

可使用埃拉托斯特尼篩法（Sieve of Eratosthenes）時間複雜度 O(n log log n)。