筛质数算法
朴素做法
1.先把所有的数放在一个数表中
2.从前往后把每一个数的所有倍数删掉
3.删完之后,所有剩下的数就是质数
神奇吗?
简单证明一下:在2-(p-1)当中,未把p删掉,说明其中没有可以和p整除的数,也就是说2-(p-1)中不存在p的约数,所以p是质数。
prime数组只是作为一个计数来用,prime[cnt++]=n或者=i都不改变结果。
C++ 代码
//朴素筛法
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int prime[N],cnt;
bool st[N];
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])//如果没有被访问过
{
prime[cnt++]=i;//记录没有被消除的点,多一个,cnt就自增一个
}
for(int j=i+i;j<=n;j+=i) st[j]=true;
}
}
int main()
{
int n;
scanf("%d",&n);
get_prime(n);
cout<<cnt<<endl;
return 0;
}
优化后的筛法
明确我们不需要遍历2-(p-1)的所有数,而只需要筛所有质数的倍数,当一个数不是质数,我们也就不需要筛掉它所有的倍数。
核心代码如下
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])//如果没有被访问过
{
prime[cnt++]=i;//记录没有被消除的点,多一个,cnt就自增一个
for(int j=i+i;j<=n;j+=i) st[j]=true;
}
}
}
线性筛法
核心代码如下
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
st[primr[j]*i]=true;//每一次把当前质数和i的乘积筛掉
if(i%prime[j]==0) break;//这句话发生意味着peime[j]一定是i的最小质因子
}
}