Crivo de Eratóstenes

É possível encontrar todos os números primos menores do que n de uma forma muito mais rápida do que fazer um teste de primalidade para cada número de 2 até n. Em vez de verificar cada número, podemos proativamente remover da lista todos os números que sabemos que não serão primos.

Para começar, podemos ter todos os números de 2 até n marcados como “possivelmente primos”. Em seguida, removemos todos os múltiplos de 2 dessa lista e marcamos o 2 como “definitivamente primo”. Depois, removemos todos os múltiplos de 3 da lista e marcamos o 3 como “definitivamente primo”. Em seguida, pulamos o 4, pois ele já foi removido anteriormente ao processar o 2. O próximo número a considerar será 5, e também removeremos todos os múltiplos de 5. Pulamos o 6, pois ele foi marcado como não primo quando processamos o 2. Podemos continuar esse procedimento até chegarmos em n.

Propriedades Interessantes e Otimizações do Algoritmo

Uma grande consequência de remover todos os múltiplos de um número primo p da lista de “possivelmente primos” a partir do menor (2), e depois ir gradualmente aumentando o p, é que, em vez de processar todos os múltiplos 2·p, 3·p, 4·p, 5·p..., podemos começar diretamente de p·p. Isso acontece porque todos os múltiplos de p como 2·p, 3·p, 4·p, 5·p já foram removidos da lista de “possivelmente primos” quando processamos os números 2, 3, 5… assim, o primeiro número que ainda não foi removido é exatamente p·p.

Portanto, quando começamos a processar p=3, podemos iniciar diretamente em 9, pois 6 já havia sido removido ao processar o número 2. Da mesma forma, ao processar p=5, podemos começar diretamente em 25, pois 10 (10 = 2·5) foi removido quando processamos o 2, 15 (15 = 3·5) foi removido ao processarmos o 3 e, finalmente, 20 (20 = 4·5) foi removido também quando processamos o 2.

prime = [True] * n                    # prime[i] = True => i é um número primo
prime[0] = prime[1] = False           # 0 e 1 não são primos

for i in range(2, n):                 # Loop de 2 até n
    if prime[i]:                      # se i é primo => marcar todos os múltiplos de i como não primos
        for j in range(i * i, n, i):  # começamos de i*i porque todos os múltiplos de i menores já foram marcados
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Essa abordagem é significativamente mais rápida e executa operações. É um ganho enorme! Fazer operações ao invés de faz uma diferença gigantesca. Voltando àquele exemplo em que o algoritmo levaria 10 anos (3650 dias) para terminar um cálculo se fizesse n operações, ou 2 meses (61 dias) se realizasse operações, com só precisaria de menos de 4 dias!

Mais uma otimização que mencionamos na simulação é que basta iterar i de 2 até , pois o loop interno começa em i·i. Sendo assim, para todos os números maiores que a raiz quadrada de n, não chegaremos a marcar nenhum prime[j] = False no loop interno (já que o limite superior do loop interno é n).

Entrada

A primeira linha da entrada contém um único inteiro n (2 ≤ n ≤ ).

Saída

O programa deve imprimir todos os números primos menores ou iguais a n.

Exemplos