筛法求素数

由埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明,又称埃拉托斯特尼筛子。

基本思路

不是挑选出所有素数,而是筛掉所有的合数;

#include <iostream>
    #include <cmath>
    using namespace std;  
    int main(){  
        int i, sum = 0, a[100] = {0};
        for (i = 2; i < sqrt(100.0); i++){
            sum = i;
            if (a[sum] == 0)
                while (sum < 100){
                    sum += i;
                    if (sum < 100)
                        a[sum] = 1;
                }
        }
        for (int i = 2; i < 100; i++){
            if (a[i] == 0)
                cout << i << " ";
        }
        cout << endl;
        return 0;
    }

只需要 2 ~ c 的倍数求合数

根据初等数论,若n为合数,则n的最小正因数c
满足:

\[1 < c \leq \sqrt{n}\]