第7章 数组-7数组的其他应用——筛法求素数1

【筛法求素数】是计算数学中一种高效找出一定范围内所有素数的方法，尤其适用于在数组中批量处理。在C语言程序设计中，我们通常使用这种方法来解决如何判断一个整数是否为素数的问题。 素数是大于1且只能被1和它本身整除的正整数。一个简单的判断素数的函数如`IsPrime`所示，它通过检查从2到该数平方根之间的整数是否能整除给定的数来确定。如果找到一个因子，那么这个数不是素数，返回0；如果没有找到因子，那么它是素数，返回1。 ```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; } ``` 接下来，如果我们想要找出一定范围内的所有素数，比如100以内，可以遍历这个范围，对每个数使用`IsPrime`函数进行判断，然后打印出素数。这个过程可以通过一个名为`main`的主函数实现。 ```c int main() { int i; for (i=1; i<=100; i++) { if (IsPrime(i)) printf("%d\t", i); } printf("\n"); return 0; } ``` 然而，筛法求素数提供了更高效的方式，即埃拉托斯特尼筛法（Sieve of Eratosthenes）。这种方法通过创建一个数组`a`来表示每个数是否是素数，初始化时数组的每个元素都表示相应的数值。从2开始，将2的倍数全部标记为非素数，接着处理下一个未标记的数（即3），标记它的倍数为非素数，以此类推，直到处理到平方根以下的所有数。数组中未被标记为0的元素对应的数值就是素数。 ```c void SiftPrime(int a[], int n) { int i, j; for (i=2; i<=n; i++) { a[i] = i; } for (i=2; i<=sqrt(n); i++) { if (a[i] != 0) { for (j=i*i; j<=n; j+=i) { a[j] = 0; } } } } void PrintPrime(int a[], int n) { int i; for (i=2; i<=n; i++) { if (a[i] != 0) { printf("%d\t", a[i]); } } printf("\n"); } ``` 在这个过程中，`SiftPrime`函数先初始化数组，然后遍历数组，筛选掉每个素数的倍数。`PrintPrime`函数负责打印出筛选后数组中剩余的非零元素，即素数。 总结来说，筛法求素数利用了数组存储和遍历的特性，通过消除已知素数的倍数来有效地找到所有素数，避免了对每个数进行单独的素性测试，从而提高了效率。这种方法在计算机科学中广泛应用于需要大量处理素数的情况，如加密算法和数论问题。