题解 P3912 【素数个数】
Nemlit
2017-11-06 13:12:30
# %%% @神云_cloud 大佬
这道题的数据范围很大,到了10^8,所以用一个一个判断素数显然会TLE,所以我们就要考虑其他算法。这个时候我们就会引入一种方便好用的算法:筛。这里介绍两种筛法,都是用筛数来做的,一种八十分(自己乱搞的玄学筛法)和100分(欧拉筛O(n))的算法(其实还有O(nlogn)的筛法,但是和80分的筛法区别不大,有兴趣的同学可以问问度娘)
80分算法:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int m=100000000;
bool a[m];
int n,sum=1;
//当n>=2时,至少有一个素数2
int main()
{
scanf("%d",&n);
if(n<2)
{//特判一下当n<2
cout<<'0';
return 0;
}
for(int j=2;j*2<=n;j++)
//先筛一边偶数,sum初值已经是一,所以不用考虑2
{
a[2*j]=1;
}
for(int i=3;i*i<=n;i+=2)
{//从3开始搜,不考虑2
if(!a[i])
{
for(int j=3;j*i<=n;j+=2)
//乘三即可,因为偶数已经被筛过了
{
a[i*j]=1;
}
}
}
for(int i=3;i<=n;i+=2)
{
//判断是否为素数
if(!a[i])
{
sum++;
}
}
printf("%d",sum);
return 0;
}
```
100分算法:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define m 5800000//10^8的范围大概有5700000多个素数
#define m1 100000000
bool f[m1];//f来判断是否筛过
int n,cnt=0,p[m];//p来存素数个数
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{//欧拉筛素数法模板,可以不重复的筛数
if(!f[i])
{//判断i是否被标记,没被标记则为素数
p[++cnt]=i;
}
for(int j=1;j<=cnt;j++)
{
if(i*p[j]>n)
{//若i*p[j]>n则没有再搜的意义(由于欧拉筛是O(n)的,所以没有重复筛,若i*p[j]>n,则后面一定会有另一个数来筛
break;
}
f[i*p[j]]=1;
if(!(i%p[j]))
//保证每个数都只被它的最小质因子筛掉。若i%p[j]即p[j]是i的一个质因子,因为p数组是单调递增的,所以后面的i*p[j]会有比p[j]更小的质因子。为了优化算法到此时停止即可
//再次 %%% @神云_cloud 大佬
{
break;
}
}
}
printf("%d",cnt);
return 0;
}
```