Реализация решета Эратосфена на C

Введение

В этом практическом занятии вы научитесь реализовывать алгоритм «Решето Эратосфена» на языке C для нахождения простых чисел до заданного верхнего предела. Вы начнете с чтения верхнего предела от пользователя, затем будете отмечать кратные простым числам как непростые, и, наконец, будете выводить все найденные простые числа. В этом практическом занятии рассматриваются концепции теории чисел и дискретной математики с использованием языка программирования 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("Marking multiples complete.\n");

    return 0;
}

Скомпилируем и запустим программу:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Пример вывода:

Enter the upper limit for finding prime numbers: 50
Marking multiples complete.

Рассмотрим логику «Решета Эратосфена»:

• Мы создаем булевый массив 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("Prime numbers up to %d are:\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
Prime numbers up to 50 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Рассмотрим последние шаги:

• После отметки кратных чисел мы перебираем массив is_prime
• Мы выводим только те числа, которые по-прежнему отмечены как простые
• Вывод показывает все простые числа до заданного пользователем предела

Резюме

В этом практическом занятии вы сначала узнали, как читать верхний предел для алгоритма «Решето Эратосфена» на языке C. Вы создали C-файл prime_sieve.c и написали код для запроса у пользователя верхнего предела и сохранения его в переменную upper_limit. Затем вы реализовали核心逻辑алгоритма «Решето Эратосфена», создав булевый массив для отметки простых и непростых чисел. Вы инициализировали все числа как простые и затем отметили кратные каждого простого числа как непростые. Наконец, вы узнаете, как вывести все простые числа в заданном верхнем пределе.