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.)
+reestructurar secciones
Raulshc (discusión | contribs.)
+formato
Línea 74:
 
=== Pseudocódigo ===
Aplicando la iteración 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#Lema 1|Lemalema 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>
 
Combinando ambos lemas, de manera que se 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#Lema 2|Lema 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>
 
'''algoritmo''' <math>\text{factorización }(n)</math>
'''si''' <math>n = 1</math> '''ó''' <math>n = 2</math> '''ó''' <math>n = 3</math>
'''devolver''' <math>n</math>
'''sino'''
<math>i \leftarrow 2</math>
'''mientras''' <math>i \leq \lfloor \sqrt{n} \rfloor</math> '''hacer'''
'''si''' <math>i \in \mathbb{P}</math> '''y''' <math>i \mid n</math>
<math>\{ \text{lista factores } n \} \leftarrow i</math>
<math>n \leftarrow n/i</math>
'''sino'''
<math>i \leftarrow i+1</math>
<math>\{ \text{lista factores } n \} \leftarrow n</math>
'''devolver''' <math>\{ \text{lista factores } n \}</math>
 
Combinando ambos lemas, de manera que se 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#Lema 2|Lemalema 2]]</small>]
 
'''algoritmo''' <math>\text{factorización }(n)</math>
'''si''' <math>n = 1</math> '''ó''' <math>n = 2</math> '''ó''' <math>n = 3</math>
'''devolver''' <math>n</math>
'''sino'''
<math>i \leftarrow 2</math>
<math>m \leftarrow 0</math>
'''mientras''' <math>i \leq \lfloor \sqrt{n} \rfloor</math> '''hacer'''
'''si''' <math>i \in \mathbb{P}</math> '''y''' <math>i \mid n</math>
<math>\{ \text{lista factores } n \} \leftarrow i</math>
<math>n \leftarrow n/i</math>
'''sino si''' <math>i < 5</math>
<math>i \leftarrow i+1</math>
'''sino'''
<math>i \leftarrow i+(2 \cdot (-1)^m \bmod 6)</math>
<math>m \leftarrow (m+1) \bmod 2</math>
<math>\{ \text{lista factores } n \} \leftarrow n</math>
'''devolver''' <math>\{ \text{lista factores } n \}</math>
 
[[Categoría:Libro:Implementación de algoritmos de teoría de números]]