《C编程技巧：117个问题解决方案示例 》 —3.2　从数字列表中选择质数

3.2　从数字列表中选择质数

问题

你想从序列号列表中选择质数，例如1到1000。

解决方案

编写一个C程序，使用埃拉托斯特尼的筛法从1到N的整数列表中选择质数，具有以下规格说明：

程序生成从1到N的整数列表。

程序删除列表中的第一个数字1，因为根据定义，1不是质数。然后程序删除列表中2的倍数，但不删除2，因为2是质数。

程序删除列表中3的倍数（3表示2之后的下一个未删除数字），然后是5的倍数（5表示3之后的下一个未删除数字），然后是下一个未删除数（最多为N的平方根）的倍数。

最后，你将获得一个质数列表。

代码

以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序并将其保存在文件夹C:\Code中，文件名为erato.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理

埃拉托斯特尼筛法的工作原理很简单。当你想要计算前N个质数时，此方法特别有用。在这种方法中，简单地从1到N的序列号列表中逐个删除非质数，最后，在1到N的序列号列表中只留下质数。图3-3说明了埃拉托斯特尼筛法的工作原理。

图3-3　使用埃拉托斯特尼筛法从数列中挑选质数

在LOC 5～24中定义的函数sieve()执行筛选数字和选择质数的任务。在LOC 4中定义了一个名为status大小为 SIZE的int类型数组，SIZE定义为1000。此数组中的所有单元格都将填充1或0。这些1和0是状态指示器，0表示质数，1表示非质数。例如，单元格status[17]将填充0，表示17是质数；单元格status[20]将填充1，表示20是非质数，等等。

在LOC 8和9中，借助于for循环，该数组填充0。你忽略此数组中的第一个单元格，即status[0]。根据定义，数1不是质数，因此，在LOC 23中，程序将整数1置于单元格status[1]中。你知道数字2和3是质数，因此不会影响相应单元格的状态，因为这些单元格中已经填充了0。

在LOC 12～14中，程序在for循环的帮助下删除列表中的所有偶数（2除外）。实际上，程序用状态指示符1填充相应的单元格。在LOC 15～22中，程序删除列表中剩余的非质数。实际上，程序用状态指示符1填充相应的单元格。

在LOC 28中调用函数sieve()，并使用所需的状态指示符填充数组status。当LOC 28执行完成时，质数列表已经在机器的存储器中准备好了。LOC 30要求你输入数字N，范围为1～1000。在LOC 34～35中，在屏幕上显示数字1到N范围内的质数。