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
Raulshc (discusión | contribs.)
m m
Raulshc (discusión | contribs.)
+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. LosEl más sencillossencillo sonde losentender siguientese implementar en una computadora es el algoritmo de división por tentativa y sus variantes.
 
== División por tentativa ==
Línea 25:
*<math>i \mid n</math> significa que ''i'' divide a ''n''.
 
=== Mejoras ===
Se pueden realizar mejoras sobre el algoritmo inicial para ganar algo en velocidad de cálculo utilizando los siguientes lemas.
 
=== NotaLema 1 ===
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>
 
== Notas ==
=== 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>.
 
=== NotaLema 2 ===
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 ===
Otro,Aplicando similar pero que consiste enla iterariteración hasta la raíz cuadrada de N''n'' [<small>[[Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos#NotaLema 1|NotaLema 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 combinaCombinando ambos lemas, consistede en,manera además,que irse va incrementando ''i'' de a 2, 4, 2, 4.. a partir de 5 [<small>[[Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos#NotaLema 2|NotaLema 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>
 
 
 
 
[[Categoría:Libro:Implementación de algoritmos de teoría de números]]