如何用 C 语言实现埃拉托斯特尼筛法

简介

在本实验中，你将学习如何用 C 语言实现埃拉托斯特尼筛法（Sieve of Eratosthenes）算法，以找出小于等于给定上限的所有质数。你将首先从用户那里读取上限，然后将质数的倍数标记为非质数，最后打印出找到的所有质数。本实验使用 C 编程语言涵盖了数论和离散数学中的概念。

该实验包括三个主要步骤：读取上限、将倍数标记为非质数以及打印所有质数。通过遵循这些步骤，你将更深入地理解埃拉托斯特尼筛法算法及其在 C 语言中的实现。

读取上限

在这一步中，你将学习如何在 C 语言中读取埃拉托斯特尼筛法算法的上限。上限决定了我们要查找的质数范围。

首先，让我们为我们的实现创建一个新的 C 文件：

cd ~/project
nano prime_sieve.c

现在，让我们编写读取上限的初始代码：

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    printf("Upper limit entered: %d\n", upper_limit);

    return 0;
}

编译并运行程序：

gcc prime_sieve.c -o prime_sieve
./prime_sieve

示例输出：

Enter the upper limit for finding prime numbers: 50
Upper limit entered: 50

让我们来分析一下这段代码：

我们使用scanf()从用户那里读取一个整数输入
%d格式说明符告诉scanf()读取一个整数
我们将输入存储在upper_limit变量中
然后我们打印输入的上限以确认输入

将倍数标记为非质数

在这一步中，你将实现埃拉托斯特尼筛法算法的核心逻辑，将质数的倍数标记为非质数。

让我们修改之前的prime_sieve.c文件：

cd ~/project
nano prime_sieve.c

更新代码以包含一个数组并标记倍数：

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // 创建一个布尔数组来标记质数和非质数
    bool is_prime[upper_limit + 1];

    // 将所有数字初始化为质数
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // 将每个质数的倍数标记为非质数
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // 将 p 的倍数标记为非质数
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("标记倍数完成。\n");

    return 0;
}

编译并运行程序：

gcc prime_sieve.c -o prime_sieve
./prime_sieve

示例输出：

Enter the upper limit for finding prime numbers: 50
标记倍数完成。

让我们来分析一下埃拉托斯特尼筛法的逻辑：

我们创建一个布尔数组is_prime来跟踪质数和非质数
最初，所有数字都被标记为质数
我们遍历从 2 到 sqrt(上限) 的数字
对于每个质数，我们将其倍数标记为非质数
我们从 p^2 开始标记以优化算法
内层循环每次增加 p 以标记 p 的所有倍数

打印所有质数

在这一步中，你将通过打印在给定范围内找到的所有质数来完成埃拉托斯特尼筛法的实现。

让我们修改prime_sieve.c文件以添加打印功能：

cd ~/project
nano prime_sieve.c

更新代码以打印质数：

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // 创建一个布尔数组来标记质数和非质数
    bool is_prime[upper_limit + 1];

    // 将所有数字初始化为质数
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // 将每个质数的倍数标记为非质数
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // 将 p 的倍数标记为非质数
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // 打印所有质数
    printf("小于等于 %d 的质数有：\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

编译并运行程序：

gcc prime_sieve.c -o prime_sieve
./prime_sieve

示例输出：

Enter the upper limit for finding prime numbers: 50
小于等于 50 的质数有：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

让我们来分析一下最后的步骤：

在标记完倍数之后，我们遍历is_prime数组
我们只打印那些仍然被标记为质数的数字
输出显示了所有小于等于用户指定上限的质数

总结

在本实验中，你首先学习了如何在 C 语言中读取埃拉托斯特尼筛法算法的上限。你创建了一个 C 文件prime_sieve.c，并编写代码提示用户输入上限并将其存储在upper_limit变量中。然后，你通过创建一个布尔数组来标记质数和非质数，实现了埃拉托斯特尼筛法算法的核心逻辑。你将所有数字初始化为质数，然后将每个质数的倍数标记为非质数。最后，你学习了如何打印给定上限内的所有质数。