Algoritmo de factorización en números primos

De Wikipedia, la enciclopedia libre

Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.

Un algoritmo, el más obvio, para obtener números primos, es

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 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

(*): 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 q 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 analisis, 6n+5), no proporcionan ninguna garantía de divisibilidad, por lo tanto los números primos solo pueden encontrarse entre ellos).