题目描述

筛选法求 1 到 N 之间有多少质数。

输入格式

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

输出格式

一个整数。

样例

100

25

完善程序

#include <bits/stdc++.h>
using namespace std;
int N, ANS;
int a[1000010];
int main()
{
	cin >> N;
	int ct=0;   //记录被删除的个数
	for (int i=2; i*i <= N; i++)
	{
		if (a[i]==0)  // "选"出质数i
		{		   
			for (int j=填空(1); j<=N; 填空(2) )
			{
				if( 填空(3) )   ct++; //这个地方是 i 的倍数
				a[j]=i;  // "筛"掉i的倍数，打上标记
			}
		}
	}
	ans = 填空(4);
	cout <<  ANS << endl;
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}