筛法求素数

算法 Nov 24, 2014

由埃拉托斯特尼(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}\]

Tags

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.