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 , esse método consiste em verificar quais números inteiros menores do que 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
, incluindo repetições. É suficiente verificar os fatores de
(primeiro primo) até
, pois se um número não é primo, então ele deve ter um divisor que é no máximo
.[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]