题目描述:
质数(prime number)又称素数,有无限个,质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
例如小于10的质数有2,3,5,7。
输入描述:
第一行输入一个整数T,表示询问的个数
接下来T行每行输入一个整数n.
1<=T<=1e8,1<=n<=1000000
输出描述:
对于每个询问n输出小于等于n的的质数的个数。
直接上代码
这里有篇博客,可以看下素数筛:
https://blog.csdn.net/qq_43876850/article/details/102518530
#include<iostream> using namespace std; int su[1000000+10]; //存放素数 bool u[1000000+10]; //判定素数 int i,j,k; //控制循环 int ans=0; int t; //测试的次数 int n; //最大范围 int num=1; void prepare() { for(i=2;i<=1000000;i++) u[i]=true; for(i=2;i<=1000000;i++) if(u[i]) { for(j=2;j*i<=1000000;j++) u[i*j]=false; } for(i=2;i<=1000000;i++) if(u[i]) { su[num++]=i; } } int main() { ios::sync_with_stdio(false); cout.tie(0); cin.tie(0); prepare(); cin>>t; while(t--) { ans=0; cin>>n; for(i=1;i<num;i++) if(su[i]<=n) ans++; else break; cout<<ans<<endl; } return 0; }