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