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.
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[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..[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=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).
