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.

    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.

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.


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.

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:


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.