NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 25 题

看程序写结果：

#include "math.h"
#include "stdio.h"
int main()
{
	int a1[51] = { 0 };
	int i, j, t, t2, n = 50;
	for ( i = 2; i <= sqrt( n ); i++ )
		if ( a1[i] == 0 )
		{
			t2 = n / i;
			for ( j = 2; j <= t2; j++ )
				a1[i * j] = 1;
		}
	t = 0;
	for ( i = 2; i <= n; i++ )
		if ( a1[i] == 0 )
		{
			printf( "%4d", i ); t++;
			if ( t % 10 == 0 )
				printf( "\n" );
		}
	printf( "\n" );
}

这道题考的是素数筛法。拿到程序先别急着敲，看数组a1的初值全是0，后面遇到0才去标记倍数，这明显是筛法。核心就是理解循环边界i<=sqrt(n)的数学含义，以及为什么1不会被输出。

最容易把1当成素数输出去，或者漏掉2这个唯一的偶素数。还有学生不理解为什么i只循环到sqrt(n)，以为要一直筛到n，结果多算或者少算。另外要注意输出格式，程序里每10个数换行，别把两行拼在一起当一长串数。

这道题考查的是埃拉托色尼筛法（Sieve of Eratosthenes）求素数，同时结合了C语言数组操作和循环边界控制。命题人喜欢用这种经典算法的变体来考学生是否真正理解筛法的原理，而不是死记硬背素数表。他们会在循环条件、数组下标、以及输出格式上挖坑，比如这里i只循环到sqrt(n)，就是考察你对"大于sqrt(n)的合数其最小质因子一定小于sqrt(n)"这个数学事实的掌握。拿到题先想：数组a1初始全0，遇到0说明没被标记过，那就是素数，用它去标记它的倍数。所以程序逻辑是：从2开始，只要a1[i]还是0，就把i的倍数（i*2, i*3...）标记为1。内层循环j从2开始，一直乘到i*j<=n，也就是j<=n/i。外层循环i的条件是i<=sqrt(n)，这是筛法的优化点——超过sqrt(n)的数，如果是合数，它的最小质因子肯定已经小于sqrt(n)，在之前的循环里就被筛掉了，所以不用再处理。接下来一步步推：i=2时，a1[2]=0，进入内层，把4,6,8...50都标成1；i=3时，a1[3]=0，把6,9,12...48标成1（注意6已经被标过了，但标两次没关系）；i=4时，a1[4]=1，跳过；i=5时，a1[5]=0，标10,15,20...50；依此类推，直到i=7（因为7*7=49<=50，7*11=77>50，所以i=7还能进内层循环），i=8时a1[8]=1跳过，i=9跳过，i=10跳过，i=11（11*11=121>50）此时i<=sqrt(50)≈7.07，所以i=11不满足外层循环条件，直接结束筛法。剩下的a1[i]=0的数就是素数：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47。输出部分很简单，每行10个，所以第一行到29，第二行从31开始。避坑方面，千万别把1算进去，因为程序从i=2开始，而且1本身也不是素数；也别漏掉2，它是唯一的偶素数；还有循环边界i<=sqrt(n)一定要记牢，这是筛法效率的关键。从考频看，递推相关题目在题库里共出现过79次，覆盖从2007到2026年的所有级别，其中近年爆发式增长：2023年12题、2024年23题、2025年24题、2026年13题，说明这类算法题越来越受青睐，尤其是GESP六级和七级，分别考了34题和27题，占比很高。趋势上，命题人倾向于用经典算法的优化版本（如筛到sqrt(n)）来考察理解深度，而不是单纯记忆。基于这个数据，预测未来会继续考筛法及其变种，可能还会结合其他数论概念如欧拉函数、最小公倍数等，但核心还是看你是否能准确写出循环边界和标记逻辑。暂无足够依据预测具体年份的题目形式，但可以确定的是，这类题在普及组初赛和GESP六级、七级仍是高频考点，务必熟练掌握。