CRIVO DE ERASTÓTENES e DIVISÃO POR TENTATIVA

Os testes rápidos de primalidade são utilizados para a determinação de primos pequenos. São processos manuais que, obviamente, também podem ser realizados pelo computador. Seus algoritmos são simples porém não necessariamente rápidos, tanto é que, em determinadas situações, os procedimentos manuais são mais rápidos que os informatizados.

O CRIVO DE ERATÓSTENES

Para encontrar todos os números primos numa lista de números inteiros pequenos, o modo mais rápido e fácil é o de Erastótenes. Tendo em conta que a multiplicação é uma operação mais fácil de realizar do que a divisão, Erastótenes de Cirene (no século III a.C.) teve a brilhante idéia de organizar estas computações em forma de crivo ou peneira.

Criando um crivo

Um dos meios mais eficientes de achar todos os números primos pequenos, por exemplo os menores que 10.000.000, é usando o Crivo de Erastótenes (± 240 a.C.). Basta fazer uma lista com todos os inteiros maiores que um e menores ou igual a n e riscar os múltiplos de todos os primos menores ou igual à raiz quadrada de n (n^½). Os números que não estiverem riscados são os números primos.

Vamos determinar, por exemplo, os primos menores ou igual a 20:

1. Inicialmente faz-se a lista dos inteiros de 2 a 20.

2. O primeiro número (2) é primo. Vamos mantê-lo e riscar todos os seus múltiplos. Desta forma, obtemos:

3. O próximo número "livre" é o 3, outro primo. Vamos mantê-lo e riscar seus múltiplos:

4. O próximo número primo é 5, porém não é necessário repetir o procedimento porque 5 é maior que a raiz quadrada de 20 (20^½ = 4,4721). Os números restantes são primos, destacados abaixo:

Os números primos encontrados foram {2, 3, 5, 7, 11, 13, 17, 19}.

A DIVISÃO POR TENTATIVA

Para determinar se um determinado número inteiro pequeno é primo, a divisão por tentativa funciona bem. Basta dividí-lo por todos os primos menores ou igual à sua raiz quadrada.

Por exemplo, queremos saber se 323 é um número primo. A raiz quadrada de 323 é 323^½ = 17,9722, portanto, vamos dividir 323 por 2, 3, 5, 7, 11 e 17. Se nenhum destes primos dividir 323, então ele será primo:

O inteiro 323 NÃO é primo porque é dividido por 17.

Se estivéssemos procurando por um primo titânico, com mais de 10.000 dígitos decimais, nunca poderíamos dividí-lo por todos os primos menores que a sua raiz quadrada. Ainda assim, mesmo nestes casos a divisão por tentativa é utilizada, somente para fazer um rastreamento inicial. Faz-se divisões por alguns milhões de primos pequenos e depois aplica-se um teste de primalidade.

No caso de n ter 25 dígitos ou mais, a divisão por tentativa usando primos menores que sua raiz quadrada é impraticável. Se n tiver 200 dígitos, então a divisão por tentativa é impossível.

Esta página

Notice: Undefined variable: fecha in /home/numaboa.com.br/public_html/criptologia/footCript.php on line 49
Criptologia Matemática Teoria dos Números
Notice: Undefined variable: indica in /home/numaboa.com.br/public_html/criptologia/footCript.php on line 175
CRIVO DE ERASTÓTENES E DIVISÃO POR TENTATIVA
Notice: Undefined variable: imgR in /home/numaboa.com.br/public_html/criptologia/footCript.php on line 179

---

Créditos: Chris Caldwell e NumaBoa.

---

| Indique aos amigos | Fale com a mestre da teia | Voltar
Notice: Undefined variable: fecha in /home/numaboa.com.br/public_html/criptologia/footCript.php on line 196
| Sobre a autora |

sobMedida by vickiSoft - /criptologia/matematica/testRapid.php Versão 1.2 de 25.09.02 - Atualizada em 27.08.03
Licença Creative Commons 1998-2006 Aldeia NumaBoa
Exceto onde especificamente declarado, todo material deste site é disponibilizado de acordo com a Licença Creative Commons.