sábado, agosto 09, 2008

Busquemos primos con VB.NET


Bueno, he hecho el primer programita algo útil para buscar primos.
El tipo long de .NET tiene 8 bytes por lo que nos permite manejar enteros largos desde -9223372036854775808 hasta +9223372036854775807.

Lo primero en lo que nos tenemos que fijar es en un pequeño detalle. Llamemos candidato al entero que queremos saber si es primo o no. Pues no hace falta revisar si tiene divisores desde 2 hasta el candidato - 1, ya que ocurre lo siquiente:

Si revisamos los divisores desde 2 en adelante, cuando lleguemos a un divisor cuyo cuadrado es mayor que el candidato ya no va a aparecer ningún divisor más por lo que dejaremos de comprobar. Esto es así porque si has comprobado todos los divisores anteriores y no han resultado, si el candidato no es primo tendrá 2 factores primos mayores que el que estamos comprobando. Como vemos que el que estamos probando al cuadrado se pasa del número pues ya vemos que no hay que buscar más porque es imposible que tenga esos 2 factores primos.

La pantalla del encabezado es el aspecto del formulario.

Este programita sólo tiene código asociado al botón. Cuando se pulsa se pone la máquina en marcha y nos irá poniendo en la lista todos los primos hasta llegar al número que hemos medido en el cuadro de texto.



Private Sub btnBuscarPrimos_Click
(ByVal sender As System.Object, ByVal e As System.EventArgs)
Handles btnBuscarPrimos.Click
Dim candidato As Long = 2
Dim pruebaDivisor As Long
Dim esPrimo As Boolean
Me.lblInicio.Text = ""
Me.lblFIn.Text = ""
Me.lblInicio.Text = Now
While candidato <= Val(Me.txtLimiteSuperior.Text)
pruebaDivisor = 2
esPrimo = True
While pruebaDivisor * pruebaDivisor <= candidato
If candidato Mod pruebaDivisor = 0 Then
esPrimo = False
Exit While
End If
pruebaDivisor += 1
End While
If esPrimo Then
lstPrimos.BeginUpdate()
Me.lstPrimos.Items.Add(candidato)
lstPrimos.EndUpdate()
End If
candidato += 1
End While
Me.lblFIn.Text = Now
End Sub



Aviso:

Si buscamos primos hasta 10.000 el programa los muestra inmediatamente.
Hasta 100.000 en mi portátil tarda 3 segundos.
Hasta 1.000.000, hay que esperar 7 minutos.
Hasta 100.000.000 tarda 3 horas 7 minutos y 1 segundo.

Lo peor es lo que ha pasado al ponerlo a buscar hasta 1.000.000.000. Después de muchas horas...









No hay comentarios: