Anuncio

Colapsar
No hay ningún anuncio todavía.

Software para crear números primos

Colapsar
X
 
  • Filtro
  • Hora
  • Mostrar
Borrar todo
nuevos mensajes

  • Maq77
    ha respondido
    Re: Software para crear números primos

    Escrito por Maq77 Ver mensaje
    Por aca otra función que me da los números primos por debajo del 1.000.000 en menos de 10 segundos.

    Código:
    '****************************************************************************************
    '* PROYECTO      : NUMEROS PRIMOS
    '* CONTENIDO     : FUNCIONES GLOBALES
    '* VERSION       : 1.1
    '* AUTORES       : MIGUEL QUINTEIRO PIÑERO
    '* INICIO        : 26 DE JULIO DE 2017
    '* ACTUALIZACION : 26 DE JULIO DE 2017
    '****************************************************************************************
    
    Module Funciones
        ' Función para determinar si un número es o no primo
        Public Function Primo(ByVal pN As Long) As Boolean
            Dim i As Long
            Primo = True
            If (pN = 1) Or ((pN / 2) = Int(pN / 2)) Then
                Primo = False
            Else
                For i = 3 To Math.Sqrt(pN) Step 2
                    If (pN / i) = Int(pN / i) Then
                        Primo = False
                        i = pN
                    End If
                Next
            End If
        End Function
    End Module
    Acá tengo un error, estoy dejando por fuera al número 2, no lo está contando como un primo, el código corregido sería:

    Código:
    Module Funciones
        ' Función para determinar si un número es o no primo
        Public Function Primo(ByVal pN As Long) As Boolean
            Dim i As ULong
            Primo = True
            ' Modificacion
            ' **********************************************************
            If ((pN = 1) Or ((pN / 2) = Int(pN / 2))) And (pN <> 2) Then
                ' ******************************************************
                Primo = False
            Else
                For i = 3 To Math.Sqrt(pN) Step 2
                    If (pN / i) = Int(pN / i) Then
                        Primo = False
                        i = pN
                    End If
                Next
            End If
        End Function
    End Module
    Disculpen el error, pero me estaba dando un primo de menos en todos los conteos.

    Saludos.

    Dejar un comentario:


  • Maq77
    ha respondido
    Re: Software para crear números primos

    En una computadora de 64 bits con Visual Basic 2010 en adelante puedes utilizar las variables del tipo ULong

    "ULong contiene enteros de 64 bits sin signo (8 bytes) que van de un valor de 0 a 18.446.744.073.709.551.615 (más de 1,84 veces 10 ^ 19)."

    Creo que dividir la tarea en dos formas de trabajo te sería de utilidad, hasta este valor al menos trabajar el programa como números, y cambiar a una función en string solo cuando los valores superen esta cifra.

    También se podría revisar la función que utilizas para trabajar los string, tal vez allí también se pueda encontrar alguna optimización posible.

    Dejar un comentario:


  • Richard R Richard
    ha respondido
    Re: Software para crear números primos

    Escrito por Maq77 Ver mensaje
    Deberías revisar cual parte de tu programa es la que se está llevando todo el tiempo del cálculo.
    Sospecho que es por tratar números como strings para que no haya problemas con las variables, por pretender que con números grandes funcione, es muy lento al principio.

    Estoy cambiando el método, pero no quiero usar variables variant, desconozco si en efecto puede reconocer y como se hace a tener todo el numero no solo las cifras significativas... por eso manejo strings

    No se si se entiende lo que busco, un programa que permita hallar números primos de largas cadenas de cifras, el tema pasa entonces por donde almacenas tanta cantidad de números tan grandes, la memoria en GBytes de un PC se vuelve pequeña 55MB ocupan mas de 5M de números primos llegar a 1e 16 requiere varios teras... no tiene mucho sentido ni utilidad almacenarlos, mas que para calcular los gaps

    En tu código de ejemplo la función Int fallara luego de 32767 +1 y la long fallara cuando cargues PN [FONT=Consolas]2147483647 +1 o mejor +2 [/FONT]lo que pretendo es que ese tipo de límites no se de en mi software... pero hacerlo a mi modo ralentiza.
    Última edición por Richard R Richard; 05/11/2018, 01:41:19.

    Dejar un comentario:


  • Maq77
    ha respondido
    Re: Software para crear números primos

    Escrito por Richard R Richard Ver mensaje
    Mi pc tardó 36 hs hasta llegar a 100000000 números naturales, y hallar 5765021 primos , pero cualquier estudio decente arranca de 1 e16 para arriba, lo que me llevara estimo unos 300000 años o mas generar esos primos, mejor foja cero y buscar otro algoritmo.
    Richard esto es demasiado tiempo, pero sospecho que hay algo mal en tu algoritmo, programa o PC, porque yo obtuve ese mismo resultado en menos de media hora.

    Deberías revisar cual parte de tu programa es la que se está llevando todo el tiempo del cálculo.

    Saludos
    Última edición por Maq77; 04/11/2018, 22:17:57. Motivo: Corregir error ortográfico

    Dejar un comentario:


  • u_maligno
    ha respondido
    Re: Software para crear números primos

    Gracias Richard, yo por eso te decía de comprobar alguna diferente (más acotada), porque para las más conocidas ya se ha comprobado para números bastante grandes. Y bueno, algunas incluso son teoremas así que no hace falta (aunque yo personalmente no soy capaz de seguir la demostración, mates demasiado chungas para mi xd)

    Gracias de todos modos por la molestia, igual con el algoritmo de Maq77 mejoraba la cosa..

    Saludos.

    Dejar un comentario:


  • Richard R Richard
    ha respondido
    Re: Software para crear números primos

    Escrito por u_maligno Ver mensaje
    Hola Richard, podrías comprobar una cosa? La conjetura de Legendre afirma que existe al menos un primo entre n^2 y (n+1)^2 (entre cuadrados consecutivos vaya),
    tambien probe
    Escrito por Richard R Richard Ver mensaje
    Bueno , también hay otras conjeturas con que siempre hay un primo entre n y 2n inclusive, y entre 2n y 3n...algo mas difícil que no hay gaps de tamaño n hasta mas allá de n^2...

    Se les ocurre alguna mas, para validar/ refutar empíricamente?
    hasta el 1e8 encontré.... nada como era de esperar Saludos

    Mi pc tardó 36 hs hasta llegar a 100000000 números naturales, y hallar 5765021 primos , pero cualquier estudio decente arranca de 1 e16 para arriba, lo que me llevara estimo unos 300000 años o mas generar esos primos, mejor foja cero y buscar otro algoritmo.

    Dejar un comentario:


  • Maq77
    ha respondido
    Re: Software para crear números primos

    Por aca otra función que me da los números primos por debajo del 1.000.000 en menos de 10 segundos.

    Código:
    '****************************************************************************************
    '* PROYECTO      : NUMEROS PRIMOS
    '* CONTENIDO     : FUNCIONES GLOBALES
    '* VERSION       : 1.1
    '* AUTORES       : MIGUEL QUINTEIRO PIÑERO
    '* INICIO        : 26 DE JULIO DE 2017
    '* ACTUALIZACION : 26 DE JULIO DE 2017
    '****************************************************************************************
    
    Module Funciones
        ' Función para determinar si un número es o no primo
        Public Function Primo(ByVal pN As Long) As Boolean
            Dim i As Long
            Primo = True
            If (pN = 1) Or ((pN / 2) = Int(pN / 2)) Then
                Primo = False
            Else
                For i = 3 To Math.Sqrt(pN) Step 2
                    If (pN / i) = Int(pN / i) Then
                        Primo = False
                        i = pN
                    End If
                Next
            End If
        End Function
    End Module
    Trabaja de manera ligeramente diferente a la antes vista en el sentido que no almacena los primos anteriores para luego utilizarlos, simplemente asigna como primo a cualquier número a comprobar, luego verifica que el número sea 1 o un multiplo exacto del 2, en cuyo caso dice que no es primo y termina, y si no verifica si tiene algun factor exacto entre los números impares inferiores a su raiz cuadrada, si lo tiene cambia a que el numero no es primo. Si logra terminar todos los ciclos sin encontrar factores exactos termina quedándose como un número primo.

    Encuentra y señala a los 78.497 números primos por debajo del 1.000.000 en 5 segundos más o menos

    Haz clic en la imagen para ampliar

Nombre:	NPrimos1000000.jpg
Vitas:	1
Tamaño:	61,1 KB
ID:	304284

    Saludos.

    Dejar un comentario:


  • Jaime Rudas
    ha respondido
    Re: Software para crear números primos

    Escrito por Alriga Ver mensaje
    Este teorema fue demostrado por Chebyshev en 1950.
    En realidad, fue demostrado en 1852: Chebyshov murió en 1894.

    Dejar un comentario:


  • u_maligno
    ha respondido
    Re: Software para crear números primos

    Gracias Alriga, justo hace un rato volví a editar, en el mismo enlace que puse lo pone pero me confundí por el título. Voy a leer un poco más sobre el tema a ver si me aclaro, porque ahora mismo no entiendo que eso no demuestre también la conjetura de Legendre (algo se me debe de estar escapando )

    Salu2

    - - - Actualizado - - -

    Vale, ya lo entiendo. En realidad n^2 - (n+1)^2 es siempre menor que n^2 - 2n^2 para n > 2. xD
    Última edición por u_maligno; 26/10/2018, 15:00:26.

    Dejar un comentario:


  • Alriga
    ha respondido
    Re: Software para crear números primos

    Escrito por u_maligno Ver mensaje
    Al parecer eso ya no es conjetura sino postulado https://es.wikipedia.org/wiki/Postulado_de_Bertrand ...
    No, no es un postulado, se le conoce con el nombre incorrecto de "postulado de Bertrand" por motivos históricos: Bertrand lo "postuló" en 1845, (hoy diríamos con más propiedad "lo conjeturó") y no fue capaz de demostrarlo. Su nombre matemáticamente correcto es "Teorema de Bertrand–Chebyshev" como yo lo nombré aquí: http://forum.lawebdefisica.com/threa...900#post185900

    Este teorema fue demostrado por Chebyshev en 1850.

    Saludos.
    Última edición por Alriga; 26/10/2018, 15:50:40. Motivo: Lapsus numérico

    Dejar un comentario:


  • Maq77
    ha respondido
    Re: Software para crear números primos

    Escrito por Richard R Richard Ver mensaje
    He corregido el codigo, en base a las premisas de maq77, logre los primos hasta el millon en 5 minutos..... una hora 55 minutos menos que antes

    ....

    Coloque limite los cálculos en vez de debajo de la raíz de Num , como en este soft el numero es un string de texto , lo hice limitando la longitud de los numeros que estan por arriba de la raiz de Num y cargando siempre impares en el algoritmo de detección

    ¡Qué bueno haberte servido para algo!

    Por acá dos enlaces en los que se tienen ejemplos de códigos en diversos lenguajes de programación para el estudio y determinación de los numeros primos.

    La parte del código en VBA es aplicable perfectamente en VB6

    https://rosettacode.org/wiki/Category:Prime_Numbers

    https://rosettacode.org/wiki/Primali...l_division#VBA


    También existen en línea bibliotecas de archivos con una gran cantidad de números primos, por ejemplo en:

    https://numerosprimos.org/numeros-pr...e-1-a-1000000/

    Ya podemos encontrar el listado de los números primos menores al 1.000.000


    Es por eso que yo había enfocado el esfuerzo en encontrar un "Mejor Algoritmo" y no en un listado como tal, que ya hay muchos, es más encarar el asunto desde el punto de vista de "P Vs NP", y buscar un algoritmo que realmente baje el grado de complejidad de la tarea de determinar cual número es primo y cual no lo es.

    Al final, todos los métodos y algoritmos terminan siendo solo una Criba, algunas más sofisticadas y eficientes que otras, la idea es inventar o descubrir cual es la mejor de todas, la que consume menos recursos computacionales y de tiempo.

    Dejar un comentario:


  • u_maligno
    ha respondido
    Re: Software para crear números primos

    Al parecer eso ya no es conjetura sino postulado https://es.wikipedia.org/wiki/Postulado_de_Bertrand Pero ahora me haces dudar, no acabo de entender por qué la de Legendre (o incluso la que puse yo) sigue siendo conjetura si crece más rápidamente.. xD

    Supongo que lo interesante sería encontrar alguna que se pudiera refutar, y no las que ya se han comprobado hasta números gigantescos jeje

    Salu2

    Perdón, me lié entre postulado y teorema. Ni caso a lo primero que dije

    Segundo perdón, en realidad no me lié, releyendo veo que al final sí es teorema. Así que ya no entiendo nada xD
    Última edición por u_maligno; 26/10/2018, 14:07:41.

    Dejar un comentario:


  • Richard R Richard
    ha respondido
    Re: Software para crear números primos

    Bueno , también hay otras conjeturas con que siempre hay un primo entre n y 2n inclusive, y entre 2n y 3n...algo mas difícil que no hay gaps de tamaño n hasta mas allá de n^2...

    Se les ocurre alguna mas, para validar/ refutar empíricamente?

    Lo que tengo que hacer esjar correr el programa al menos hasta el100000000 o 1000000000 para tener números y tiempos de pc dentro de lo posibles normales, cuando tenga la tabla de primos se las comparto
    Última edición por Richard R Richard; 26/10/2018, 10:51:20.

    Dejar un comentario:


  • u_maligno
    ha respondido
    Re: Software para crear números primos

    Hola Richard, podrías comprobar una cosa? La conjetura de Legendre afirma que existe al menos un primo entre n^2 y (n+1)^2 (entre cuadrados consecutivos vaya), no te voy a pedir que compruebes esto ya que si aún es conjetura será porque nadie a conseguido encontrar un contraejemplo pero, podrías ver si se cumple también entre (x^2 + x)/2 y ((x+1)^2 + (x+1))/2 (entre sumatoria de naturales en vez de cuadrados)?

    Si no es mucho lío eh, es para darle algo de vidilla al programa (vale, y por curiosidad morbosa )

    Salu2

    Dejar un comentario:


  • Richard R Richard
    ha respondido
    Re: Software para crear números primos

    He corregido el codigo, en base a las premisas de maq77, logre los primos hasta el millon en 5 minutos..... una hora 55 minutos menos que antes

    Código:
    Public Num As StringPublic Cant As Single
    Public Ban As Integer
    
    
    Private Sub Command1_Click()
    Dim Gap(100001) As Double
    Open Text1.Text For Input As #4
    ant = "1"
    While Not EOF(4)
        Line Input #4, primo
        Num = primo
        gaps = primo - ant
       Gap(CSng(gaps)) = Gap(CSng(gaps)) + 1
       ant = primo
    Wend
    Close #4
    For x = 2 To 100000 Step 2
    If Gap(x) > 0 Then
    ngap = x
    End If
    If Maxgap <= Gap(x) Then
    Maxgap = Gap(x)
    End If
    Next
    
    
    inix = 10000
    iniy = 10000
    gapant = Gap(2)
    A = 4
    Do Until A > ngap
    Line (inix + (A - 2) * 10000 / ngap, iniy - 10000 * gapant / Maxgap)-(inix + A * 10000 / ngap, iniy - 10000 * Gap(A) / Maxgap), &H0&
    Line (inix + (A - 2) * 10000 / ngap, iniy - 10000 * gapant * (A - 2) / 100000)-(inix + A * 10000 / ngap, iniy - 10000 * Gap(A) * A / 100000), &HFF&
    gapant = Gap(A)
    A = A + 2
    Loop
    
    
    End Sub
    
    
    Private Sub Command3_Click()
    Open Text1.Text For Input As #1
    While Not EOF(1)
        Line Input #1, primo
        Num = primo
        Numero.Text = Num
    Wend
    Close #1
    Cant = 0
    
    
    Do While Cant < CSng(cnt.Text)
        Ban = 0
        ln = Len(Num)
    ' leo un dato
        Open Text1.Text For Input As #2
        While Not EOF(2)
            Line Input #2, primo
            lp = Len(primo)
            
            If Divide(Num, primo) Then
                Ban = Ban + 1
                Close #2
                GoTo 1
            End If
            If lp * 2 - 1 > ln Then
                Close #2
                GoTo 2
            End If
        Wend
        Close #2
    2    If Ban = 0 And Num <> 2 Then
            Open Text1.Text For Append As #3  'Crear el archivo plano
            Print #3, Num
                    
            Close #3
            If Cant / 10 = Int(Cant / 10) Then
            Numero.Text = Num
            Numero.Refresh
            End If
            Cant = Cant + 1
        End If
    1    A = 0
        Do Until A = ln
            x = Mid(Num, ln - A, 1)
            If x = 2 And ln = 1 Then
            sig = CInt(x) + 1
            ElseIf A = 0 Then
            sig = CInt(x) + 2
            Else
            sig = CInt(x) + 1
            End If
            If sig = 11 Or sig = 10 Then
                If ln = 1 Then
                Num = 11
                Else
                    If A = ln - 1 Then
                        Num = "10" & Right(Num, ln - 1)
                    Else
                        Num = Left(Num, ln - A - 1) & Right(CStr(sig), 1) & Right(Num, A)
                    End If
                    
                End If
                A = A + 1
            Else
                If A = 0 Then
                    Num = Left(Num, ln - A - 1) & sig
                Else
                    Num = Left(Num, ln - A - 1) & Right(CStr(sig), 1) & Right(Num, A)
                End If
                Exit Do
            End If
        Loop
    Loop
    MsgBox ("TERMINO")
    End Sub
    
    
    Public Function Divide(C, D) As Boolean
    ln = Len(C)
    lp = Len(D)
    If CSng(Left(C, 1)) < CSng(Left(D, 1)) Then
    uso = Len(D) + 1
    Else
    uso = Len(D)
    End If
    parte = Mid(C, 1, uso)
    n = 0
    Do Until n > Len(C) - uso
        E = Int(CSng(parte) / CSng(D))
        r = CSng(parte) - CSng(D) * E
        If n = Len(C) - uso Then
            If r = 0 Then
               Divide = True
               Exit Function
            Else
               Divide = False
               Exit Function
            End If
        End If
        parte = CStr(10 * r + CSng(Mid(C, n + uso + 1, 1)))
        n = n + 1
    Loop
    End Function

    Coloque limite los cálculos en vez de debajo de la raíz de Num , como en este soft el numero es un string de texto , lo hice limitando la longitud de los numeros que estan por arriba de la raiz de Num
    y cargando siempre impares en el algoritmo de detección
    Última edición por Richard R Richard; 26/10/2018, 04:34:08.

    Dejar un comentario:

Contenido relacionado

Colapsar

Trabajando...
X