No hay avance

Ocurre algo raro...

Ayer realicé los cambios propuestos por Tayoken (ver los comentarios de los dos anteriores post) y apenas ha habido mejoras cuando por lógica los tiempos en la búsqueda de primos tenían que haberse mejorado enormemente.

Es seguro que se debe a los tiempos de ejecución de algunas instrucciones en .net pero en estos momentos sólo voy a exponer los resultados.

Cambios realizados:

Utilizamos el cuadro que nos proponían:

01 02 03 04 05 06
07 08 09 10 11 12
13 14 15 16 17 18
...

Los primeros primos son 1, 2 y 3, pero a partir de este punto los candidatos a primos son los de las columnas 1 y 5. En las otras columnas o bien son números pares, o tienen el 3 como divisor.

Los cambios son:
1.-se meten los primos iniciales 2 y 3 en la lista de primos.
2.-se buscan primos a partir del 5.
3.-en lugar de sumar dos para el siguiente candidato se empieza sumando dos, luego se suma cuatro, luego otra vez dos, y así hasta el final.

Lo que ocurre es que contra toda lógica los tiempos no se han reducido demasiado:
Hasta el número 100.000 antes tardaba 4 segundos y ahora 3. Hay 9.592 primos.
Hasta 1.000.000 antes 16 segundos y ahora 14. Hay 78.498 primos.
Hasta 100.000.000 antes 2 horas, 19 minutos 48 segundos y ahora 2 horas 17 minutos y 26 segundos. Hay 5.761.455 primos.

Dim candidato As Long = 5
        Dim pruebaDivisor As Long
        Dim esPrimo As Boolean
        Dim numPrimos As Long = 2
        Dim sumarDosAlCandidato As Boolean = True
        Me.lblInicio.Text = ""
        Me.lblFIn.Text = ""
        Me.lblInicio.Text = Now
        lstPrimos.BeginUpdate()
        Me.lstPrimos.Items.Add(2)
        Me.lstPrimos.Items.Add(3)
        Me.lblNumPrimos.Text = numPrimos
        Me.lblNumPrimos.Refresh()
        While candidato <= Val(Me.txtLimiteSuperior.Text)
            pruebaDivisor = 5
            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
            If sumarDosAlCandidato Then
                candidato += 2
                sumarDosAlCandidato = False
            Else
                candidato += 4
                sumarDosAlCandidato = True
            End If
        End While
        lstPrimos.EndUpdate()
        Me.lblFIn.Text = Now