素数筛法略

墨蓝 2022-10-25 01:23 180阅读 0赞

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：  
1 2 3 4 5 6 7 8 9 10  
11 12 13 14 15 16 17 18 19 20  
21 22 23 24 25 26 27 28 29 30  
1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：  
3 5 7 9 11 13 15 17 19 21 23 25 27 29  
剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：  
2 3 5 7 11 13 17 19 23 29

# 埃氏筛法 #

#include <iostream>
    #include <cstring>
    using namespace std;
    bool mark[105];
    int main()
    { 
    
        int sum = 0;
        for (int i = 2; i <= 100; i++)
            mark[i] = 1;
    
        for (int i = 2; i * i <= 100; i++)
        { 
            if (mark[i])
            { 
                for (int j = 2 * i; j <= 100; j += i)
                    mark[j] = 0;
            }
        }
        for (int i = 1; i <= 100; i++)
            if (mark[i] == 1)
                cout << i << " ";
        return 0;
    }

# 欧拉筛法（线性筛，最快最好） #

// 欧拉筛法，线性筛法
    #include <iostream>
    #include <cstring>
    using namespace std;
    bool mark[105];
    int main()
    { 
    
        int sum = 0;
        for (int i = 2; i <= 100; i++)
            mark[i] = 1;
    
        for (int i = 2; i * i <= 100; i++)
        { 
            if (mark[i])
            { 
                for (int j = i * i; j <= 100; j += i)
                    mark[j] = 0;
            }
        }
        for (int i = 1; i <= 100; i++)
            if (mark[i] == 1)
                cout << i << " ";
        return 0;
    }

就差在了i\*i这一个变化，就让欧拉筛法比埃氏筛法快了不知道多少倍