筛选质数(课程G)
题目描述
完善程序：
筛选法求1到N之间有多少质数。
#include <bits/stdc++.h>
using namespace std;
int N, ANS;
int a[1000010];
int main()
{
freopen("1452.in","r",stdin);
freopen("1452.out","w",stdout);
cin >> N;
int ct=0; //记录被删除的个数
for (int i=2; i*i < N+1; i++)
if (a[i]==0) //"选"出质数i
{
for (int j=i+i; j < N+1; _____ )
{
if( ______ ) ct++;
a[j]=i; //"筛"掉i的倍数
}
}
ANS = _______;
cout << ANS << endl;
return 0;
}输入格式
第一行1个正整数：N，范围在[1,1000000]。
输出格式
一个整数。
输入/输出例子1
100
25