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.)
+contenido traído de https://es.wikipedia.org/w/index.php?title=Divisi%C3%B3n_por_tentativa&oldid=119496047 bajo licencias GFDL y CC BY-SA 3.0
Raulshc (discusión | contribs.)
+retoques
Línea 26:
 
== Mejoras ==
Se pueden realizar mejoras sobre el algoritmo dependiendo de sus variantes para ganar algo en velocidad de cálculo utilizando los siguientes lemas. Hay que tener en cuenta que también se necesita vefificar si un determinado número ''i'' es primo y eso supone una sobrecarga de hacer un test de primalidad, o utilizar una tabla precalculada de números primos hasta cierto ''n'', con lo que este paso para implementaciones sencillas se obvia, ganando en sencillez a costa de rendimiendo computacional. Siempre se puede ganar algo de rendimiendo descartando ciertos números utilizando el lema 2 descrito abajo.
Se pueden realizar mejoras sobre el algoritmo inicial para ganar algo en velocidad de cálculo utilizando los siguientes lemas.
 
=== Lema 1 ===
Línea 90:
'''devolver''' <math>\{ \text{lista factores } n \}</math>
 
CombinandoPara las variantes del algoritmo que no utilicen una tabla de primos precalculada o un test de primalidad para obtener los números primos candidatos a ser factores, se pueden combinar ambos lemas, de manera que se va incrementando ''i'' de aen 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>]
 
'''algoritmo''' <math>\text{factorización }(n)</math>
Línea 99:
<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>