判断素数的方法（二）

前面那篇文章写了素数的判断方法，现在讲下如何在区间中筛选出全部素数。

方法一

既然已经可以判断素数了，自然可以通过判断素数的方法来依次判断素数，从而进行筛选，请原谅我的表述能力，代码如下

#include<bits/stdc++.h>
using namespace std;
inline int prime(int x)
{
    for (int i = 2; i <= sqrt(x); i++)
        if (x%i == 0)
            return 0;
    return 1;
}

int main()
{
    int left, right;
    cin >> left >> right;
    for (int i = left; i <= right; i++)
        if (prime(i) == 1)
            cout << i << " ";
}

但这个时间复杂度好像有点高，假设从[100,500]这个区间，要执行1878次，执行判断的复杂度是O(sqrt(n)),外循环是O(n)，所以总复杂度是O(n*sqrt(n)),其实效率并不高，让我们想办法优化下...

方法二

这个方法我高中自己莫名其妙来的灵感，哦豁，有点小骄傲，思考下素数的定义：质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数 ,反正百度是这么写的qaq,那么换句话说，只要是除1意外任何数字的倍数就一定不是素数了，比如2，2的倍数是4，6，8，10,等等，那就一定不是素数了，3的倍数6，9，12，一定不是素数了。
这有什么用处呢。感觉一切描述都是苍白的，好吧，其实是我不会描述，直接上代码吧

#include<bits/stdc++.h>
using namespace std;
const int MAXV = 10001;
int XX[MAXV];
void init(int left, int right)
{
    for (int i = 2; i <= right; i++)
    {
        int k = 2;
        while (i*k <= right)
        {
            XX[i*k] = 1;
            k++;
        }
    }
    for (int i = left; i <= right; i++)
        if (!XX[i])
            cout << i << " ";
}
int main()
{
    int myleft, myright;
    cin >> myleft >> myright;
    init(myleft,myright);
}

我们接着假设[100,500]这个区间，看看他到底执行多少次，2192次。
什么2192次，那不是比上面那个还高么，让我们把数据区间放大一点..[100,9999]试下，73647次，而上面那个算法需要117291次，随着数据增大，优势越来越明显，其实我们还可以优化上面那个筛选算法。
试想一下4这个数字，他已经被2筛选了，这就意味这4的倍数也一定是2的倍数，那么后面4的倍数这个循环就不用做了，让我们试试，先付下代码

#include<bits/stdc++.h>
using namespace std;
const int MAXV = 10001;
int XX[MAXV];
int mycount= 1;
void init(int left, int right)
{
    for (int i = 2; i <= right; i++)
    {
        if(XX[i]==1)
            continue;
        int k = 2;
        while (i*k <= right)
        {
            XX[i*k] = 1;
            k++;
        }
    }
    for (int i = left; i <= right; i++)
        if (!XX[i])
            cout << i << " ";
}

int main()
{
    int myleft, myright;
    cin >> myleft >> myright;
    init(myleft,myright);
    cout << endl;
    cout << mycount;

}

代码很简单，在筛素数的前面加个判断就行。让我们测试下运行次数，哇23070次，这真的是一个伟大的改进。速度翻了一番还多。
其实这个算法很早就有了，反正叫啥我布吉岛
先就这样吧~~~~~

判断素数方法（二）

原文：https://www.cnblogs.com/ColdKiller/p/10250497.html