Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos»
Contenido eliminado Contenido añadido
m a wikilibros |
m Correcciones menores, (WP:CEM) |
||
Línea 1:
{{a wikilibros}}
Un algoritmo, el
Sea N el
Sea Ps la lista de
Si N = 1, entonces el
Si no es 1:
Línea 19:
devolvemos Ps
Otro, similar pero que consiste en iterar hasta la
Si N = 1, entonces el
si N = 2, o N = 3: agregamos N a Ps, devolvemos Ps
i=2
Línea 35:
devolvemos Ps
Otro, que combina ambos, consiste en,
aumentar=2
Si N = 1, entonces el
si N = 2, o N = 3: agregamos N a Ps, devolvemos Ps
i=6
Línea 58:
(*): Un
Dem: Supongamos q sí puede haber
Sea dA = A - raizcuad(C)
Sea dB = B - raizcuad(C)
Si A y B son mayores que la
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
Por lo tanto, a lo sumo un factor puede ser mayor que la
(**) Los
Dem: Todo
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
| |||