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.
Dado um número inteiro positivo , esse método consiste em verificar quais números inteiros menores do que são seus divisores.
Também pode ser utilizado para testar a primalidade de um número.
Algoritmo miniaturadaimagem|Algoritmo "Enumeração de divisores"
Em pseudocódigo, o algoritmo é dado portrialDivision(n) | para d ← 2 até √n | | enquanto(n % d = 0) | | | imprima d | | | n ← n / d | | fim_enquanto | fim_para | imprima n fim_trialDivisionO 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 .
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.
Ver também Teste de primalidade Fatoração de inteiros
Ligações externas Algoritmo em Java, C e em JavaScript
Categoria:Algoritmos Categoria:Matemática