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

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  .NET (C#, VB.NET, ASP) (Moderador: kub0x)
| | | |-+  [duda]Mostrar los numeros primos entre un intervalo
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [duda]Mostrar los numeros primos entre un intervalo  (Leído 11,962 veces)
Jirp96

Desconectado Desconectado

Mensajes: 46


Ver Perfil
[duda]Mostrar los numeros primos entre un intervalo
« en: 11 Mayo 2011, 04:22 am »

Hola!
Tengo una funcion(hecha por mi) para averiguar si un numero es primo(es un poco "rustico" el metodo para averiguarlo, creo yo, pero funciona bien)
Y ahora la estoy usando en otro programa pero me da resultados "algo" extraños, y no entiendo porque :-\
este es el codigo de la funcion:

Código
  1. Function isPrime(ByVal num As Integer) As Boolean
  2.        Dim i As Integer
  3.        Dim auxTest As Boolean
  4.        Dim auxCriba(9) As Integer
  5.        auxCriba(0) = 2
  6.        auxCriba(1) = 3
  7.        auxCriba(2) = 5
  8.        auxCriba(3) = 7
  9.        auxCriba(4) = 11
  10.        auxCriba(5) = 13
  11.        auxCriba(6) = 17
  12.        auxCriba(7) = 19
  13.        auxCriba(8) = 23
  14.        auxCriba(9) = 29
  15.  
  16.        For i = 0 To auxCriba.Length - 1
  17.            If num Mod auxCriba(i) = 0 Then
  18.                isPrime = False
  19.            Else
  20.                auxTest = True
  21.  
  22.            End If
  23.        Next
  24.  
  25.        Return auxTest
  26.    End Function

y este el codigo para hallar los numeros en un intervalo dado(por el usuario):
Código
  1.    Sub Main()
  2.        Dim Min, Max, maxPrim As Integer
  3.        Dim i, j As Integer
  4.        Dim Primes() As Integer
  5.  
  6.        Console.Write("Introduce el maximo de primos a mostrar: ")
  7.        maxPrim = CInt(Console.ReadLine())
  8.        Console.Write("Introduce el minimo del intervalo: ")
  9.        Min = CInt(Console.ReadLine())
  10.        Console.Write("Introduce el maximo del intervalo: ")
  11.        Max = CInt(Console.ReadLine())
  12.        Console.WriteLine()
  13.        Console.WriteLine()
  14.        ReDim Primes(maxPrim-1)
  15.  
  16.        For i = 0 To maxPrim - 1 'este for es para almacenar el numero primo en el array Primes(), en la posicion "i"
  17.            For j = Min To Max - 1 'y este recorrre desde el valor minimo hasta el maximo y va comparando si el valor de "j" es un numero primo(deberia)
  18.                If isPrime(j) = True Then
  19.                    Primes(i) = j
  20.                End If
  21.            Next
  22.        Next
  23.  
  24.        Console.Write("Los numero primos entre " & Min & " y " & Max & " son: ")
  25.        For i = 0 To Primes.Length - 1
  26.            Console.Write(Primes(i) & " ")
  27.        Next
  28.        Console.ReadLine()
  29.    End Sub

Si pruebo(por ejemplo) Con:
-maxPrim = 10
-min = 1
-max = 20

Me devuelve:

Código:
19 19 19 19 19 19 19 19 19 19

y.... la verdad no veo porqué...
Por lo que puedo ver, siempre me devuelve el valor de la variable "max" -1, como esta en el 2do for, asi que creo que el error debe estar ahi
Alguien sabe cual es el problema(o al menos la linea)?
Saludos, y gracias a todos los que se tomaron la molestia de leer
pd: si alguna parte del codigo no se entiende o algo, digan y lo explico
pd2: Me olvide de aclarar, uso Visual Basic 2005 Express


« Última modificación: 11 Mayo 2011, 04:28 am por Jirp96 » En línea

Shell Root
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.724


<3


Ver Perfil WWW
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #1 en: 11 Mayo 2011, 05:47 am »

A ver, antes programa en VB pero desde que me pase a linux no lo hago, así que por código casi no podré ayudarte, pero quizás si en la lógica.

Código
  1. Function esPrimo( Integer sNum ) return Boolean
  2.   Integer sCont = 0
  3.   For i = 0 To sNum
  4.    If (sNum MOD i == 0) Then
  5.      sCont = sCont + 1
  6.    End If
  7.   Next
  8.  
  9.  If ( sCont == 2 ) Then
  10.    Return true
  11.  Else
  12.    Return false
  13.  End If
  14. End Function

Maso menos debería ser así, ahora para calcular dependiendo del rango, podría ser así:
Código
  1.  Integer sMen = 3, sMax = 50
  2.  
  3.  For i = sMen To sMax
  4.    If ( esPrimo( i )  == true ) Then
  5.      Print i
  6.    End If
  7.  Next


En línea

Te vendería mi talento por poder dormir tranquilo.
neoncyber

Desconectado Desconectado

Mensajes: 90



Ver Perfil WWW
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #2 en: 11 Mayo 2011, 06:43 am »

Hola, matematicamente y existen varios teoremas demostrados que la mejor forma de verificar si un numero primo es comparar desde el numero 3 hasta la raiz cuadrada de este mismo numero
Código
  1. if num == 2
  2.   return true;
  3.  
  4. if num%2==0
  5.   return false
  6. raiz=sqrt(num)
  7. for i =3 hasta raiz
  8.   if num%i==0
  9.      return false
  10.  
  11. return true
  12.  

Saludos
En línea

Código
  1. #!/usr/bin/python
  2. print "Visit:"
  3. print "http:\\donkeysharp.blogspot.com"
  4.  
SoniaEliza

Desconectado Desconectado

Mensajes: 1


Ver Perfil
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #3 en: 11 Mayo 2011, 08:45 am »

Hola,
sin revisar la funcion isPrime, tienes un error de lógica en esta parte:
For i = 0 To maxPrim - 1 'este for es para almacenar el numero primo en el array Primes(), en la posicion "i"
            For j = Min To Max - 1 'y este recorrre desde el valor minimo hasta el maximo y va comparando si el valor de "j" es un numero primo(deberia)
                If isPrime(j) = True Then
                    Primes(i) = j
                End If
            Next
        Next

Prueba eliminando el primer for así:
i=0
For j = Min To Max - 1 'y este recorrre desde el valor minimo hasta el maximo y va comparando si el valor de "j" es un numero primo(deberia)
    If isPrime(j) = True Then
        Primes(i) = j
        i= i+1
    End If
Next

Saludos,
En línea

Keyen Night


Desconectado Desconectado

Mensajes: 496


Nothing


Ver Perfil
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #4 en: 12 Mayo 2011, 18:15 pm »

Hace tiempo hice un código para factorizar y la función IsPrime la modifique hasta obtener los resultados más rápidos posibles sin algoritmo y el codigo quedo así:

Explique cada línea :xD

  
Código
  1. Public Function IsPrime(ByVal n As Long) As Boolean
  2.  
  3.        ''Si es 1 no es primo
  4.        If n = 1 Then
  5.            Return False
  6.            ''Si es 2 es primo
  7.        ElseIf n = 2 Then
  8.            Return True
  9.        End If
  10.  
  11.        'Si la raiz de "n" es exacta entonces no es primo
  12.  
  13.        If Math.Sqrt(n) Mod 2 = 0 Then
  14.            Return False
  15.        End If
  16.  
  17.        ''Desde el 2 hasta el número "n - 1"
  18.        For x As Long = 2 To (n - 1)
  19.            ''Si "n" divisible entre "x"
  20.            ''entonces no es primo
  21.            If (n Mod x) = 0 Then
  22.                Return False
  23.            End If
  24.        Next
  25.        ''Despues de todas las comprobaciones
  26.        '' fallidas entonces "n" es primo
  27.        Return True
  28.  
  29.    End Function
« Última modificación: 14 Mayo 2011, 18:24 pm 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...
seba123neo


Desconectado Desconectado

Mensajes: 3.621



Ver Perfil WWW
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #5 en: 13 Mayo 2011, 02:07 am »

una de las formas mas rapidas de sacar primos es la llamada "Criba de Eratóstenes" y tambien una de las mas antiguas (antes de cristo),

informacion del metodo:

Criba de Eratóstenes

aca hay una implementación de ese metodo.

Código
  1. Public Class Form1
  2.    Private vReloj As New Stopwatch()
  3.  
  4.    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
  5.        vReloj.Reset()
  6.        vReloj.Start()
  7.        Dim vPrimos As Long() = getPrimes(9000000)
  8.        vReloj.Stop()
  9.        Debug.WriteLine("Se Calcularon los primeros " & vPrimos.Length & " en " & (vReloj.ElapsedMilliseconds / 1000) & " segundos.")
  10.    End Sub
  11.  
  12.    Private Shared Function getPrimes(ByVal n As Long) As Long()
  13.        If n < 3 Then
  14.            If n = 2 Then
  15.                Dim prime2 As Long() = {2}
  16.                Return prime2
  17.            Else
  18.                Dim no_prime As Long() = {}
  19.                Return no_prime
  20.            End If
  21.        End If
  22.  
  23.        Dim composite As New BitArray(n / 3)
  24.        Dim d1 As Long = 8, d2 As Long = 8, p1 As Long = 3, p2 As Long = 7, s As Long = 7, s2 As Long = 3
  25.        Dim i As Long = 0
  26.        Dim len As Long = composite.Length
  27.        Dim toggle As Boolean = False
  28.  
  29.        While s < len
  30.  
  31.            If Not composite(System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)) Then
  32.                Dim inc As Long = p1 + p2
  33.                Dim k As Long = s
  34.  
  35.                While k < len
  36.                    composite(k) = True
  37.                    k += inc
  38.                End While
  39.  
  40.                k = s + s2
  41.  
  42.                While k < len
  43.                    composite(k) = True
  44.                    k += inc
  45.                End While
  46.            End If
  47.  
  48.            p1 += 2
  49.            If InlineAssignHelper(toggle, Not toggle) Then
  50.                s += d2
  51.                d1 += 16
  52.                p2 += 2
  53.                s2 = p2
  54.            Else
  55.                s += d1
  56.                d2 += 8
  57.                p2 += 6
  58.                s2 = p1
  59.            End If
  60.        End While
  61.  
  62.        Dim primes As New List(Of Long)()
  63.        Dim log_n As Double = Math.Log(n)
  64.  
  65.        primes.Capacity = CInt((n / log_n) * (1 + 1.2762 / log_n))
  66.        primes.Add(2)
  67.        primes.Add(3)
  68.  
  69.        Dim p As Long = 5
  70.        toggle = False
  71.        i = 0
  72.  
  73.        While p <= n
  74.            If Not composite(System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)) Then
  75.                primes.Add(p)
  76.            End If
  77.            p += If((InlineAssignHelper(toggle, Not toggle)), 2, 4)
  78.        End While
  79.  
  80.        Return primes.ToArray()
  81.    End Function
  82.  
  83.    Private Shared Function InlineAssignHelper(Of T)(ByRef target As T, ByVal value As T) As T
  84.        target = value
  85.        Return value
  86.    End Function
  87. End Class
  88.  

la diferencia es abismal, compilado este ejemplo calcula el primer MILLON de numeros primos en 0.3 segundos, no llega a un segundo.

en cambio algo asi como la funcionde Keyen Night, calcular el primer millon de numeros tardaria unos 40 segundos, en cambio este ejemplo en 40 segundos calcularia los primeros 100 millones.

saludos.

En línea

Keyen Night


Desconectado Desconectado

Mensajes: 496


Nothing


Ver Perfil
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #6 en: 14 Mayo 2011, 19:41 pm »

Si bien la Criba de Eratóstenes es el metodo mas rapido ese codigo que colocastes no funciona :-[ hice getPrimes(1000), se salta varios primos y hay compuestos en la lista como el 995, no hay ningun primo que termine en 5 y se salto el 751 que es un primo.

Así estaría bien aplicado y mas corto :)
Código
  1.    Public Function Primes(ByVal N As Long) As Long()
  2.  
  3.        If N < 3 Then
  4.            Return New Long() {}
  5.        End If
  6.  
  7.        Dim _Tabla As New BitArray(N - 2), _
  8.        _Primes As New List(Of Long), _
  9.        _P As Byte() = New Byte() {2, 3, 5, 7}
  10.  
  11.  
  12.        Dim Y As Long = 2
  13.        For Each X As Byte In _P
  14.            Do While (X * Y) < N
  15.                _Tabla((X * Y) - 2) = True
  16.                Y += 1
  17.            Loop
  18.        Next
  19.  
  20.        Y = 0
  21.        Do While Y < (_Tabla.Length - 1)
  22.            If Not _Tabla(Y) AndAlso _
  23.                Not (Math.Sqrt(Y + 2) = CLng(Math.Sqrt(Y + 2))) Then
  24.                _Primes.Add(Y + 2)
  25.            End If
  26.            Y += 1
  27.        Loop
  28.  
  29.        Return _Primes.ToArray()
  30.    End Function
« Última modificación: 15 Mayo 2011, 19:09 pm 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...
seba123neo


Desconectado Desconectado

Mensajes: 3.621



Ver Perfil WWW
Re: [duda]Mostrar los numeros primos entre un intervalo
« Respuesta #7 en: 14 Mayo 2011, 23:22 pm »

tenes razon, lo que pasa que se adapto de C# a VB y algo esta mal, aca te dejo uno que funciona bien con el mismo metodo.

Código
  1. Public Class Form1
  2.    Private vReloj As New Stopwatch()
  3.  
  4.    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
  5.        vReloj.Reset()
  6.        vReloj.Start()
  7.        Dim vPrimos As List(Of Long) = getPrimes(99999999)
  8.        vReloj.Stop()
  9.        Debug.WriteLine("Se Calcularon los primeros " & vPrimos.Count & " en " & (vReloj.ElapsedMilliseconds / 1000) & " segundos.")
  10.    End Sub
  11.  
  12.    Function getPrimes(ByVal vLimite As Long) As List(Of Long)
  13.        Dim vNoEsPrimo(vLimite) As Boolean
  14.        Dim vPrimos As New List(Of Long)
  15.        For vPrimo As Long = 2 To vLimite
  16.            If Not vNoEsPrimo(vPrimo) Then
  17.                vPrimos.Add(vPrimo)
  18.                For i As Long = vPrimo * 2 To vLimite Step vPrimo
  19.                    vNoEsPrimo(i) = True
  20.                Next
  21.            End If
  22.        Next
  23.        Return vPrimos
  24.    End Function
  25. End Class

saludos.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
katas 2 9,860 Último mensaje 10 Marzo 2010, 01:50 am
por Novlucker
[Duda] Sacar números primos de una secuencia
Programación Visual Basic
Hurubnar 2 4,012 Último mensaje 25 Febrero 2011, 16:59 pm
por Hurubnar
Duda en numeros primos
Java
noaptebuna 4 2,792 Último mensaje 22 Septiembre 2015, 09:03 am
por noaptebuna
(Duda matemática) Cuestión sobre los números primos
Dudas Generales
class_OpenGL 9 3,924 Último mensaje 6 Mayo 2016, 16:18 pm
por MinusFour
Sucesion parcial o completa entre numeros primos. « 1 2 3 »
Criptografía
Usuario887 23 15,291 Último mensaje 15 Febrero 2021, 23:56 pm
por Usuario887
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines