[Aporte] Factorización Relativamente Rápida - Actualizado 18/08/2012 -

[Keyen Night]

Cada vez más rápido y con más soporte para números más grandes

Quizás a alguien le sirva factoriza números enteros incluso mayores que Decimal.MaxValue en menos de una décima de segundo para la mayoría hay números que se factorizan más lento que otros pero es un un porcentaje muy bajo. La solución es exponencial en tiempo polinomial, quiere decir que todo número N que sea Natural puede ser factorizado por este algoritmo en un tiempo relativamente corto y este se va exponiendo (Aumentando) con los dígitos que contenga N.

Código (vb.net) [Seleccionar] Expandir

   Function PSqrt(ByVal N As Decimal) As Decimal

       PSqrt = 1D

       Try

           Dim L As Decimal = Math.Floor(Math.Log(N))
           Dim b As Decimal, c As Decimal, d As Decimal


           For a As Decimal = L To 2D Step -1D
               b = 1D / a
               c = Math.Floor(N ^ b)
               d = (c ^ a)
               If d = N Then
                   Return a
               End If
           Next

       Catch ex As OverflowException
           Return 1D
       End Try

   End Function

   Public Primes As Decimal() = New Decimal() {2D, 3D, 5D, 7D}
   Public Function IsPrime(ByVal N As Decimal) As Boolean

       If (N Mod 2D = 0D) Then
           Return False
       End If

       If PSqrt(N) > 1D Then
           Return False
       End If

       If Primes.Contains(N) Then
           Return True
       End If

       IsPrime = True

       Dim R As Decimal = Math.Floor(Math.Sqrt(N))

       For Y As Decimal = 3D To R Step 2D
           If (N Mod Y = 0D) And (Not Y = N) Then
               Return False
           End If
       Next

   End Function

   Public Function Factorize(ByVal N As Decimal) As Dictionary(Of Decimal, Decimal)

       Factorize = New Dictionary(Of Decimal, Decimal)

       Dim PSqrtD As Decimal = PSqrt(N)

       If PSqrtD > 1D Then

           Dim SSqrt As Decimal = N ^ (1D / PSqrtD)

           If IsPrime(SSqrt) Then
               Factorize.Add(SSqrt, PSqrtD)
           Else
               For Each x As KeyValuePair(Of Decimal, Decimal) In Factorize(SSqrt)
                   Factorize.Add(x.Key, x.Value * PSqrtD)
               Next
           End If

       Else
           If IsPrime(N) Then
               Factorize.Add(N, 1D)
           Else

               While N Mod 2D = 0D
                   N /= 2D
                   If Factorize.ContainsKey(2D) Then
                       Factorize.Item(2D) += 1D
                   Else
                       Factorize.Add(2D, 1D)
                   End If
               End While

               If N > 1D Then
                   Dim I As Decimal = 3D
Again:
                   Dim R As Decimal = Math.Floor(Math.Sqrt(N))

                   For X As Decimal = I To R Step 2D

                       If N Mod X = 0D Then

                           If Factorize.ContainsKey(X) Then
                               Factorize.Item(X) += 1D
                           Else
                               Factorize.Add(X, 1D)
                           End If

                           N /= X
                           I = X

                           GoTo Again

                       End If

                   Next

                   If N > 1D Then
                       If Factorize.ContainsKey(N) Then
                           Factorize.Item(N) += 1D
                       Else
                           Factorize.Add(N, 1D)
                       End If
                   End If

               End If

           End If
       End If

   End Function


Bueno, y algunos se preguntarán como es posible que factorize el número 79.228.162.514.264.337.593.543.950.335 (Decimal más grande de 96 Bits soportado) en menos de 1 segundo

Este algoritmo no se enfrasca en lo que hacen los demás, realizar ese For interminable desde 0 hasta N comprobando la divisibilidad y luego la primadilidad del número divisible, tardarías millones de años literalmente en factorizar el número anterior. Sino que se basa en leyes y propiedades básicas de los primos, por ejemplo:

Un N no puede tener más de un factor que supere su raíz, así que no encontraremos ningún factor que se repita 2 veces al pasar la raíz, de igual forma el primer divisible de N siempre es primo y se encuentra en el rango de 1 a raíz de N.

Código [Seleccionar] Expandir


Ejemplo:

Los factores del número 123.456.789, su raíz redondeada es 11.111, están entre 2 y 11.111 y no pueden haber factores que se repitan más grandes que dicha raíz.


Debido a que los primos forman a los compuestos, siempre estará primero un primo que un compuesto en la recta numérica ya que el compuesto siguiente al primo esta conformado por un primo anterior.

Código [Seleccionar] Expandir


Desde el 2 a todos los compuestos le antecede un primo e igualmente están compuestos por el primo que les antecedió

2, 3, 4, 5, 6, 7, 8, 9, ...

Siendo el 2, 3, 5 y 7 primos en esta recta, de manera que para el número 1.023, el primer
divisible que aparece es el 3 y este es primo, Otros divisibles de 1.023 quizás sean compuestos de
3 y debido a esto es imposible que se escape un compuesto en la lista porque siempre estará
primero un primo. Y así con cualquier número entero N que sea compuesto.


Al dividir el primer factor encontrado de N generará un compuesto y los factores de este serán
factores de N, aplicando este procedimiento hasta que se generé un número primo, se podrán
obtener todos los factores de N y cuantas veces estos se repiten. Dicho procedimiento no
consume casi tiempo ya que cada vez el valor generado se va haciendo más pequeño y el primer
factor se encontrará antes de la raíz así que el procedimiento se verá cortado antes de finalizar en
el caso de que N sea compuesto, no es necesario comprobar los números de 2 a raíz de N, se
puede disminuir el tiempo de operación a la mitad si se ignoran los números pares que son
compuestos de 2 y por lo tanto no pueden ser factores de N.

Código [Seleccionar] Expandir



En el mismo caso del 1.023 el primer divisible es 3 y el resultado es 341, aplicamos el método
nuevamente y el primer divisible es 11 que también es primo eso da como resultado 31 que es un
primo y la operación no se puede continuar, esto arroja que los factores de 1.023 son 3, 11
y 31. Si comprobamos 3 * 11 * 31 = 1.023.



Un número N es cuadrado perfecto de indice I, cuando existe un número X en el rango [2D, Log(N)], que satisfaga la siguiente condición:

Código [Seleccionar] Expandir


N ^ (1/X) 'Es Entero'
N ^ (1/X) ^ X = N


Lo que quiere decir que si N ^ (1/X) es primo, entonces N es compuesto por I factores de dicho primo. Si en cambio N ^ (1/X) es compuesto, entonces los factores de N serán I-ésimas veces los factores primos de dicho compuesto.

El restante de N después de aplicar el algoritmo, de dividir N por el primer factor que se encuentre hasta que no se encuentre ningún otro, es primo.