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

De Wikilibros, la colección de libros de texto de contenido libre.
Saltar a: navegación, buscar

Un Algoritmo de factorización en números primos es un algoritmo para generar una lista de números primos; los más obvios son los siguientes.

Algoritmos comunes[editar]

Sea N el número compuesto 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 (*)

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.. (**)

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=6
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
mientras i < (raizcuad(n)+1) y N no sea 1
     si (i-1) 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
Agregamos N a Ps
devolvemos Ps

Notas[editar]

(*): Un número compuesto (llamemoslo C) no puede tener más de un factor primo que sea mayor a su raíz cuadrada

Dem: Supongamos que sí puede haber más de uno. Llamemos A y B a esos dos números primos. Llamemos P1, P2,.. Pn al resto de los números primos factores de C. Sea dA = A - raizcuad (C) Sea dB = B - raizcuad (C) Si A y B son mayores que la raíz cuadrada de C, entonces dA y dB serán positivos Entonces C = A*B*P1*P2... = (raizcuad (C)+dA)*(raizcuad (C)+dB)*P1*P2... = (raizcuad (C)*raizcuad (C) + dA*raizcuad (C) + dB*raizcuad (C) + dA*dB)*P1*P2... = (C + (dA+dB)*raizcuad (C) + dA*dB)*P1*P2... C*P1*P2.. + (dA+dB)*raizcuad (C)*P1*P2... + dA*dB*P1*P2... Obviamente, toda esa suma es mayor a C. Como partimos diciendo que C era igual a esa suma llegamos a una contradicción Por lo tanto, a lo sumo un factor puede ser mayor que la raíz cuadrada de C.

(**) Los números primos (mayores que 3) pueden expresarse de la siguiente forma: 6n±1 (siendo esta la más eficiente para soluciones iterativas de programación). Dem: Todo número natural puede expresarse como 6n±r, para algún n. R variara solo entre 0 y 5. 6n+0 es divisible por 6 SIEMPRE 6n+2 es divisible por 2 SIEMPRE 6n+3 es divisible por 3 SIEMPRE 6n+4 es divisible por 2 SIEMPRE 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, por lo tanto los números primos solo pueden encontrarse entre ellos).