División por tentativa

La división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender.

Descripción

Dado un entero compuesto n (a lo largo de este artículo, n será «el entero a factorizar»), la división por tentativa consiste en intentar dividir n entre todo número primo menor o igual a √n. Si se encuentra un número que es divisor de n, en división entera, ese número es un factor de n.

Es posible determinar un límite para los factores primos. Supóngase que es el i-ésimo primo, de modo que , , etc. Entonces el valor del último número primo probado como un posible factor de n sería puesto que ; si fuese igual querría decir que es un factor. Aunque todo esto está muy bien, normalmente el inconveniente de inspeccionar un n concreto para determinar el valor correcto de i es más costoso que simplemente probar con el único candidato innecesario que estaría incluido en la tentativa con todos los tales que . Puede la raíz cuadrada de n ser entera, entonces es un factor y n es un cuadrado perfecto, pero no es esta una manera buena de encontrarlos.

La división por tentativa garantiza encontrar un factor de n, puesto que comprueba todos los factores primos posibles de n. Por tanto, si el algoritmo no encuentra ningún factor, es una prueba de que n es primo.

Other Languages