筛法求素数

筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

筛法求素数 （ACM基础知识）

当只需要求某个数是不是素数的时候，我们可以直接通过素数的定义来求，即如果可以被除1及素数本身的其他数整除，则这个数不是素数

但是如果要求某个范围内的素数的个数的时候这个方法就不太合适了。虽然我们可以进行预处理，但是这种方法比较慢，一旦范围过大，预处理过程便会超时。

因此，需要使用筛法求素数，这样可以在线性时间内求得范围内每个数是否为素数。

思想：去除要求范围内所有的合数，剩下的就是素数，而任何合数都可以表示为素数的乘积，因此，如果已知一个数为素数，则它的倍数都是合数

普通的线性筛法：

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int MAX = 1000100;   // 求MAX范围内的素数
ll su[MAX],cnt;
bool isprimer[MAX];
void prime()
{
    cnt = 1;
    memset(isprimer,1,sizeof isprimer);   // 初始化认为所有数都为素数
    isprimer[0] = isprimer[1] = 0;   // 0和1不是素数
    for(ll i = 2;i <= MAX;i++)
    {
        if(isprimer[i])   // 保存素数
        {
            su[cnt++] = i;
        }
        for(ll j = i*2;j <= MAX;j += i)   // 素数的倍数都为合数
        {
            isprimer[j] = 0;
        }
    }
}

int main()
{
    prime();
    for(ll i = 1;i < cnt;i++)
        printf("%lld ",su[i]);
    return 0;
}

弊端：虽然这种方法已经极大的减小了判断的时间，但是仍然有一些重复计算。比如判断2的时候将（2*3）6筛了一遍。

在判断3的时候又将6(3*2)筛了一遍。

如果只筛选小于等于i的素数与i的乘积，便可以尽量减少重复的筛选，也不会遗漏掉，大大提高了计算效率。

优化后的线性筛法：

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int MAX = 1000100;   // 求MAX范围内的素数
ll su[MAX],cnt;
bool isprimer[MAX];
void prime()
{
    cnt = 1;
    memset(isprimer,1,sizeof isprimer);   // 初始化认为所有数都为素数
    isprimer[0] = isprimer[1] = 0;   // 0和1不是素数
    for(ll i = 2;i <= MAX;i++)
    {
        if(isprimer[i])   // 保存素数
        {
            su[cnt++] = i;
        }
        for(ll j = 1;j < cnt && su[j]*i <= MAX;++j)   // 素数的倍数都为合数
        {
            isprimer[su[j]*i] = 0;   // 筛掉小于等于i的素数和i的积构成的合数
        }
    }
}

int main()
{
    prime();
    for(ll i = 1;i < cnt;i++)
        printf("%lld ",su[i]);
    return 0;
}