0
已解决
曹砚青
中级光能
中级光能
3870 好大的质数经验值:0
题目描述 Description
给定一个正整数n(2<=n<=10000000),求1~n间质数的个数。
输入描述 Input Description
一个正整数n
输出描述 Output Description
1~n间质数的个数
样例输入 Sample Input
10
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
1~10之间有2,3,5,7共4个质数
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
bool b[10000010];
int main()
{
//freopen("____.in","r",stdin);//打开输入文件
//freopen("____.out","w",stdout);//打开输出文件
cin>>n;
for(int i=2;i<=n;i++)
{
if(b[i]==0)
{
cnt++;
for(int j=i*1;j<=n;j+=i)
{
b[j]='1';
}
}
}
cout<<cnt;
//fclose(stdin);//关闭输入文件
//fclose(stdout);//关闭输出文件
return 0;
}