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 algorítmo en un tiempo relativamente corto y este se va exponiendo (Aumentando) con los digitos que contenga N.

Tuve que postear el código sin acentos por que aparecen como hexadecimal

    Function PSqrt(ByVal N As Decimal) As Boolean
        Return (Math.Floor(Math.Sqrt(N)) ^ 2D) Mod Math.Sqrt(N) = 0D
    End Function
 
    Public Function IsPrime(ByVal N As Decimal) As Boolean
 
        IsPrime = True
 
        Dim P As Decimal() = New Decimal() {2D, 3D, 5D, 7D}
 
        If P.Contains(N) Or PrimesMatch(N) Then
            Return True
        End If
 
        Dim Y As Decimal = 0D
 
        If PSqrt(N) Then
            Return False
        End If
 
        Do While Y <= (P.Length - 1D)
 
            If (N Mod P(Y) = 0D) AndAlso Not N = P(Y) Then
                Return False
            End If
            Y += 1
 
        Loop
 
        Y = 11D
        Dim R As Decimal = Math.Floor(Math.Sqrt(N) + 1D)
 
        For Y = 11D To R Step 2D
            If N Mod Y = 0D Then
                Return False
            End If
        Next
 
    End Function
 
    Public Function PrimesMatch(ByVal N As Decimal) As Boolean
 
        PrimesMatch = New Regex("^(3{1,7})1$").IsMatch(N.ToString)
 
        PrimesMatch = PrimesMatch Or _
        (New Regex("^(9)1$").IsMatch(N.ToString) AndAlso New Regex("9").Matches(N.ToString).Count Mod 2 = 0)
 
    End Function
 
    Public Function Factorize(ByVal N As Decimal) As String
 
        Factorize = String.Empty
 
        Dim Facts As New Dictionary(Of Decimal, Decimal)
 
        If IsPrime(N) Then
            Facts.Add(N, 1)
            GoTo Leave
        Else
            If N < 49 Or New Regex("$(1|9)").IsMatch(N) Then
                Dim R2 As Decimal = Math.Sqrt(N)
                If (Math.Floor(R2) ^ 2D) Mod R2 = 0D Then
                    If IsPrime(R2) Then
                        Facts.Add(R2, 2)
                        GoTo Leave
                    End If
                End If
            End If
        End If
        Do While N Mod 2D = 0
            N /= 2D
            If Facts.ContainsKey(2D) Then
                Facts(2D) += 1D
            Else
                Facts.Add(2D, 1D)
            End If
        Loop
        If N = 1D Then
            GoTo Leave
        End If
Again:
        Dim R As Decimal = Math.Floor(Math.Sqrt(N) + 1D)
 
        For X As Decimal = 11D To R Step 2D
            If N Mod X = 0D Then
                If Facts.ContainsKey(X) Then
                    Facts(X) += 1D
                Else
                    Facts.Add(X, 1D)
                End If
                N /= X
                GoTo Again
            End If
        Next
 
        If N > 1D Then
            If Facts.ContainsKey(N) Then
                Facts(N) += 1D
            Else
                Facts.Add(N, 1D)
            End If
        End If
Leave:
        For Each x As KeyValuePair(Of Decimal, Decimal) In Facts
            If x.Value <> 0D Then
                Factorize += "(" & x.Key.ToString("0,0") & "^" & x.Value.ToString("0,0") & ")·"
            End If
        Next
 
        Return Factorize.Remove(Factorize.Length - 1, 1).Replace("^01)", ")").Replace("^0", "^").Replace("(0", "(")
 
    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 96Bits soportado) en menos de 1 segundo

Este algorítmo 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.

Todos los multiplos de los primos son compuestos y los números que cumplan los criterios de divisibilidad de los primos menores que la raíz de N son compuestos.

El criterio de divisibilidad del número primo 3, se basa en que si todos los dígitos de un número entero sumados son múltiplo de 3 entonces el entero es un divisible de 3. No es necesario comprobar si el número entero 3.965.124.231 es primo ya que la suma de sus dígitos es divisible entre 3 y esto lo hace automáticamente divisible de 3 y compuesto.

Todos los cuadrados perfectos que esten compuestos de 2 primos terminan en 1 o en 9 a exepción del 25 y el 49 porque son los estos son los únicos cuadrados perfectos que están compuestos por un primo de una sola cifra.

Todo número de la forma 3(1,7)1, entiendase que 3 se repite de 1 a 7 veces, es primo.


Un N de la siguiente forma, 9(2,)1, entiendase que 9 viene en pares, siempre que 9 se repita en pares y termine en 1, N es primo.


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