Introdução
Compraste uma caixa grande de peças de computador aleatórias numa venda de garagem.
Começaste a juntar as peças para montar computadores à medida.
Queres testar o desempenho de diferentes combinações de peças e decides criar o teu próprio programa de avaliação de desempenho para ver como os teus computadores se comparam.
Escolhes o famoso algoritmo "Crivo de Eratóstenes", um algoritmo antigo, mas que deve levar os teus computadores ao limite.
Instruções
A tua 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 dado.
Um número primo é um número maior do que 1 que só é divisível por 1 e por si próprio.
Por exemplo, 2, 3, 5, 7, 11 e 13 são números primos.
Em contrapartida, 6 não é um número primo, pois não só é divisível por 1 e por si próprio, como também por 2 e por 3.
Para usar o Crivo de Eratóstenes, começas por criar uma lista com todos os números entre 2 e o número dado.
Depois, repetes os seguintes passos:
- Encontra o próximo número não marcado da tua lista (saltando os números marcados).
Este número é primo.
- Marca todos os múltiplos desse número primo como não primos.
Continuas a repetir estes passos até teres percorrido todos os números da tua lista.
No final, todos os números não marcados são primos.
Os testes não verificam se implementaste o algoritmo, apenas se chegaste à lista correta de primos.
Para verificares se estás a implementar o Crivo corretamente, um bom primeiro teste é verificar que não usas operações de divisão ou de resto.
Exemplo
Imagina que estás a encontrar os números primos menores ou iguais a 10.
- Escreve 2, 3, 4, 5, 6, 7, 8, 9 e 10 numa lista, deixando-os todos não marcados.
- O 2 não está marcado e, por isso, é primo.
Marca o 4, o 6, o 8 e o 10 como "não primo".
- O 3 não está marcado e, por isso, é primo.
Marca o 6 e o 9 como "não primo" (marcar o 6 é opcional, uma vez que já está marcado).
- O 4 está marcado como "não primo", por isso ignoramo-lo.
- O 5 não está marcado e, por isso, é primo.
Marca o 10 como "não primo" (opcional, uma vez que já está marcado).
- O 6 está marcado como "não primo", por isso ignoramo-lo.
- O 7 não está marcado e, por isso, é primo.
- O 8 está marcado como "não primo", por isso ignoramo-lo.
- O 9 está marcado como "não primo", por isso ignoramo-lo.
- O 10 está marcado como "não primo", por isso paramos, pois já não há mais números para verificar.
Examinaste todos os números e verificaste que 2, 3, 5 e 7 continuam não marcados, o que significa que são os números primos menores ou iguais a 10.
