线性筛素数

· · 个人记录

怎么求素数？

一、普通方法

//定义法：质数只能被１和本身整除，最小质数为２
#include <iostream>
using namespace std;

bool prime(int num){
    int i;
    if(sum<2） return false;
    if(num==2) return true;
    for (i = 2; i < num/2; i++)
        if (num % i == 0)
            return false;
    return true;
}
int main(){  //求1~100以内的素数
    for(int i=1;i<=100;i++)
        if(prime(i)) 
            cout << i << endl;
    return 0;
}
//计数法：质数只有两个因数
#include <iostream>
using namespace std;

bool prime(int num){
    int i;
    int count = 0;
    if(sum<2） return false;
    if(num==2) return true;
    for (i = 1; i <= num; i++)
        if (num % i == 0)
            count++;    // 统计能够整除自己的个数
    if (count == 2)     // 只有1和自己两个数可以整除自己
        return true;
    else
        return false;
}
int main(){  //求1~100以内的素数
    for(int i=1;i<=100;i++)
        if(prime(i)) 
            cout << i << endl;
    return 0;
}

先来看这两个代码，时间复杂度非常高。另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ \sqrt {m} 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ \sqrt {m} 间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

#include <iostream>
using namespace std;

bool prime(int sum){
    if(sum<2） return false;
    if(num==2) return true;
    for(int i=2;i*i<=sum;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}
int main(){  //求1~100以内的素数
    for(int i=1;i<=100;i++)
        if(prime(i)) cout << i << endl;
    return 0;
}

二、埃式筛

这是什么？ 埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于\sqrt {n}的所有素数的倍数剔除，剩下的就是素数。 算法：要得到自然数n以内的全部素数，必须把不大于\sqrt {n}的所有素数的倍数剔除，剩下的就是素数。 即：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......

#include <iostream>
using namespace std;

bool book[20005];
int main(){  //求1~100以内的素数
    book[0]=book[1]=0;//不是必需的，因为后面程序直接从2开始筛
    for(int i=2;i<=100;i++)
        if(!book[i]){
            for(int j=i+i;j<=100;j+=i)//用每一个素数一次去筛每一个数
                book[j]=1;
        }
    for(int i=2;i<=100;i++)
        if(!book[i]) cout << i;
    return 0;
}

三、线性筛（欧拉筛法）

这又是什么？先上代码：

#include <iostream>
using namespace std;

bool book[20005];
int prime[20005],t=0;
int main(){  //求1~100以内的素数
    for (int i = 2;i <= 100; i++) 
    {
        if (!book[i]) 
            prime[++t] = i;
        for (int j = 1; j <=t && i*prime[j] <= 100; j++) 
        {
            book[i*prime[j]] = 1;
            if (i % prime[j] == 0) 
                break;
        }
    }
     for(int i=2;i<=100;i++)
        if(!book[i]) cout << i << endl;
    return 0;
}

细心的同学就会发现，这就是优化的埃氏筛。先来看埃氏筛的问题：会将一个合数重复筛。举个例子，30=2*3*5，那么它就会被2筛一次，被3筛一次，再被5筛一次，就会浪费很多时间。线性筛的目的就是在埃氏筛的基础上做到一个数只筛一次，不重复筛。 代码讲解：

#include <iostream>
using namespace std;

bool book[20005];
int prime[20005],t=0;
int main(){  //求1~100以内的素数
    for (int i = 2;i <= 100; i++) 
    {
        if (!book[i])//book[i]=0表示i是素数 
            prime[++t] = i;//这里的prime是一个栈，用来存放得到的素数
        for (int j = 1; i*prime[j] <= 100; j++) //i*prime[j]的作用是控制筛查的范围，节约时间
        {
            if(j>t)//超过目前素数个数了
                break;
            book[i*prime[j]] = 1;//筛去当前数
            if (i % prime[j] == 0)//i是prime[j]的整数倍时，说明 i * prime[j+1] 是 prime[j] 的整数倍，不需要现在筛出，因为在之后筛除过程中i * prime[j+1] 这个合数一定会被prime[j]筛除，这样节约时间
                break;
        }
    }
    for(int i=1;i<=t;i++)//依次输出，注意不要写成for(int i=2;i<=10;i++)
        cout << prime[t] << endl;
    return 0;
}

四、打表

这个就不用我说了吧。 可以参考我另一篇文章：https://www.cnblogs.com/include-blog/p/12365937.html。

---分割线--- 本文参考文章： https://blog.csdn.net/aiwangtingyun/article/details/79581598 https://blog.csdn.net/qq_39763472/article/details/82428602