题解 P3912 【素数个数】

Nemlit

2017-11-06 13:12:30

Solution

# %%% @神云_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; } ```