Edição didática em português. O código e suas saídas preservam o original.

Crivo de Eratóstenes em C

Encontre todos os primos até um limite marcando seus múltiplos.

Crie um array que indique os candidatos de 0 até N. Marque 0 e 1 como não primos. Para cada candidato primo p, elimine seus múltiplos; você pode começar em p * p porque os múltiplos menores já têm um fator menor.

Só é necessário iniciar marcações para p até a raiz de N. Evite estouro em p * p ao generalizar para limites grandes, por exemplo comparando p <= N / p com p positivo. Confira se o buffer inclui o índice N.

O crivo clássico utiliza memória O(N) e aproximadamente tempo O(N log log N). Teste limites 0, 1, 2 e um valor maior; o limite pode exigir adaptar o exemplo.

Código 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;
}

Abrir no compilador

Saída esperada

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

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.