c语言求质数的最优算法

在 C 语言中，求质数的常见算法有几种，但通常我们会倾向于效率较高的算法。埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种常用且相对高效的查找质数的方法。以下是简单的原理和代码实现：

**埃拉托斯特尼筛法**：
1. 创建一个从 0 到 n 的布尔数组，初始所有元素设为 true，表示所有数字都是潜在的质数。
2. 遍历数组，从 2 开始（因为 1 不是质数），将每个质数的倍数都标记为非质数（即 false）。
3. 遍历结束时，未被标记为 false 的数字就是质数。

#include <stdio.h>
#define MAX 1000000

int isPrime(int n) {
    if (n <= 1)
        return 0;
    if (n == 2 || n == 3)
        return 1;

    // 如果 n 能够被 2 或 3 整除，它不是质数
    if (n % 2 == 0 || n % 3 == 0)
        return 0;

    // 检查 n 是否能被 6k ± 1 的值整除，其中 k 是正整数
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;

    return 1;
}

int main() {
    int limit = MAX;
    int primeNumbers[MAX];
    int count = 0;

    for (int i = 2; i <= limit; ++i) {
        if (isPrime(i)) {
            primeNumbers[count++] = i;
            printf("%d ", i);
        }
    }

    return 0;
}