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

preview
需积分: 0 1 下载量 119 浏览量 更新于2022-08-03 收藏 175KB PDF 举报
【筛法求素数】是计算数学中一种高效找出一定范围内所有素数的方法,尤其适用于在数组中批量处理。在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`函数负责打印出筛选后数组中剩余的非零元素,即素数。 总结来说,筛法求素数利用了数组存储和遍历的特性,通过消除已知素数的倍数来有效地找到所有素数,避免了对每个数进行单独的素性测试,从而提高了效率。这种方法在计算机科学中广泛应用于需要大量处理素数的情况,如加密算法和数论问题。