Software para crear números primos

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.

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

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.

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.

[Richard R Richard]

Re: Software para crear números primos

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 $\notcien{1}{308}-1\neq\notcien{1}{308}$ 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.

Re: Software para crear números primos

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

[u_maligno]

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.

[Richard R Richard]

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),

tambien probe

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.

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.

'****************************************************************************************
'* 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

Saludos.

[Jaime Rudas]

Re: Software para crear números primos

Este teorema fue demostrado por Chebyshev en 1950.

En realidad, fue demostrado en 1852: Chebyshov murió en 1894.

[u_maligno]

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

[Alriga]

Re: Software para crear números primos

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.

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

....

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.

[u_maligno]

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

[Richard R Richard]

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

[u_maligno]

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

[Richard R Richard]

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

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