埃氏筛法 O(nloglogn)
将数排成一列,从第一个开始删掉后面的它的倍数,最后留下的数即为素数,因为前面的数都不是它的约数
优化:可以只把质数的倍数删掉就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int cnt,n;
bool used[N];
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
if(!used[i])
{
cnt++;
for(int j=i+i;j<=n;j+=i)
{
used[j]=true;
}
}
}
printf("%d",cnt);
return 0;
}
线性筛法
n只会被最小质因子筛掉
如2 3 6如果用埃氏筛法则6会被筛两次,而线性筛只筛1次,只会用最小的质因子把它筛掉,每个数的最小质因子又是唯一的,所以是O(n)的
可参考收藏题解
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int primes[N],cnt;
bool st[N];
int n;
void get_primes(int n)
{
for(int i=2;i<=n;i++)//筛质数
{
if(!st[i])//如果是质数(质数表示为false)
primes[cnt++]=i;//存放质数
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)break;
}
}
}
int main()
{
scanf("%d",&n);
get_primes(n);
printf("%d",cnt);
return 0;
}