NOIP 普及组初赛 · NOIP 2014 普及组初赛试题 第 26 题

阅读程序写结果：

#include <iostream>
using namespace std;
const int SIZE = 100;
int main()
{
	int	p[SIZE];
	int	n, tot, i, cn;
	tot = 0;
	cin >> n;
	for ( i = 1; i <= n; i++ )
		p[i] = 1;
	for ( i = 2; i <= n; i++ )
	{
		if ( p[i] == 1 )
			tot++;
		cn = i * 2;
		while ( cn <= n )
		{
			p[cn] = 0;
			cn += i;
		}
	}
	cout << tot << endl;
	return(0);
}

输入：30 输出：___

看到'筛倍数'逻辑 → 先想埃氏筛法

易把p[1]误计入或误以为内层筛掉i本身；别当成约瑟夫环模拟。

考点：埃拉托斯特尼筛法（素数筛选）

程序在做什么

初始化p[1..n]全为1，外层从2扫到n，若p[i]仍为1则计数，并把i的所有倍数标记为0。