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

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

Esta página existe graças aos esforços das seguintes pessoas:

Timur

Timur

Julia Gomes

Criado: 2021-07-04 03:35:48, Ultima atualização: 2021-11-17 07:52:00

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