miércoles, agosto 13, 2008

Algunas mejoras del programa



Bueno, antes de llegar a interpretar el error del programa para buscar primos, tenemos que saber cuantos elementos se han metido en el cuadro de lista o ListBox. Posiblemente hayamos llegado al límite de lo soportable.

Como se puede intuir en la imagen del encabezado hemos metido un nuevo control para llevar la cuenta de primos introducidos en la lista.

También es conveniente el siguiente cambio:

El único número primo par es 2. Todos los demás pares tienen el número dos como divisor por lo que vamos a hacer el pequeño cambio de no estudiar si los números pares son primos. Lo hacemos metiendo en la lista de primos el número 2 directamente. El primer candidato a valorar será el 3 y los siguientes se obtendrán sumando de 2 en 2.

Como sólo vamos a comprobar si son primos los números impares, no vamos a probar las divisiones con pares (nunca darán resto cero). Por lo tanto los divisores serán 3, 5 7, etc. Para encontrar el siguiente divisor haremos +2.

Resultados obtenidos:
Si buscamos primos hasta el número 100.000 la ejecución ahora tarda 4 segundos. Es un segundo más que antes debido al esfuerzo de sumar el contador de primos y refrescar el control en el formulario. Se encuentran 9.592 primos.

Buscando primos hasta el número 1.000.000 ahora ya en lugar de 7 minutos tarda 16 segundos.

Y por último hasta 100.000.000 antes tardaba 3 horas, 7 minutos y 1 segundo. Ahora en cambio encuentra los 5.761.455 primos en 2 horas, 19 minutos y 48 segundos.


Dim candidato As Long = 3
Dim pruebaDivisor As Long
Dim esPrimo As Boolean
Dim numPrimos As Long = 1
Me.lblInicio.Text = ""
Me.lblFIn.Text = ""
Me.lblInicio.Text = Now
lstPrimos.BeginUpdate()
Me.lstPrimos.Items.Add(2)
Me.lblNumPrimos.Text = numPrimos
Me.lblNumPrimos.Refresh()
While candidato <= Val(Me.txtLimiteSuperior.Text)
pruebaDivisor = 3
esPrimo = True
While pruebaDivisor * pruebaDivisor <= candidato
If candidato Mod pruebaDivisor = 0 Then
esPrimo = False
Exit While
End If
pruebaDivisor += 2
End While
If esPrimo Then
Me.lstPrimos.Items.Add(candidato)
numPrimos += 1
Me.lblNumPrimos.Text = numPrimos
Me.lblNumPrimos.Refresh()
End If
candidato += 2
End While
lstPrimos.EndUpdate()
Me.lblFIn.Text = Now

3 comentarios:

Anónimo dijo...

Hola, pasaba por aquí...

Has probado lo siguente? coloca los números así:

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27...

De esta manera podemos eliminar muchos números de manera directa ya que todos los números de las columnas 2, 3, 4 y 6 no serán primos, así que en lugar de un +=2 quizá valdría la pena condicionarlo también cuando el candidato mod 6 = 3, en realidad es sólo una división que te ahorras, porque la primera comprobación es el 3... pero algo es algo.

De las dos columnas restantes hay formas de extraer números para que no haya que calcularlos todos...

Saludos

Anónimo dijo...

Antes se me olvidó comentar, los números restantes de la primera y quinta columna (que son los que contienen los números primos) ya no serán divisibles por 3 así que no hace falta empezar en 3, eso ahorra un poquiiiiito más :)

Aitor Iriarte dijo...

Gracias tayoken,
Me pongo a hacer esos cambios y a ver que pasa.
:-)