第7章 数组-7数组的其他应用——筛法求素数1
需积分: 0 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`函数负责打印出筛选后数组中剩余的非零元素,即素数。
总结来说,筛法求素数利用了数组存储和遍历的特性,通过消除已知素数的倍数来有效地找到所有素数,避免了对每个数进行单独的素性测试,从而提高了效率。这种方法在计算机科学中广泛应用于需要大量处理素数的情况,如加密算法和数论问题。