Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Решето Эратосфена на C

Находите все простые числа до заданной границы, отмечая кратные.

Создайте массив кандидатов от 0 до N; исключите 0 и 1. Для каждого простого p отмечайте его кратные. Можно начинать с p * p: меньшие кратные уже имеют меньший простой делитель.

Начинать вычёркивание нужно лишь для p до корня из N. При больших пределах избегайте переполнения p * p, например используя p <= N / p для положительного p. В буфере должна существовать позиция N.

Классический вариант требует O(N) памяти и примерно O(N log log N) времени. Проверьте границы 0, 1, 2 и более крупное значение; для новых пределов может потребоваться изменить пример.

Код C

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

void sieve(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    printf("Primes up to %d:\n", n);
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) printf("%d ", p);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

Открыть в компиляторе

Ожидаемый вывод

Primes up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.