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 determinado número.
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, o 6 não é um número primo, pois não é apenas divisível por 1 e por si próprio, mas também por 2 e por 3.
Para usar o Crivo de Eratóstenes, começa por escrever todos os números desde o 2 até ao teu número, inclusive.
Depois, segue estes passos:
- Encontra o próximo número que ainda não está marcado (saltando por cima dos que já estão marcados).
Esse número é primo.
- Marca todos os múltiplos desse número primo como não primos.
Repete os passos até teres passado por todos os números.
No fim, todos os números que ficaram por marcar são primos.
O Crivo de Eratóstenes marca os múltiplos de cada primo através da adição (somar o primo repetidamente) ou da multiplicação (calcular diretamente os seus múltiplos), em vez de verificar se cada número é divisível.
Os testes não verificam se implementaste o algoritmo, apenas se chegaste aos primos corretos.
Exemplo
Imagina que estás a encontrar os primos menores ou iguais a 10.
-
Escreve 2, 3, 4, 5, 6, 7, 8, 9 e 10, deixando-os todos por marcar.
2 3 4 5 6 7 8 9 10
-
O 2 está por marcar e, por isso, é primo.
Marca 4, 6, 8 e 10 como «não primos».
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
O 3 está por marcar e, por isso, é primo.
Marca 6 e 9 como não primos (marcar o 6 é opcional, uma vez que já está marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 4 está marcado como «não primo», por isso saltamo-lo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 5 está por marcar e, por isso, é primo.
Marca 10 como não primo (opcional, uma vez que já está marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 6 está marcado como «não primo», por isso saltamo-lo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 7 está por marcar e, por isso, é primo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 8 está marcado como «não primo», por isso saltamo-lo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 9 está marcado como «não primo», por isso saltamo-lo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
O 10 está marcado como «não primo», por isso paramos, pois já não há mais números para verificar.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Examinaste todos os números e viste que 2, 3, 5 e 7 continuam por marcar, ou seja, são os primos menores ou iguais a 10.
