朴素算法
优化方法
1.只判断奇数
2.因子是成对出现，并且分布在 sqrt (n) 两侧的 所以只判断到n的根

[素数筛] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int IsPrime(int n)
{
    int i;
    if(n<2||(n!=2&&n%2==0))
        return 0;
    else //n都是奇数
    {
        for(i=3;i*i<=n;i+=2)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}

显然如此优化依旧不够

埃氏筛1.0
便是数组a储存已经筛选过的素数 数组b包含范围内所有数字，用来标记是否被访问过 从2开始循环 对其进行倍增操作
优化方法
1.易知很多倍增其实重复了 浪费了时间空间 优化方法便是只对素数进行倍增
2.倍增从i开始 而不是从2开始 减少一半计算量

[素数筛] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int vis[N];//判断是否被访问过
int prime[N];//存储筛选出来的素数

int s(int n)
{
    int i,j,k;//i是逐个访问 j二轮标记，k标记prime数组的位置
    k=0; //这样定义 每次函数调用时都清空
    memset(vis,0,sizeof(int)*N); //清空访问数组
    vis[0]=vis[1]=1;//此步无所谓 因为从2开始
    for(int i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            prime[k++]=i;//如果没有被访问过 那么就是最小的素数
            for(int j=i;j<=n;j++) vis[i*j]=1; //标记在上界内 这个素数数倍增后的数
        }
    }
    return k;
}

埃氏筛2.0 除了上述优化
1.只判断奇数
2.由于因子是成对出现的，如果左侧范围数字不是因子，则右侧范围中也没有因子，因此可以说明这个数字是素数
即x在[2，sqrt (x) ] 范围内的数倍增时 已经得到了
于是有了最终埃氏筛

[埃氏筛] [c++]
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
int E(int n)
{
    if(n<2) return 0;
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*N);
    vis[0]=vis[1]=1;//0 1都是非素数

    for(i=4;i<=n;i+=2) vis[i]=1;//把偶数全部标记了 都是非素数
    for(i=3;i*i<=n;i+=2)
    {
        if(vis[i]==0)
        {
            for(j=i;i*j<=n;j++) vis[i*j]=1;//这里把j=2改为j=i
        }
    }
    prime[k++]=2; //上面循环 只循环到了sqrt(n) 所以需要从头循环一次
    for(i=3;i<=n;i+=2)
    {
        if(vis[i]==0) prime[k++]=i;
    }
    return k;
}


埃氏筛的最终版本 是只要是素数就进行倍增
欧拉筛 在埃氏筛的基础上 保证了每个合数只被筛选一次

[欧拉筛] [c++]
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
//欧拉筛函数
int E2(int n)
{
    int i,j,k;
    k=0;//保存素数的个数
    memset(vis,0,sizeof(int)*maxn);//初始化数组
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)//i是素数，则存起来
            prime[k++]=i;
        for(j=0;j<k;j++)//进行倍增，用i去乘以i之前(包括i)的素数
        {
            if(i*prime[j]>n)//倍增结果超出范围，退出
                break;

            vis[ i*prime[j] ]=1;//将倍增结果进行标记

            if(i%prime[j]==0)//i是前面某个素数的倍数时，也需要退出
                break;
        }
    }
    return k;
}