AcWing 868. 筛质数
原题链接
简单
作者:
奈奈生
,
2024-04-11 11:55:13
,
所有人可见
,
阅读 10
算法1
(朴素算法) $O(n^2)$
思想:
1.st[i]表示i没有被质数筛 筛掉,那么说明i是质数,所以要把i保存到质数数组,prime[cnt++]=i(cnt是质数的个数)
2.去遍历每一个数(包括质数和合数),把其倍数全部筛掉(实际上是把当前的i也筛掉了,如果i是合数,则那么筛掉是正确的,但如果i是质数,则不应该被筛掉,不过也不影响结果,因为此时的i已经被放入到质数数组中
#include<iostream>
using namespace std;
const int N=1e7;
int prime[N],cnt;
bool st[N];
int get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=i;j<=n;j=j+i)
st[j]=true;
}
return cnt;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",get_prime(n));
return 0;
}
算法2
(埃氏算法) $O(nloglogn)$
思想:
1.在朴素算法中,我们是遍历所有的数,把其倍数删掉;但我们其实只需要把质素的倍数删掉即可;
2.方法就是把标记倍数的过程放在 是质数 的前提下即可
C++ 代码
#include<iostream>
using namespace std;
const int N=1e7;
int prime[N],cnt;
bool st[N];
int get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
{
prime[cnt++]=i;
for(int j=i;j<=n;j=j+i)
st[j]=true;
}
}
return cnt;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",get_prime(n));
return 0;
}
算法3
(线性筛法) $O(n)$
思想:
1.在埃氏筛选的过程中,我们发现一个合数,会被多个质数筛掉,也就是说发生了很多次没有必要的筛选
2.所以我们想,能不能每个合数只能被筛一次,所以,我们规定用最小的质因数去筛掉这个合数
C++ 代码
#include<iostream>
using namespace std;
const int N=1e7;
int prime[N],cnt;
bool st[N];
int get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
st[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
return cnt;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",get_prime(n));
return 0;
}