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 ${\displaystyle n}$, esse método consiste em verificar quais números inteiros menores do que ${\displaystyle n}$ são seus divisores.^[1]

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

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 ${\displaystyle n}$, incluindo repetições. É suficiente verificar os fatores de ${\displaystyle 2}$ (primeiro primo) até ${\displaystyle {\sqrt {n}}}$, pois se um número não é primo, então ele deve ter um divisor que é no máximo ${\displaystyle {\sqrt {n}}}$.^[2]

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]

• Teste de primalidade
• Fatoração de inteiros

Referências

• Algoritmo em Java, C e em JavaScript