NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 25 题

看程序写结果

#include "math.h"
#include "stdio.h"
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 代表‘未标记’，后面把倍数改成 1 就是‘标记合数’，所以只要数数最后哪些位置还是 0 就能得到答案。

很多同学容易把输出顺序搞反，以为是从大到小或者乱序，其实循环是从 2 到 n 顺次扫描，保证从小到大输出。还有人会忽略数组下标从 0 开始但逻辑从 2 开始，误以为 a1[1] 也是质数，但程序里 i 从 2 起，所以 1 根本不会被输出。另外，sqrt(50) 约等于 7，只筛到 7 的倍数就够，若有人以为要筛到 n 就会多算很多无用的标记，不过对结果不影响，只是效率问题。

这道题考查的是素数筛法，属于基础算法里的经典内容。命题人喜欢用这种‘看程序写结果’的形式，让你在不运行代码的情况下，通过分析算法流程得出输出，既考理解也考细心。这里用到了埃拉托斯特尼筛法（简称埃氏筛），核心思想非常简单：先假设所有数都是素数，然后从最小的素数 2 开始，把它的所有倍数（除了它自己）都划掉，接着找下一个没被划掉的数，它必然是新的素数，再把它后面的倍数划掉，如此反复，直到处理到 sqrt(n) 为止。最后剩下的没被划掉的数就是素数。

咱们一步步看程序是怎么实现的。首先定义了一个整型数组 a1[51]，全部初始化为 0。在筛法里，0 代表‘未被标记’，也就是当前认为是素数；后面会把合数标记成 1。数组大小开到 51 是为了方便处理 2 到 50 这些数，下标正好对应数值本身。

外层循环从 i = 2 开始，一直跑到 i <= sqrt(n)，这里 n = 50，sqrt(50) 约等于 7.07，所以 i 会取 2,3,4,5,6,7。每次循环先判断 a1[i] == 0，如果为真，说明 i 还没被标记，那它一定是素数。这时候就要把 i 的所有倍数都标记掉。程序里用了一个变量 t2 = n / i，表示 i 的倍数最多到 floor(50 / i)。然后内层循环 j 从 2 开始，一直跑到 j <= t2，每次把 a1[i * j] = 1。注意 j 从 2 开始，所以 i * j 不会等于 i 本身，正好只筛掉 i 的倍数而不把 i 自己划掉。

咱们手动跑几轮看看效果：

• i = 2 时，t2 = 25，j 从 2 到 25，把 a1[4,6,8,...,50] 都改成 1，也就是所有偶数（除了 2）都被标记了。
• i = 3 时，t2 = 16，j 从 2 到 16，把 a1[6,9,12,...,48] 改成 1。注意 6 已经在上一轮被标记了，但这不影响，重复标记也没关系。
• i = 4 时，a1[4] 已经是 1，不进入内层循环，跳过。
• i = 5 时，t2 = 10，j 从 2 到 10，把 a1[10,15,20,...,50] 改成 1。
• i = 6 时，a1[6] 已经是 1，跳过。
• i = 7 时，t2 = 7，j 从 2 到 7，把 a1[14,21,28,35,42,49] 改成 1。

至此，所有合数都被标记成了 1，剩下的 0 就是素数。接下来程序进入第二个循环，从 i = 2 到 n = 50，逐个检查 a1[i] == 0。如果是，就打印 i，并且计数器 t++。每打印 10 个数就换行一次，所以输出会分成两行。

咱们按顺序数一下哪些数的 a1 还是 0： 2, 3, 5, 7, 11, 13, 17, 19, 23, 29（第一行 10 个） 31, 37, 41, 43, 47（第二行 5 个） 正好就是 50 以内的全部素数，共 15 个。

易错点方面，首先要留意数组下标和数值的对应关系，a1[1] 虽然存在，但循环从 2 开始，所以 1 不会被输出。其次，很多人会误以为 sqrt(n) 要取整到 n，其实筛到 sqrt(n) 就足够了，因为大于 sqrt(n) 的合数必然有一个因子不超过 sqrt(n)，早被前面的素数筛掉了。再者，输出格式里每行 10 个数，如果数错了行数可能会把答案写错，但本题只要求填空输出内容，所以只要按顺序列出素数就行。

从历年考频来看，基础算法在 NOIP 和 CSP 的初赛里占有重要地位。题库里基础算法相关题目共 30 道，覆盖 2007 到 2025 年共 19 个年份，每年平均不到 2 道，但分布并不均匀：2007 年考了 2 道，2009 年 4 道，2010 年 4 道，2011 年更是 5 道，之后几年相对少一些，2024 年和 2025 年各考 2 道。分赛事统计，NOIP 提高组初赛出现过 13 次，CSP 提高级 9 次，NOIP 普及组初赛 8 次。这说明素数筛这类经典算法在提高组初赛里出现频率最高，普及组也常考，属于高频考点。

基于这些数据，我可以做一个小预测：未来几年（比如 2026、2027）在初赛里大概率还会继续考基础算法，尤其是筛法、排序、搜索这些内容，因为它们是算法思维的基石，命题人不会轻易放弃。不过具体考哪种筛法（埃氏筛、线性筛）或者结合什么变体（比如求第 k 个素数、统计素数个数等），目前从已有年份的分布看，还不足以做出精准预测，所以暂且认为‘暂无足够依据预测更细的题型’。

总之，这题的关键就是读懂筛法流程，知道标记 0 和 1 的含义，然后按顺序数出未被标记的数。只要抓住这个主线，答案自然水到渠成。