números primo
331 palavras
2 páginas
Algoritmo para definir números primosO algoritmo se baseia numa "peneira": ele vai testando se um número é primo e, se for, elimina todos os seus múltiplos. Pode-se começar com um conjunto de números naturais não -nulos .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
50
O menor número primo é o 2, mas qualquer outro que seja divisível por 2 não é primo, certo? Então, mantém-se o 2 e excluem-se todos os seus múltiplos,
2 3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
o que elimina metade da lista!
O próximo número primo é 3. Deve-se mantê-lo e excluir os múltiplos de 3, uma vez que um número múltiplo de 3 não pode ser primo:
2
3
5
7
11
13
17
19
23
25
29 31
35
37
41
43
49
E o 4? Quando se eliminam os múltiplos de 2, também se eliminaram os múltiplos de 4, 6, 8, e todos os números pares! É por esse motivo que o crivo é tão eficiente: ao excluir os múltiplos de um número primo, não há necessidade de verificar aqueles múltiplos.
Daí, pode-se passar ao próximo número da sequência, que é exatamente o próximo primo, o 5. Removendo os múltiplos de 5 (a essa altura, só restam o 25 e o 35) e fazendo o mesmo com o próximo da sequência que é o 7 (removendo apenas o 49), fica-se assim:
2
3
5
7
11
13
17
19
23
29 31
37
41
43
47
Todos os números que sobraram na lista são primos!
Múltiplos de 11
Você poderia se perguntar se o