C 语言：高效输出质数326

在计算机科学中，质数是一个大于 1 的自然数，它不能被任何其他自然数（除了 1 和它本身）整除。例如，2、3、5、7 和 11 都是质数，因为它们只能被 1 和它们自己整除。理解和生成质数对于密码学、数学和计算机科学的其他领域非常重要。

本文将重点介绍如何使用 C 语言有效地输出质数。我们将探讨不同的算法并提供代码示例来帮助您理解质数的生成过程。

素数筛算法

素数筛算法是一种经典算法，用于生成质数。它的基本思想是创建一个布尔数组，其中索引对应于自然数，并且每个元素的值指示该数字是否是质数。该算法从 2 开始遍历每个整数，并将其倍数标记为非质数。这个过程一直持续到数组中没有更多的元素需要检查。

下面是使用素数筛算法在 C 语言中查找和输出质数的示例代码：```c
#include
#include
int main() {
int n;
// 创建一个布尔数组，其中索引对应于整数，值表示是否为质数
int *isPrime = (int *)calloc(1000, sizeof(int));
// 默认情况下，将所有数字标记为质数
for (int i = 0; i < 1000; i++) {
isPrime[i] = 1;
}
// 遍历所有整数并标记其倍数为非质数
for (int i = 2; i < 1000; i++) {
if (isPrime[i] == 1) {
for (int j = i * i; j < 1000; j += i) {
isPrime[j] = 0;
}
}
}
// 输出所有质数
printf("质数：");
for (int i = 2; i < 1000; i++) {
if (isPrime[i] == 1) {
printf(" %d", i);
}
}
printf("");
return 0;
}
```

欧拉筛算法

欧拉筛是素数筛算法的一种优化，它可以减少标记非质数所需的步骤数量。欧拉筛的思想是，对于每个质数 p，只检查其倍数是否为非质数，而忽略其他非质数的倍数。这样可以减少标记非质数所需的迭代次数。

下面是使用欧拉筛算法在 C 语言中查找和输出质数的示例代码：```c
#include
#include
int main() {
int n;
// 创建一个布尔数组，其中索引对应于整数，值表示是否为质数
int *isPrime = (int *)calloc(1000, sizeof(int));
// 默认情况下，将所有数字标记为质数
for (int i = 0; i < 1000; i++) {
isPrime[i] = 1;
}
// 遍历所有整数并标记其倍数为非质数
for (int i = 2; i < 1000; i++) {
if (isPrime[i] == 1) {
for (int j = i * i; j < 1000; j += i) {
isPrime[j] = 0;
}
}
}
// 输出所有质数
printf("质数：");
for (int i = 2; i < 1000; i++) {
if (isPrime[i] == 1) {
printf(" %d", i);
}
}
printf("");
return 0;
}
```