Setor fatorial
Pra testar se
um número n é primo a primeira idéia é o dividir sucessivamente por 2 até por
n-1. Mas isso é um desperdício, pois se nota que depois da metade não há mais
divisor.
Então a idéia
seria o dividir por 2 até o inteiro da metade. Mas também é um desperdício.
O número 24,
tendo muitos divisores, é um bom exemplo da distribuição dos fatores.
Excetuando o 1 e o 24, se vê que os fatores estão entre 2 e o inteiro da
metade. Mas se deve usar só um lado desse setor, pois é o produto
correspondente, um espelho.
Temos dois setores
espelhados. Uma entre 2 e o inteiro da raiz quadrada e a outra entre o inteiro
da raiz quadrada e o inteiro da metade.
Ou seja: Se o
número tiver divisor, esse divisor estará nesses dois setores.
As duas
regiões não têm o mesmo tamanho, sendo imensa a diferença quando for um número
muito grande. Portando se deve usar o primeiro setor, variando de 2 até int√n.
Não precisa dividir por todos os números, apenas pelos primos.
Assim, por
exemplo, pra saber se o número 289 é primo usar o setor fatorial variando de 2
até 17, só considerando os primos. Ou seja, o dividir sucessivamente por 2, 3, 5, 7, 11, 13 e 17. Um resultado
inteiro e se aborta o processo, pois não é primo. Se nenhuma divisão der
resultado inteiro o número é primo.
O número 2991
tem o setor menor entre 2 e 173. Pra verificar se é primo se deve dividir
sucessivamente apenas pelos primos nesse intervalo.
Nenhum comentário:
Postar um comentário