Fatoração de números inteiros. Divisão por tentativa

Fatoração de números inteiros usando algoritmo de divisão por tentativa.

De repente, preciso fatorar alguns números inteiros. Como não presumi que meus inteiros fossem números enormes, eu implementei o método de divisão por tentativa. A descrição do método está abaixo da calculadora.

PLANETCALC, Fatoração de números inteiros. Divisão por tentativa

Fatoração de números inteiros. Divisão por tentativa

Fatoração
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

Fatoração de números inteiros

Na teoria dos números, a fatoração de números inteiros ou fatoração de números primos é a decomposição de um número composto em divisores não triviais menores, que, quando multiplicados juntos, são iguais ao número inteiro original.

E, como a divisão por tentativa é a mais fácil de entender dos algoritmos de fatoração de números inteiros, aqui estão algumas frases da Wikipédia:

Dado um número inteiro n (o inteiro a ser fatorado), a divisão por tentativa consiste em testar sistematicamente se n é divisível por qualquer número menor. Obviamente, só vale a pena testar fatores candidatos menores que n e em ordem de dois para cima, porque um n arbitrário tem mais chance de ser divisível por dois do que por três, e assim por diante.

Com esta ordenação, não há sentido em testar a divisibilidade por quatro se o número já tiver sido determinado como não divisível por dois, e assim por diante para três e qualquer múltiplo de três, etc.

Sendo assim, você consegue reduzir o esforço através da seleção de apenas números primos como fatores candidatos. Além disso, os fatores de teste não precisam ir além de \sqrt{n} porque, se n for divisível por algum número p, então n = p × q, e se q fosse menor que p, n teria sido detectado anteriormente como sendo divisível por q ou um fator primo de q.

A divisão por tentativa é um algoritmo trabalhoso, mas ainda assim é bom para números pequenos. Mais informações podem ser encontradas no link da Wikipédia acima.

URL copiado para a área de transferência
PLANETCALC, Fatoração de números inteiros. Divisão por tentativa

Comentários