[duda]Mostrar los numeros primos entre un intervalo

[Jirp96]

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 (vbnet) [Seleccionar] Expandir

Function isPrime(ByVal num As Integer) As Boolean
       Dim i As Integer
       Dim auxTest As Boolean
       Dim auxCriba(9) As Integer
       auxCriba(0) = 2
       auxCriba(1) = 3
       auxCriba(2) = 5
       auxCriba(3) = 7
       auxCriba(4) = 11
       auxCriba(5) = 13
       auxCriba(6) = 17
       auxCriba(7) = 19
       auxCriba(8) = 23
       auxCriba(9) = 29

       For i = 0 To auxCriba.Length - 1
           If num Mod auxCriba(i) = 0 Then
               isPrime = False
           Else
               auxTest = True

           End If
       Next

       Return auxTest
   End Function

y este el codigo para hallar los numeros en un intervalo dado(por el usuario):

Código (vbnet) [Seleccionar] Expandir

   Sub Main()
       Dim Min, Max, maxPrim As Integer
       Dim i, j As Integer
       Dim Primes() As Integer

       Console.Write("Introduce el maximo de primos a mostrar: ")
       maxPrim = CInt(Console.ReadLine())
       Console.Write("Introduce el minimo del intervalo: ")
       Min = CInt(Console.ReadLine())
       Console.Write("Introduce el maximo del intervalo: ")
       Max = CInt(Console.ReadLine())
       Console.WriteLine()
       Console.WriteLine()
       ReDim Primes(maxPrim-1)

       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

       Console.Write("Los numero primos entre " & Min & " y " & Max & " son: ")
       For i = 0 To Primes.Length - 1
           Console.Write(Primes(i) & " ")
       Next
       Console.ReadLine()
   End Sub

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

Me devuelve:

Código [Seleccionar] Expandir

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

[Shell Root]

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 (vbnet) [Seleccionar] Expandir

Function esPrimo( Integer sNum ) return Boolean
   Integer sCont = 0
   For i = 0 To sNum
    If (sNum MOD i == 0) Then
      sCont = sCont + 1
    End If
   Next

  If ( sCont == 2 ) Then
    Return true
  Else
    Return false
  End If
End Function

Maso menos debería ser así, ahora para calcular dependiendo del rango, podría ser así:

Código (vbnet) [Seleccionar] Expandir

  Integer sMen = 3, sMax = 50

  For i = sMen To sMax
    If ( esPrimo( i )  == true ) Then
      Print i
    End If
  Next

[neoncyber]

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 (vb) [Seleccionar] Expandir


if num == 2
   return true;

if num%2==0
   return false
raiz=sqrt(num)
for i =3 hasta raiz
   if num%i==0
      return false

return true


Saludos

[SoniaEliza]

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,

[Keyen Night]

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

 

Código (vb.net) [Seleccionar] Expandir

Public Function IsPrime(ByVal n As Long) As Boolean

       ''Si es 1 no es primo
       If n = 1 Then
           Return False
           ''Si es 2 es primo
       ElseIf n = 2 Then
           Return True
       End If

       'Si la raiz de "n" es exacta entonces no es primo

       If Math.Sqrt(n) Mod 2 = 0 Then
           Return False
       End If

       ''Desde el 2 hasta el número "n - 1"
       For x As Long = 2 To (n - 1)
           ''Si "n" divisible entre "x"
           ''entonces no es primo
           If (n Mod x) = 0 Then
               Return False
           End If
       Next
       ''Despues de todas las comprobaciones
       '' fallidas entonces "n" es primo
       Return True

   End Function

[seba123neo]

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 (vbnet) [Seleccionar] Expandir

Public Class Form1
    Private vReloj As New Stopwatch()

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        vReloj.Reset()
        vReloj.Start()
        Dim vPrimos As Long() = getPrimes(9000000)
        vReloj.Stop()
        Debug.WriteLine("Se Calcularon los primeros " & vPrimos.Length & " en " & (vReloj.ElapsedMilliseconds / 1000) & " segundos.")
    End Sub

    Private Shared Function getPrimes(ByVal n As Long) As Long()
        If n < 3 Then
            If n = 2 Then
                Dim prime2 As Long() = {2}
                Return prime2
            Else
                Dim no_prime As Long() = {}
                Return no_prime
            End If
        End If

        Dim composite As New BitArray(n / 3)
        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
        Dim i As Long = 0
        Dim len As Long = composite.Length
        Dim toggle As Boolean = False

        While s < len

            If Not composite(System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)) Then
                Dim inc As Long = p1 + p2
                Dim k As Long = s

                While k < len
                    composite(k) = True
                    k += inc
                End While

                k = s + s2

                While k < len
                    composite(k) = True
                    k += inc
                End While
            End If

            p1 += 2
            If InlineAssignHelper(toggle, Not toggle) Then
                s += d2
                d1 += 16
                p2 += 2
                s2 = p2
            Else
                s += d1
                d2 += 8
                p2 += 6
                s2 = p1
            End If
        End While

        Dim primes As New List(Of Long)()
        Dim log_n As Double = Math.Log(n)

        primes.Capacity = CInt((n / log_n) * (1 + 1.2762 / log_n))
        primes.Add(2)
        primes.Add(3)

        Dim p As Long = 5
        toggle = False
        i = 0

        While p <= n
            If Not composite(System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)) Then
                primes.Add(p)
            End If
            p += If((InlineAssignHelper(toggle, Not toggle)), 2, 4)
        End While

        Return primes.ToArray()
    End Function

    Private Shared Function InlineAssignHelper(Of T)(ByRef target As T, ByVal value As T) As T
        target = value
        Return value
    End Function
End Class


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.

[Keyen Night]

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 (vb.net) [Seleccionar] Expandir

   Public Function Primes(ByVal N As Long) As Long()

       If N < 3 Then
           Return New Long() {}
       End If

       Dim _Tabla As New BitArray(N - 2), _
       _Primes As New List(Of Long), _
       _P As Byte() = New Byte() {2, 3, 5, 7}


       Dim Y As Long = 2
       For Each X As Byte In _P
           Do While (X * Y) < N
               _Tabla((X * Y) - 2) = True
               Y += 1
           Loop
       Next

       Y = 0
       Do While Y < (_Tabla.Length - 1)
           If Not _Tabla(Y) AndAlso _
               Not (Math.Sqrt(Y + 2) = CLng(Math.Sqrt(Y + 2))) Then
               _Primes.Add(Y + 2)
           End If
           Y += 1
       Loop

       Return _Primes.ToArray()
   End Function

[seba123neo]

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 (vbnet) [Seleccionar] Expandir

Public Class Form1
    Private vReloj As New Stopwatch()

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        vReloj.Reset()
        vReloj.Start()
        Dim vPrimos As List(Of Long) = getPrimes(99999999)
        vReloj.Stop()
        Debug.WriteLine("Se Calcularon los primeros " & vPrimos.Count & " en " & (vReloj.ElapsedMilliseconds / 1000) & " segundos.")
    End Sub

    Function getPrimes(ByVal vLimite As Long) As List(Of Long)
        Dim vNoEsPrimo(vLimite) As Boolean
        Dim vPrimos As New List(Of Long)
        For vPrimo As Long = 2 To vLimite
            If Not vNoEsPrimo(vPrimo) Then
                vPrimos.Add(vPrimo)
                For i As Long = vPrimo * 2 To vLimite Step vPrimo
                    vNoEsPrimo(i) = True
                Next
            End If
        Next
        Return vPrimos
    End Function
End Class

saludos.