elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  .NET (C#, VB.NET, ASP) (Moderador: kub0x)
| | | |-+  [Aporte] Factorización Relativamente Rápida - Actualizado 18/08/2012 -
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Aporte] Factorización Relativamente Rápida - Actualizado 18/08/2012 -  (Leído 3,364 veces)
Keyen Night


Desconectado Desconectado

Mensajes: 496


Nothing


Ver Perfil
[Aporte] Factorización Relativamente Rápida - Actualizado 18/08/2012 -
« en: 15 Marzo 2011, 04:38 »

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

Quizás a alguien le sirva ;D 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
  1.    Function PSqrt(ByVal N As Decimal) As Decimal
  2.  
  3.        PSqrt = 1D
  4.  
  5.        Try
  6.  
  7.            Dim L As Decimal = Math.Floor(Math.Log(N))
  8.            Dim b As Decimal, c As Decimal, d As Decimal
  9.  
  10.  
  11.            For a As Decimal = L To 2D Step -1D
  12.                b = 1D / a
  13.                c = Math.Floor(N ^ b)
  14.                d = (c ^ a)
  15.                If d = N Then
  16.                    Return a
  17.                End If
  18.            Next
  19.  
  20.        Catch ex As OverflowException
  21.            Return 1D
  22.        End Try
  23.  
  24.    End Function
  25.  
  26.    Public Primes As Decimal() = New Decimal() {2D, 3D, 5D, 7D}
  27.    Public Function IsPrime(ByVal N As Decimal) As Boolean
  28.  
  29.        If (N Mod 2D = 0D) Then
  30.            Return False
  31.        End If
  32.  
  33.        If PSqrt(N) > 1D Then
  34.            Return False
  35.        End If
  36.  
  37.        If Primes.Contains(N) Then
  38.            Return True
  39.        End If
  40.  
  41.        IsPrime = True
  42.  
  43.        Dim R As Decimal = Math.Floor(Math.Sqrt(N))
  44.  
  45.        For Y As Decimal = 3D To R Step 2D
  46.            If (N Mod Y = 0D) And (Not Y = N) Then
  47.                Return False
  48.            End If
  49.        Next
  50.  
  51.    End Function
  52.  
  53.    Public Function Factorize(ByVal N As Decimal) As Dictionary(Of Decimal, Decimal)
  54.  
  55.        Factorize = New Dictionary(Of Decimal, Decimal)
  56.  
  57.        Dim PSqrtD As Decimal = PSqrt(N)
  58.  
  59.        If PSqrtD > 1D Then
  60.  
  61.            Dim SSqrt As Decimal = N ^ (1D / PSqrtD)
  62.  
  63.            If IsPrime(SSqrt) Then
  64.                Factorize.Add(SSqrt, PSqrtD)
  65.            Else
  66.                For Each x As KeyValuePair(Of Decimal, Decimal) In Factorize(SSqrt)
  67.                    Factorize.Add(x.Key, x.Value * PSqrtD)
  68.                Next
  69.            End If
  70.  
  71.        Else
  72.            If IsPrime(N) Then
  73.                Factorize.Add(N, 1D)
  74.            Else
  75.  
  76.                While N Mod 2D = 0D
  77.                    N /= 2D
  78.                    If Factorize.ContainsKey(2D) Then
  79.                        Factorize.Item(2D) += 1D
  80.                    Else
  81.                        Factorize.Add(2D, 1D)
  82.                    End If
  83.                End While
  84.  
  85.                If N > 1D Then
  86.                    Dim I As Decimal = 3D
  87. Again:
  88.                    Dim R As Decimal = Math.Floor(Math.Sqrt(N))
  89.  
  90.                    For X As Decimal = I To R Step 2D
  91.  
  92.                        If N Mod X = 0D Then
  93.  
  94.                            If Factorize.ContainsKey(X) Then
  95.                                Factorize.Item(X) += 1D
  96.                            Else
  97.                                Factorize.Add(X, 1D)
  98.                            End If
  99.  
  100.                            N /= X
  101.                            I = X
  102.  
  103.                            GoTo Again
  104.  
  105.                        End If
  106.  
  107.                    Next
  108.  
  109.                    If N > 1D Then
  110.                        If Factorize.ContainsKey(N) Then
  111.                            Factorize.Item(N) += 1D
  112.                        Else
  113.                            Factorize.Add(N, 1D)
  114.                        End If
  115.                    End If
  116.  
  117.                End If
  118.  
  119.            End If
  120.        End If
  121.  
  122.    End Function
  123.  

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 :xD

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:
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:
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:

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:
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.


« Última modificación: 18 Agosto 2012, 22:17 por Keyen Night » En línea

La Fé Mueve Montañas...
                                    ...De Dinero

La programación es más que un trabajo es más que un hobby es una pasión...
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Recopilatorio de herramientas CommandLine. (Actualizado el 30/03/2012) « 1 2 3 4 »
Scripting
SuperDraco 33 82,701 Último mensaje 20 Julio 2012, 01:37
por Eleкtro
Reto relativamente fácil « 1 2 »
Desafíos - Wargames
ace332 15 7,497 Último mensaje 23 Enero 2012, 19:46
por Caster
Ayuda con estos códigos (Actualizado 22/06/2012) « 1 2 »
Programación C/C++
LoLo2207 12 5,993 Último mensaje 22 Junio 2012, 15:57
por 0xDani
[Aporte] Libro muy actualizado
Programación C/C++
samuelhm 3 1,170 Último mensaje 7 Octubre 2014, 22:24
por flony
[APORTE] [BATCH] [ACTUALIZADO] Ver conexiones activas y puertos de escuha
Scripting
W17CH3R 6 424 Último mensaje 29 Marzo 2020, 15:40
por W17CH3R
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines