C语言程序设计：筛法高效求素数

"本章介绍了数组的其他应用，特别是通过筛法来求解素数的C语言编程方法。首先，讲解了如何判断一个整数是否为素数，然后展示了如何用筛法找出100以内的所有素数。" 在编程领域，数组是一种基本的数据结构，用于存储相同类型的数据集合。在C语言中，数组提供了处理一维和二维数据的能力，同时也支持矩阵运算。本章节探讨了数组的其他应用，特别是在寻找素数上的算法实现。 素数是指大于1且只能被1和自身整除的正整数。判断一个整数x是否为素数通常有两种方法：试商法和优化后的试商法。试商法通过遍历2到x-1的所有整数，检查x是否能被整除。优化后的试商法则只检查2到sqrt(x)的整数，因为如果x能被大于sqrt(x)的数a整除，那么一定存在一个小于或等于sqrt(x)的数b，使得x=a*b。基于这个优化，我们可以编写如下的C语言函数`IsPrime`： ```c int IsPrime(int x) { int i, squareRoot; if (x <= 1) return 0; squareRoot = (int)sqrt(x); for (i = 2; i <= squareRoot; i++) { if (x % i == 0) return 0; } return 1; } ``` 这个函数可以判断一个整数是否为素数，但若要找到一定范围内的所有素数，我们可以采用更高效的方法——筛法。筛法的基本思想是从2开始，标记2的所有倍数为非素数，接着标记下一个未被标记的数（即3）的所有倍数为非素数，依此类推，直到遍历到sqrt(N)。这种方法会逐渐筛掉所有非素数，最后未被标记的数就是素数。 下面是一个使用筛法找出100以内所有素数的C语言程序示例： ```c #include<stdio.h> #include<math.h> int IsPrime(int x); int main() { int i; for (i = 1; i <= 100; i++) { if (IsPrime(i)) printf("%d\t", i); } printf("\n"); return 0; } int IsPrime(int x) { int i, squareRoot; if (x <= 1) return 0; squareRoot = (int)sqrt(x); for (i = 2; i <= squareRoot; i++) { if (x % i == 0) return 0; } return 1; } ``` 虽然这个程序可以找到100以内的素数，但是筛法的效率更高，因为它只需要遍历一次数组并消除合数，而不需要对每个数字进行单独的素数测试。通过初始化一个长度为101的数组，我们可以直接在数组中标记合数，最后数组中未被标记的索引对应的数就是素数。 数组在编程中扮演着重要的角色，而通过数组实现的筛法求素数算法，不仅提高了计算效率，也体现了数组在解决特定问题时的独特优势。理解并熟练运用这些算法，对于提升编程技能和解决实际问题都大有裨益。