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