Olá, este post é o resultado de uma pequena conversa com meu irmão sobre um algoritmo simples para se calcular se um número é primo ou não no computador. Como não há uma fórmula simples que diz se um número é primo ou não, o melhor jeito que encontramos para fazer isso foi pela definição.
Considerações iniciais
A partir deste momento, todos os números tratados por este post, quando não especificado o contrário, pertencem aos naturais.
Definição
Um número maior que 1 é primo quando é divisível apenas por 1 e por ele mesmo. Em um primeiro momento, dado um número n qualquer, podemos pensar em testar a divisão de n por todos os números entre 2 e n-1 e, se algum número dividir n, n não é primo. Mas a grande questão é: Precisamos realmente testar com todos os números?
Quais números testar?
Dado um número n, para o nosso algoritmo, podemos primeiramente verificar se o número é menor que 2, ou seja, ele é 0 ou 1, e classificamos como não-primo. Caso contrário, se ele for 2 ou 3, ou seja 1<> 3). Se for divisível, n não é primo. Senão, testamos com 3. A partir deste ponto, caso não seja divisível, vamos ter que começar a chutar os próximos números a serem testados para dividir n.
Pela definição de paridade, qualquer número divisível por 2 é par, assim, não existem números primos pares fora o próprio dois, pois eles teriam que dividir por 2. Assim, podemos reduzir pela metade o nosso conjunto de busca, tomando apenas os números ímpares. Isto é, até o agora, estamos testando se n é divisível por 2, 3, 5, 7, 9, 11...
Certo, mas quando eu paro de procurar?
Não faz sentido procurarmos infinitamente. Um número não possui divisores maiores que ele mesmo. Então, uma primeira condição de parada lógica seria até n-1, já que não faz sentido dividir pelo próprio n. Mas, será que este é o melhor ponto para se parar? Será que não tem como eu testar a divisibilidade de n por um conjunto menor de números?
A resposta é sim. Se você pegar um n qualquer e escrever seus divisores perceberá uma coisa. O menor divisor, diferente de 1, possível de um número é o 2. Se ele é o menor, então, logicamente, ele deve ser multiplicado pelo maior divisor para resultar em n, ou seja, o maior divisor de n é n/2. Viram? Acabamos de reduzir pela metade o número de operações realizadas pelo nosso algoritmo.
Mas ainda há uma condição de parada muito melhor. Ela pode ser encontrada da seguinte forma:
Suponha um número n, não primo, tal que:
onde p é o menor primo que divide n e p <= q (q não precisa ser primo) O mínimo valor que q pode assumir é p. Se trocarmos q por outro p, chegamos a seguinte verdade:
Ou seja, o menor fator primo de um número é no máximo igual a raiz quadrada desse número. Dessa forma, reduzimos muito mais o número de operações que o nosso algoritmo realiza, pois
para n maior ou igual a 2 (verifique!). Pense, por exemplo, em verificar se o número 101 é primo. Ao invés de verificar os fatores primos até 50, poderíamos verificar só até 10, que é um ganho enorme.
Resumindo nosso algoritmo
Função é_primo (n) : booleano[1]
| Se n < 2 então retorne FALSO
| Se n < 4 retorne VERDADEIRO
| /* Se está aqui é porque n é maior ou igual a 4 */
| Se (n módulo 2) = 0 então retorne FALSO
| /* Se está aqui então n não é par */
| para i = 3 enquanto i
faça| | Se (n módulo i) = 0 então retorne FALSO
| | i = i+2
| fim
| /* Se o programa chegou até aqui é porque n é primo */
| retorne VERDADEIRO
fim
Conclusão
Minha idéia aqui foi mostrar o processo de construção de um algoritmo e montar um algoritmo simples que verificasse se um determinado número é primo ou não. Para números primos de muitas casas decimais, existem algoritmos melhores, mas são muito mais complexos e ficam fora do escopo deste post, que é mostrar algo que todos entendam.
Alguma dúvida?
Quem tiver sugestões de como otimizar ainda mais este algoritmo, sem prejudicar sua simplicidade ou didática, fique a vontade para colaborar :)
Notas
[1] booleano é um tipo de dado que pode assumir dois valores, VERDADEIRO ou FALSO. Em algumas linguagens de programação, VERDADEIRO é o valor inteiro 1 e FALSO é o valor inteiro 0.
[2] Aqui haverá problemas em muitas linguagens de programação se você não tomar cuidado. Normalmente, o seu i será algum tipo inteiro, porém a função raiz quadrada é de algum tipo de ponto flutuante, assim, talvez seja necessário converter o a raiz quadrada para um tipo inteiro também.
Leia mais
Artigo da wikipedia
4 comentários:
Muito legal o post. Aliás, só uma curiosidade, hoje descobri que a complexidade deste algoritmo é exponencial.
Que tal um script haskell para isso?
Implementei isso pro bicho aqui do meu quarto isso semana passada. O programinha calcula todos os primos até o número de entrada:
#include "stdio.h"
#include "math.h"
int main()
{
long p, n, temp;
int teste, i;
char opcao;
do
{
printf("Digite um numero: ");
scanf("%d", &n);
printf("\n\n");
for(i=n; i(maior_ou_igual_a)2; i--)
{
temp = (long)sqrt(i);
teste = 1;
for(p=2;p (menor_que) temp;p++)
{
if( i % p == 0 )
{
teste = 0;
break;
}
}
if( teste )
printf(" %d ", i);
}
scanf("%f", &opcao);
}
while(opcao != 's');
fflush(stdin);
getchar();
return(0);
}
PS: me esqueci de novo de ler o pdf sobre o jogo do petrus! =P
PS2: tive que remover os sinais de maior e menor pra para de dar zica (e que estou com preguiça de passar aqueles e parentes)! ;D
Postar um comentário