Problem1883--筛选质数(课程G)

1883: 筛选质数(课程G)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

完善程序:
筛选法求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;
}

Input

第一行1个正整数:N,范围在[1,1000000]。

Output

一个整数。

Sample Input Copy

100

Sample Output Copy

25

Source/Category