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.)
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. Los más sencillos son los siguientes.
 
El algoritmo más sencillo y común para la factorización de enteros es la '''división por tentativa'''. Consiste en intentar dividir ''n'' entre todo número primo menor o igual a ''n''. Si se encuentra un número que es divisor de ''n'', en división entera, ese número es un factor de ''n''.
== Algoritmos comunes ==
 
Si ''n'' es el número a factorizar, el algoritmo devuelve una lista de números primos factores de ''n''. Si ''n'' = 1, entonces el número no es factorizable por ningún número primo (es 1).
<pre>
Sea N el número a factorizar
Sea Ps la lista de números primos actualmente obtenida
 
'''algoritmo''' <math>\text{factorización }(n)</math>
Si N = 1, entonces el número no es factorizable (es 1).
'''si''' <math>n = 1</math>
Si no es 1:
'''devolver''' <math>n</math>
'''sino'''
<math>i \leftarrow 2</math>
'''mientras''' <math>n \neq 1</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>
'''devolver''' <math>\{ \text{lista factores } n \}</math>
 
Con respecto a la la notación:
i = 2
 
mientras i < (N+1) y N no sea 1
*<math>i \in \mathbb{P}</math> significa que ''i'' pertenece al conjunto de los números primos
si i es primo, y N es divisible por i
*<math>i \mid n</math> significa que ''i'' divide a ''n''.
agregamos i a Ps
 
Hacemos N = N/i
== Mejoras ==
sino
incrementamos i
fin-si
fin-mientras
devolvemos Ps
</pre>
 
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>]