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

 

 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  .NET (C#, VB.NET, ASP) (Moderador: kub0x)
| | | |-+  Descomponer en factores primos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Descomponer en factores primos  (Leído 7,499 veces)
juanlulete

Desconectado Desconectado

Mensajes: 31



Ver Perfil
Descomponer en factores primos
« en: 7 Agosto 2012, 00:56 am »

Hola, estoy intentando hacer un programa que descomponga un número en factores primos. Aunque lo conseguí, va muy lento y no lo hace perfecto.

Yo quería que me descompusiera el número de un textbox, le diera un botón y me pusiera la descomposición en un label de este modo:

textbox = 60
label = 2^2·3·5


Yo lo hice con un listbox porque no pude hacerlo de otra forma.
Este es mi código:

Código:
Public Class Form1
    Function isPrime(ByVal iNum As Decimal) As Boolean
        If (iNum < 2D) Then isPrime = False : Exit Function
        If (iNum < 4D) Then isPrime = True : Exit Function
        If (iNum Mod 2D = 0D) Then isPrime = False : Exit Function
        Dim iMax As Decimal : iMax = CInt(Math.Sqrt(CDbl(iNum)))
        Dim i As Decimal
        For i = 3D To iMax Step 2D
            If (iNum Mod i = 0D) Then isPrime = False : Exit Function
        Next i
        isPrime = True
    End Function
    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        ListBox1.Items.Clear()
        Dim a As Decimal = TextBox1.Text
        Dim j As Decimal
        Dim y As Decimal = 1D
        Dim z As Decimal
        For j = y To a
            If isPrime(j) Then
                For z = 1D To 1000D
                    If a Mod j ^ z = 0D Then ListBox1.Items.Add(j)
                Next
            End If
        Next j
    End Sub
End Class

Por favor, ¿pueden ayudarme a mejorar o mejor cambiar mi código?


En línea

Keyen Night


Desconectado Desconectado

Mensajes: 496


Nothing


Ver Perfil
Re: Descomponer en factores primos
« Respuesta #1 en: 7 Agosto 2012, 02:46 am »

Yo publico uno hace tiempo, mejore el código como por un año investigando bastante me obsesiono por un tiempo este tema :xD y en verdad va bastante rápido, claro hay números que por alguna razón matemática que aun no entiendo tardan demasiado, como por ejemplo 444445555511122222 o de ese tipo.

http://foro.elhacker.net/net/aporte_factorizacion_a_maxima_velocidad_actualizado_21102011-t321927.0.html

Normalmente siempre se recorren los números de 0 a N para hallar si un número es primo, eso serían N operaciones para cualquier N, si N es 100 mil millones entonces 100 mil millones serán las operaciones necesarias, a eso se debe la demora, sin embargo hay muchos métodos para acortar el tiempo, todos los que pude descubrir están aplicados en ese ejemplo, en tu código aplicas varios, como comenzar desde el 3, porque se sabe que el 2 es primo y el 1 no, avanzar de 2 en 2, porque sabemos que ningún primo es par, además de estos hay otros importantes como por ejemplo ningun número que se presume compuesto tiene más de un factor primo que supere su raíz por el simple hecho de que si F1 es una factor de N y es mayor que la raíz de N, N no puede tener 2 F1 de factores por que superarían a N, en otras palabras 2*F1>N, otros varios están explicados en esa publicación, nada más estos 3 disminuyen la cantidad de operaciones en

RaízCuadrada(N-3/2) en vez de N operaciones.

Como sea al menos hasta ahora no existe un método para factorizar en primos números grandes de una manera rápida, si alguien lo logra o lo matan o la seguridad informática debe volver a plantearse desde el principio :xD


« Última modificación: 7 Agosto 2012, 03:59 am 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...
juanlulete

Desconectado Desconectado

Mensajes: 31



Ver Perfil
Re: Descomponer en factores primos
« Respuesta #2 en: 7 Agosto 2012, 10:32 am »

Según lo he visto esta muy bien pero mi programa (Tengo Visual Basic 2010 Express) me indica que no está "regex" determinado.

Derive 6.0
Solo por si quieres mejorar tu programa y también mejorar otras cosas de matemáticas este programa es increíble. Tiene el mejor sistema de factorizar que haya visto nunca, resuelve todo lo que quieras de mates: sumatorios, productorios, ecuaciones, derivadas, integrales, funciones... y no solo eso resuelve con todos los dígitos que te de la gana (un millón de dígitos)

Aquí te paso el programa portable: (Copia todo lo que esté entre comillas)
"https://rapidshare.com/files/4288239705/Derive 6 - Evaluación.rar"

Si lograras descompilar el programa conseguirías muchas formulas y muy buenas.
Muchas gracias.
En línea

Keyen Night


Desconectado Desconectado

Mensajes: 496


Nothing


Ver Perfil
Re: Descomponer en factores primos
« Respuesta #3 en: 7 Agosto 2012, 15:11 pm »

La tomare mucho en cuenta si la llegase a necesitar, voy a descargarla ahora, Gracias por compartirla ;) hay una página WolframAlpha que también resuelve cualquier cosa, ofrece una API pero es paga :-\

Para usar Regex debes importar System.Text.RegularExpressions.

Mi código será siempre más lento, porque está en .Net y porque así como he agregado muchas cosas también faltaran otras, pero es solo practica lo que buscaba era entender la teoría de los problemas y las ventajas de factorizar un número que se supone compuesto en sus primos ;D.
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...
juanlulete

Desconectado Desconectado

Mensajes: 31



Ver Perfil
Re: Descomponer en factores primos
« Respuesta #4 en: 7 Agosto 2012, 16:42 pm »

Perdona pero no entiendo como utilizar lo de regex, ¿me lo podrías explicar?
En línea

Keyen Night


Desconectado Desconectado

Mensajes: 496


Nothing


Ver Perfil
Re: Descomponer en factores primos
« Respuesta #5 en: 7 Agosto 2012, 21:33 pm »

Regex es la clase en .Net que controla las expresiones regulares, que son un lenguaje de programación descriptivo para capturar patrones en textos, Es un tema muy extenso, por medio de instrucciones que describen patrones un motor de búsqueda realiza las operaciones necesarias para capturar en el texto que desees si el patrón existe o no.

http://es.wikipedia.org/wiki/Expresi%C3%B3n_regular
http://www.elguille.info/regexp/indice.aspx
http://msdn.microsoft.com/es-es/library/hs600312%28v=vs.80%29.aspx
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
AYUDA CON FACTORES PRIMOS
Ejercicios
danc98 6 8,223 Último mensaje 30 Noviembre 2005, 07:05 am
por ross_2408
Descomponer o factorizar un numero
Programación Visual Basic
Neobius 1 8,305 Último mensaje 20 Abril 2006, 19:14 pm
por Robokop
Puedo descomponer un video con vb.Net? « 1 2 3 »
.NET (C#, VB.NET, ASP)
Skeletron 20 16,054 Último mensaje 31 Agosto 2009, 00:37 am
por Skeletron
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
katas 2 9,839 Último mensaje 10 Marzo 2010, 01:50 am
por Novlucker
Descomponer numero en factores.. « 1 2 »
Programación C/C++
ThePinkPanther 13 9,385 Último mensaje 21 Febrero 2013, 01:12 am
por 85
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines