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 algoritmo do Crivo de Eratóstenes para encontrar todos os números primos menores ou iguais a um número qualquer.
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, você primeiro cria uma lista de todos os números entre 2 e o número dado.
Depois, repete os seguintes passos:
- Encontre o próximo número ainda não marcado da sua lista (pulando os que já estão marcados).
Esse número é primo.
- Marque todos os múltiplos desse número primo como não primos.
Você repete esses passos até ter passado por todos os números da sua lista.
No final, todos os números que não foram marcados são primos.
Os testes não verificam se você implementou o algoritmo, apenas se você chegou à lista correta de primos.
Para verificar se você está implementando o Crivo corretamente, um bom primeiro teste é verificar se você não usa operações de divisão nem de resto.
Exemplo
Digamos que você esteja encontrando os primos menores ou iguais a 10.
- Liste 2, 3, 4, 5, 6, 7, 8, 9, 10, deixando todos sem marcação.
- O 2 não está marcado e, portanto, é primo.
Marque 4, 6, 8 e 10 como "não primo".
- O 3 não está marcado e, portanto, é primo.
Marque 6 e 9 como não primos (marcar o 6 é opcional, pois ele já está marcado).
- O 4 está marcado como "não primo", então pulamos esse número.
- O 5 não está marcado e, portanto, é primo.
Marque o 10 como não primo (opcional, pois ele já está marcado).
- O 6 está marcado como "não primo", então pulamos esse número.
- O 7 não está marcado e, portanto, é primo.
- O 8 está marcado como "não primo", então pulamos esse número.
- O 9 está marcado como "não primo", então pulamos esse número.
- O 10 está marcado como "não primo", então paramos, pois não há mais números para verificar.
Você examinou todos os números e descobriu que 2, 3, 5 e 7 continuam sem marcação, o que significa que eles são os primos menores ou iguais a 10.
