Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos

Un Algoritmo de factorización en números primos es un algoritmo que dado un número natural mayor que 1 genera la lista de números primos que componen la factorización del mismo; los más obvios son los siguientes.

Algoritmos comunesEditar

Sea N el número a factorizar
Sea Ps la lista de números primos actualmente obtenida

Si N = 1, entonces el número no es factorizable (es 1).
Si no es 1:

i = 2
mientras i < (N+1) y N no sea 1
     si i es primo, y N es divisible por i
        agregamos i a Ps
        Hacemos N = N/i
     sino
        incrementamos i
     fin-si
fin-mientras
devolvemos Ps

Otro, similar pero que consiste en iterar hasta la raíz cuadrada de N [Nota 1]

Si N = 1, entonces el número no es factorizable.
si N = 2, o N = 3: agregamos N a Ps, devolvemos Ps
i=2
mientras i < (raizcuad(n)+1) y N no sea 1
     si i es primo, y N es divisible por i
        agregamos i a Ps
        Hacemos N = N/i
     sino
        incrementamos i
     fin-si
fin-mientras
Agregamos N a Ps
devolvemos Ps

Otro, que combina ambos, consiste en, además, ir incrementando i de a 2, 4, 2, 4..[Nota 2]

aumentar=2
Si N = 1, entonces el número no es factorizable.
si N = 2, o N = 3: agregamos N a Ps, devolvemos Ps
i=5
si N es divisible por 2, agregar 2 a Ps, hacer N = N/2
si N es divisible por 3, agregar 3 a Ps, hacer N = N/3
limite=raizcuad(N)+1
mientras i < limite y N no sea 1
     si i es primo, y N es divisible por i
        agregamos i a Ps
        Hacemos N = N/i
     sino
        si aumentar=2 entonces aumentar=4 sino aumentar=2 fin-si
        i = i + aumentar
     fin-si
fin-mientras
devolvemos Ps

NotasEditar

Nota 1Editar

Un número compuesto   no puede tener más de un factor primo que sea mayor a su raíz cuadrada.

Demostración: Supongamos que sí puede haber más de uno, por ejemplo dos. Llamemos   y   a esos dos números primos y  ,  ,..   al resto de los números primos factores de  . Sean:

 
 

Si   y   ambos son mayores que  , entonces   y   serán positivos. Desarrollando el producto se tiene que:

 

Como   y  , el desarrollo  , por lo que el producto inicial debe ser mayor que  :

 

llegándose a una contradicción, por lo tanto, a lo sumo un factor puede ser mayor que  .

Nota 2Editar

Los números primos mayores que 3 cumplen con la siguiente condición:

 

ó

 

siendo esta la más eficiente para soluciones iterativas de programación.

Demostración:

Todo número natural puede expresarse como 6n±r, para algún n, r variará solo entre 0 y 5.

6n+0 es divisible por 6
6n+2 es divisible por 2
6n+3 es divisible por 3
6n+4 es divisible por 2

6n+1 y 6n-1 (o lo que es lo mismo a efectos del análisis, 6n+5), no proporcionan ninguna garantía de divisibilidad entre 6, por lo tanto los números primos solo pueden encontrarse entre ellos.