题目描述
求1,2,\cdots,N1,2,?,N 中素数的个数。
输入输出格式
输入格式：
1 个整数NN。
输出格式：
1 个整数，表示素数的个数。
输入输出样例
说明
• 对于40% 的数据，1 \le N \le 10^61≤N≤106；
• 对于80% 的数据，1 \le N \le 10^71≤N≤107；
• 对于100% 的数据，1 \le N \le 10^81≤N≤108。
思路：RE，线性筛一边就可以做出来。bool只占一个字节，所以不会MLE。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,tot; int prime[1000000]; bool yes[10000000]; void shai(){ memset(yes,true,sizeof(yes)); yes[1]=false; for(int i=2;i<=n;i++){ if(yes[i]) prime[++tot]=i; for(int j=1;i*prime[j]<=n;j++){ yes[i*prime[j]]=false; if(i%prime[j]==0) break; } } } int main(){ scanf("%d",&n); shai(); cout<<tot; }
把上面的代码多开一个0 就可以AC了。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,tot; int prime[1000000]; bool yes[10000000]; void shai(){ memset(yes,true,sizeof(yes)); yes[1]=false; for(int i=2;i<=n;i++){ if(yes[i]) prime[++tot]=i; for(int j=1;i*prime[j]<=n;j++){ yes[i*prime[j]]=false; if(i%prime[j]==0) break; } } } int main(){ scanf("%d",&n); shai(); cout<<tot; }
当然听说大佬用了一种叫Meissel Lehmer Algorithm的算法跑的飕飕的。对于我一个蒟蒻来说，这个算法太高级了，诸君还是自行学习吧。我在这里就不粘代码了。