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.