Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos»

En el peor caso, la división por tentativa es un algoritmo costoso. Si se empieza en 2 y se va subiendo hasta la raíz cuadrada de ''n'', el algoritmo requiere

 

 

tentativas, donde <math>\pi(x)</math> es la función contador de primos, el número de primos menores que ''x''. En lo anterior no se ha tenido en cuenta la sobrecarga del test de primalidad para obtener los números primos candidatos a ser factores. Si se utiliza una variante sin el test de primalidad, sencillamente dividiendo por todo número impar menor que la raíz cuadrada de ''n'', ya sea primo o no, puede llegar a necesitarse alrededor de