在PRIME中,借助全局数组变量p用素数筛法求10000以内的所有素数,并存入全局数组变量prime中。
时间: 2024-09-25 14:16:56 浏览: 34
经典的素数筛算法学习笔记
在PRIME程序中,我们可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来找到10000以内的所有素数。首先,我们需要创建一个名为`prime`的全局数组,它的长度是10001,因为索引从0开始计数,所以最后一个元素实际上是10000。
以下是使用C语言的一个基本实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_PRIME 10000
bool prime[MAX_PRIME]; // 全局数组,用于存储素数状态
void sieveOfEratosthenes() {
for (int i = 0; i <= MAX_PRIME; i++) {
prime[i] = true; // 初始化所有数为素数假设
}
// 0和1不是素数
prime[0] = false;
prime[1] = false;
// 从2开始,检查每个数是否为素数
for (int p = 2; p * p <= MAX_PRIME; p++) {
// 若prime[p]为真,则p是素数,更新其倍数的素数状态
if (prime[p]) {
for (int i = p * p; i <= MAX_PRIME; i += p)
prime[i] = false;
}
}
}
void printPrimes() {
printf("10000以内的素数有:\n");
for (int i = 2; i < MAX_PRIME; i++) {
if (prime[i])
printf("%d ", i);
}
printf("\n");
}
int main() {
sieveOfEratosthenes(); // 执行埃拉托斯特尼筛法
printPrimes(); // 输出结果
return 0;
}
```
在这个程序中,我们先将数组`prime`的所有元素初始化为`true`,然后从2开始,逐步标记出非素数。最后,`printPrimes`函数遍历数组,打印出所有表示为`true`的位置对应的数字就是素数。
阅读全文