Um possível algoritmo que o permite determinar se um número positivo é
primo enuncia-se em quatro passos da seguinte maneira:
i)
assumir que o número positivo pode ser primo;
ii) dividir sucessivamente o número possivelmente primo, por todos
os inteiros compreendidos entre a unidade e o valor que
represente metade dele próprio, testando se o resto dessa divisão
dá valor zero;
iii) se o resto for zero o número não é primo;
iv) se o resto não for zero, o número deverá ser divido novamente
agora pelo inteiro seguinte;
v) o número é primo se após efectuadas todas as divisões não
resultar nenhum resto de valor zero;
Nota: Um número é primo se for só divisível pelo número um e por ele
próprio.
/* algoritmo para determinar se um número é primo */
logico primo(n)
inteiro n;
{
inteiro m, i;
logico primo;
m = n / 2;
i = 2;
primo = Verdadeiro;
se (n < 1) então
{
retorna( Falso);
}
enquanto (i <= m e primo) faça
{
se (n % i == 0 ) então
{
primo = Falso;
}
i = i + 1;
}
retorna( primo );
}
programa numerosprimos( )
/* programa números primos */
{
inteiro n;
leia(n);
enquanto (n != 0) faça
{
se ( primo(n) ) então
{
escreva(n,“ é número primo”);
}
senão
{
escreva(n,“ não é número primo”);
}
leia(n);
}
}