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.

Simulação do Crivo de Eratóstenes. Clique nos números e tente habilitar todos os números primos, enquanto desabilita todos os outros.

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.

Vamos simular esse processo para n=100:

prime = [False, False, True, True, ..., True] de tamanho 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 e marcar prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 e marcar prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 e marcar prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 e marcar prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [empty] e marcar prime[j]=False

Podemos parar nesse ponto, pois i * i já é maior que n. Portanto, não iremos mais marcar nenhum primo como False. Podemos apenas percorrer a lista e imprimir todos os que são primos menores que 100 aqui.

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

Entrada	Saída
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Propriedades Interessantes e Otimizações do Algoritmo

Entrada

Saída

Exemplos

Constraints

To check your solution you need to sign in

Sign in to continue