Introdução
Você comprou uma caixa grande de peças de computador aleatórias numa venda de garagem.
Começou a montar as peças para construir computadores personalizados.
Quer testar o desempenho de diferentes combinações de peças e decide criar seu próprio programa de benchmarking para comparar seus computadores.
Escolhe então o famoso algoritmo "Crivo de Eratóstenes", um algoritmo antigo, mas que deve levar seus computadores ao limite.
Instruções
Sua tarefa é criar um programa que implemente o Crivo de Eratóstenes para encontrar todos os números primos menores ou iguais a um determinado número.
Um número primo é um número maior que 1 que só é divisível por 1 e por ele mesmo.
Por exemplo, 2, 3, 5, 7, 11 e 13 são números primos.
Já o 6 não é um número primo, pois além de ser divisível por 1 e por ele mesmo, também é divisível por 2 e por 3.
Para usar o Crivo de Eratóstenes, primeiro escreva todos os números de 2 até o número que você escolheu, inclusive.
Depois, siga estes passos:
- Encontre o próximo número sem marcação (pulando os números já marcados).
Esse número é primo.
- Marque todos os múltiplos desse número primo como não primos.
Repita os passos até ter passado por todos os números.
No final, todos os números sem marcação são primos.
O Crivo de Eratóstenes marca os múltiplos de cada primo usando soma (somando o primo repetidamente) ou multiplicação (calculando os múltiplos diretamente), em vez de verificar se cada número é divisível.
Os testes não verificam se você implementou o algoritmo, apenas se você chegou aos primos corretos.
Exemplo
Digamos que você esteja buscando os primos menores ou iguais a 10.
-
Escreva 2, 3, 4, 5, 6, 7, 8, 9, 10, deixando todos sem marcação.
2 3 4 5 6 7 8 9 10
-
O 2 está sem marcação e, portanto, é primo.
Marque 4, 6, 8 e 10 como "não primo".
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
O 3 está sem marcação e, portanto, é primo.
Marque 6 e 9 como não primo (marcar o 6 é opcional, pois ele já foi marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 4 está marcado como "não primo", então pulamos ele.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 5 está sem marcação e, portanto, é primo.
Marque 10 como não primo (opcional, pois ele já foi marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 6 está marcado como "não primo", então pulamos ele.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 7 está sem marcação e, portanto, é primo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 8 está marcado como "não primo", então pulamos ele.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 9 está marcado como "não primo", então pulamos ele.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 10 está marcado como "não primo", então paramos, pois não há mais números para verificar.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Você examinou todos os números e viu que 2, 3, 5 e 7 continuam sem marcação, ou seja, são os primos menores ou iguais a 10.
