Divisão por tentativa

O algoritmo de divisão por tentativa (em inglês, Trial Division) é um método de força bruta para realizar a fatoração de números inteiros^[1].

Dado um número inteiro positivo $n$ , esse método consiste em verificar quais números inteiros menores do que $n$ são seus divisores^[1].

Também pode ser utilizado para testar a primalidade de um número.

Algoritmo

Em pseudocódigo, o algoritmo é dado por^[1]

trialDivision(n)
|   para d ← 2 até √n
|   |   enquanto(n % d = 0)
|   |   |   imprima d
|   |   |   n ← n / d
|   |   fim_enquanto
|   fim_para
|   imprima n
fim_trialDivision

O algoritmo anterior irá imprimir os fatores primos da entrada $n$ , incluindo repetições. É suficiente verificar os fatores de $2$ (primeiro primo) até ${\sqrt {n}}$ , pois se um número não é primo, então ele deve ter um divisor que é no máximo ${\sqrt {n}}$ ^[2].

Complexidade Assintótica

Uma vez que o algoritmo de divisão por tentativa é um algoritmo de força bruta, a sua complexidade é exponencial, portanto ele é inviável para fatorar números grandes^[1].

Ver também

Referências

↑ ^a ^b ^c ^d Felipe, Henrique (25 de abril de 2018). «Fatoração de números inteiros via divisão por tentativa». Blog Cyberini. Consultado em 26 de abril de 2018
↑ Amit, Alon (23 de junho de 2016). «What is trial division method for factorization? How is it implemented? Is it fit for large numbers?» (em inglês). Quora. Consultado em 26 de abril de 2018

Ligações externas

Algoritmo em Java, C e em JavaScript

[:0-1] Felipe, Henrique (25 de abril de 2018). «Fatoração de números inteiros via divisão por tentativa». Blog Cyberini. Consultado em 26 de abril de 2018

[2] Amit, Alon (23 de junho de 2016). «What is trial division method for factorization? How is it implemented? Is it fit for large numbers?» (em inglês). Quora. Consultado em 26 de abril de 2018

[1]

[2]