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 |
→Algoritmos comunes: +formato |
||
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''.
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).
'''algoritmo''' <math>\text{factorización }(n)</math>
'''si''' <math>n = 1</math>
'''devolver''' <math>n</math>
<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:
*<math>i \in \mathbb{P}</math> significa que ''i'' pertenece al conjunto de los números primos
*<math>i \mid n</math> significa que ''i'' divide a ''n''.
== Mejoras ==
▲ sino
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>]
|