Números primos são aqueles cujos únicos divisores positivos são $1$ e ele próprio.
O algoritmo mais antigo que se tem conhecimento é o chamado Crivo de Erastótenes, que consiste nos seguintes passos:
1. Marca-se o $2$, o menor primo positivo.
2. Marcam-se todos os múltiplos de $2$ até o número ao qual deseja-se conhecer sua primalidade.
3. Marca-se o próximo número primo logo após o antecessor.
4. Repete-se o processo de marcar todos os seus múltiplos.
E assim sucessivamente até chegarmos ao número dado.
Se todos os números positivos menores que o número dado forem marcados, tal número é primo.
Mas existe um procedimento menos trabalhoso. É baseado no seguinte raciocínio:
Um número é primo se não for divisível por nenhum número natural menor que o maior natural cujo quadrado não seja maior que tal número.
Consideremos como exemplo o número $97$. Observemos que $9^2\ <\ 97\ <\ 10^2$
Logo $9$ é o maior número natural cujo quadrado não supera $97$.
Se $97$ não for primo, ele será igual ao produto de dois fatores $f_1$ e $f_2$. Teremos então $97\ =\ f_1\ \cdot\ f_2$.
Se $f_1 > 9$ e $f_2 > 9$, $f_1\ \cdot\ f_2 > 97$.
Se $f_1 < 9$ e $f_2 < 9$, $f_1\ \cdot\ f_2 < 97$.
Dessa forma concluímos que o número $97$, não sendo primo, admite, obrigatoriamente um divisor menor ou igual a $9$.
Como $97$ não possui nenhum divisor positivo entre $2$ e $9$, ele é primo.
Este último procedimento diminui bastante o tempo de processo que um computador demandaria para afirmar se um número é primo ou não.
 |
Nenhum comentário:
Postar um comentário