Foro de elhacker.net

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:

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

    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:


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

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.

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í:

  Integer sMen = 3, sMax = 50
 
  For i = sMen To sMax
    If ( esPrimo( i )  == true ) Then
      Print i
    End If
  Next

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

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

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,

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

  

 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

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 (http://pinae.wordpress.com/2009/05/19/criba-de-eratostenes/)

aca hay una implementación de ese metodo.

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.

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

    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

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.

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.