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 m |
+reestructurar secciones |
||
Línea 1:
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.
== División por tentativa ==
Línea 25:
*<math>i \mid n</math> significa que ''i'' divide a ''n''.
Se pueden realizar mejoras sobre el algoritmo inicial para ganar algo en velocidad de cálculo utilizando los siguientes lemas.
Otro, similar pero que consiste en iterar hasta la raíz cuadrada de N [<small>[[Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos#Nota 1|Nota 1]]</small>]▼
<pre>▼
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▼
</pre>▼
Otro, que combina ambos, consiste en, además, ir incrementando i de a 2, 4, 2, 4..[<small>[[Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos#Nota 2|Nota 2]]</small>]▼
<pre>▼
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▼
</pre>▼
▲=== Nota 1 ===
Un número compuesto <math>n</math> no puede tener más de un factor primo que sea mayor a su raíz cuadrada.
Línea 93 ⟶ 53:
llegándose a una contradicción, por lo tanto, a lo sumo un factor puede ser mayor que <math>\sqrt{n}</math>.
===
Los números primos mayores que 3 cumplen con la siguiente condición:
Línea 112 ⟶ 72:
6''n''+1 y 6''n''-1 (o lo que es lo mismo a efectos del análisis, 6''n''+5), no proporcionan ninguna garantía de divisibilidad entre 6, por lo tanto los números primos solo pueden encontrarse entre ellos.
=== Pseudocódigo ===
▲
▲<pre>
▲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
▲</pre>
▲
▲<pre>
▲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
▲</pre>
[[Categoría:Libro:Implementación de algoritmos de teoría de números]]
|