y empieza el fin de semana

En principio estoy de vacaciones y todos los días son iguales, pero este fin de semana estaré un poco desconectado. Me voy a la playa.

El programa de los números de Mersenne está prácticamente terminado. Espero publicarlo el lunes. Está hecho en Visual Basic.

Os dejo un post de algo que me ha sorprendido y podría tener repercusión a medio plazo.

Me imagino que igual que yo, cuando queréis buscar algo acudís a la Wikipedia. No sabía que había una guerra entre la Wikipedia y Google, pero desde luego parece que ya han descubierto sus cartas.

Ya el año pasado había expertos que advertían que el mayor potencial competidor de Google era la Wikipedia. Por ejemplo esto se publicaba el 19 de julio de 2007. Se argumenta que la gente utiliza mayoritariamente Google, pero que las primeras respuestas suelen ser de Wikipedia y es aquí donde adquieres el conocimiento que buscabas.

El 13 de diciembre de 2007 Google anuncia su proyecto Google Knol que es la Wikipedia de Google donde van a pagar a los autores a través de anuncios AdWords. Es el 24 de julio de 2008 cuando se anuncia al público.

En este contexto la Wikipedia se defiende este mismo mes de agosto con este anuncio.

Es estos momentos parece David contra Goliath. La gran ventaja de Google es poder determinar los resultados de búsqueda, pero la Wikipedia ya es suficientemente conocida como para ir por libre.

Saludos.

Primos gigantes. Fase I

Siguiendo el planning indicado en el post "Como cazar un primo gigante", lo primero es conseguir un número de Maresnne grande.

El número de Maresnne se definía como Mn = 2^n -1 (ver post anterior).

¿Para que n el número es suficientemente grande? Bueno, pues depende. En el año 1952 el número M521 era muy grande, ya que constituyó el número primo más grande conocido hasta entonces.

M521 es un número de 157 dígitos y se logró con una máquina SWAC.

He hecho una pequeña aproximación al programa que nos va a permitir obtener ese primo gigante. Como es lógico el problema es la limitación de los tipos de datos predefinidos tanto en Visual Basic como en el framework.

Poniendo tipos enteros el programa funciona bien hasta el Mersenne 30:

Como se ve los números crecen rápidamente:

M15=32.767.
M20=1.048.575.
M25=33.554.431.
M30=1.073.741.823
Con M31 salta el error SYSTEM.OVERFLOWEXCEPTION: La operación aritmética ha provocado un desbordamiento.

El tipo integer es un entero de 4 bytes (32 bits) con signo por lo que puede variar entre -2.147.483.648 y 2.147.483.647.
Por eso falla el M31.

Luego he decidido utilizar los enteros más grandes:

El tipo long consiste en 8 bytes (64 bits) con signo. Por lo tanto sus valores puede variar entre -9.223.372.036.854.775.808 y 9.223.372.036.854.775.807.
El tipo long de visual basic es totalmente equivalente al tipo System.Int64 del framework .NET.

Bueno, con el tipo long se consigue llegar correctamente al M62 que es igual a 4.611.686.018.427.387.903.

Pero mejor que el tipo long es utilizar el tipo SYSTEM.DECIMAL ya que es el mayor tipo predefinido que podemos utilizar. Utiliza 16 bytes (128 bits) que son una animalada.

Los límites en los que nos movemos son (lo he copiado de la ayuda del .NET):

79.228.162.514.264.337.593.543.950.335 sin separador decimal
0 a +/-7,9228162514264337593543950335 con 28 posiciones a la derecha del signo decimal; el número más pequeño distinto de cero es
+/-0,0000000000000000000000000001 (+/-1E-28).

Con este último tipo de dato gigante llegamos correctamente a M95.
En la imagen vemos el resultado:


El programa Visual Basic.NET utilizado es el siguiente:

Module Module1
Function exponenciacionBinaria(ByVal numero As Integer) As System.Decimal
    If numero = 1 Then Return 2
    If numero Mod 2 = 0 Then Return exponenciacionBinaria(numero / 2) * exponenciacionBinaria(numero / 2)
    Return 2 * exponenciacionBinaria(numero - 1)
End Function
Sub Main()
    Dim n As Integer
    Dim numeroMersenne As String
    Dim dosElevadoAn As System.Decimal
    Console.WriteLine("Los números de Mersenne se representan como Mn")
    Console.Write("Introduzca el valor de n que quiere calcular: ")
    n = Console.ReadLine()
    dosElevadoAn = exponenciacionBinaria(n)
    numeroMersenne = dosElevadoAn - 1
    Console.WriteLine("M" & n & " es igual a " & numeroMersenne)
    Console.ReadLine()
End Sub
End Module

Programa en C#

He ejecutado el mismo programa de los primos pero esta vez en C#. El límite fijado ha sido otra vez el número 100.000.000.

El resultado ha sido intermedio entre el código VB.NET (el más rápido con 10 minutos 21 segundos) y el código C++ (el más lento con 10 minutos 46 segundos después de activar la optimización de velocidad).

Exactamente con C# ha tardado 10 minutos 40 segundos.

Saludos.

El programa es el siguiente:

using System;
using System.IO;
using System.Globalization;

namespace BuscaPrimos
{
 /// 

 /// Descripción breve de Class1.
 /// 
 class Class1
 {
  /// 

  /// Punto de entrada principal de la aplicación.
  /// 
  [STAThread]
  static void Main(string[] args)
  {

   const string fichero = @"primos.txt";
   System.IO.StreamWriter sw = new System.IO.StreamWriter(fichero);
   
   string horaInicio = DateTime.Now.ToString("G",DateTimeFormatInfo.InvariantInfo);
   int candidato = 5;
   int pruebaDivisor;
   int esPrimo;
   int limiteSuperior;

   Console.Write("Introduce el limite al que llegar: ");
   limiteSuperior = Convert.ToInt32(Console.ReadLine());

   sw.WriteLine(2);
   sw.WriteLine(3);
   while(candidato <= limiteSuperior)
   {
    pruebaDivisor = 5;
    esPrimo = 1;
    while(pruebaDivisor * pruebaDivisor <= candidato)
    {
     if(candidato % pruebaDivisor == 0)
     {
      esPrimo = 0;
      break;
     }
     pruebaDivisor += 2;
    }
    if(esPrimo == 1)
     sw.WriteLine(candidato);

    candidato += 2;
            
    pruebaDivisor = 5;
    esPrimo = 1;
    while(pruebaDivisor * pruebaDivisor <= candidato)
    {
     if((candidato % pruebaDivisor) == 0)
     {
      esPrimo = 0;
      break;
     }
     pruebaDivisor += 2;
    }
    if(esPrimo == 1)
     sw.WriteLine(candidato);

    candidato += 4;
   }
 
   sw.Write("Hora de inicio: ");
   sw.WriteLine(horaInicio);
   sw.Write("Hora de final: ");
   sw.WriteLine(DateTime.Now.ToString("G",DateTimeFormatInfo.InvariantInfo));
   sw.Close();
   Console.WriteLine("Fin.");
  }
 }
}

A veces VisualBasic.net es más rápido que visualC++

En los post anteriores se pueden ver dos programas idénticos en el que Visual Basic.NET es más rápido que Visual C++.

Buscando por ahí, he encontrado unas pruebas de rendimiento realizadas hace años. Podemos ver la comparativa aquí.

En un momento concreto nos dicen "One important distinction between the CLR and other similar types of architectures, such as the Java Virtual Machine (JVM) or the Visual Basic Virtual Machine (VBVM), is that your code is never interpreted. This means that your code is being run at native machine speed".

Lo más importante son los datos de la comparativa. Han publicado lo que tarda cada instrucción en cada lenguaje y el resultado es este:

En Visual C++ 6 (yo no utilizo exactamente esta versión, sino la que viene con el Visual Studio 2003) un test de INTEGER ADITION tarda 505 msg y en Visual Basic.NET 342 msg.

El test de INTEGER MULTIPLICATION en VC++ tarda 676 msg y en VB.NET 343msg.

Justo en nuestro programita de los primos utilizamos el INTEGER ADITION y el INTEGER MULTIPLICATION por lo el VB.NET gana a VC++.

Más adelante, en la búsqueda de un primo realmente grande vamos a tener que hacer operaciones con tipos string y otras cosillas que igual hagan más rápido al VC++ por lo que tendremos que seguir con los dos lenguajes.

Saludos y gracias a tayoken por la sugerencia anterior.

Otra sorpresa

Pues si, siguiendo el consejo de tayoken he cogido el programa de los primos en C++ y lo he pasado a VB.NET.

Este proyecto Visual Basic se trata igual que la versión de C++ de una aplicación de consola.

La ejecución para el límite de 100 millones ha tardado en VB.NET 10 minutos 21 segundos. Una gran sorpresa ya que en Visual C++ con las opciones de compilación por defecto había tardado 14 minutos 26 segundos.

No soy el primero que se sorprende. Por ejemplo aquí les ha pasado lo mismo.

Después de unos pocos ajustes de configuración en las propiedades del proyecto he conseguido reducir la ejecución a 10 minutos 46 segundos pero no es suficiente.

Para empezar, se ha comprobador que no están habilitadas las extensiones administradas. No es un proyecto CLR (opción /clr del compilador), o sea que no está orientado al Common Language Runtime.

Las opciones que he tocado son:

Propiedades de configuración, General, Optimización de todo el programa: SI
Propiedades de configuración, C/C++, Optimización: Máxima velocidad
Propiedades de configuración, C/C++, Optimizaciones globales: SI
Propiedades de configuración, C/C++, tamaño o velocidad: ninguno (no se puede seleccionar velocidad si hemos marcado antes Optimización de todo el programa).
Propiedades de configuración, C/C++, Optimizar para procesador: Pentium4 y superior.
Propiedades de configuración, C/C++, Generación de código: Valor predeterminado (las otras opciones no son compatibles con la opción de "Maximizar velocidad".
Propiedades de configuración, C/C++, General, Formato de la información de depuración: Deshabilitado (no es compatible con la opción /gl).

Mañana intentaremos que Visual C++ gane por fin a Visual Basic.NET

Saludos.

Imports System.io
Module Module1

    Sub Main()
        Dim horaComienzo As Date
        Dim fichero As New StreamWriter("primos.txt")
        horaComienzo = Now
        Dim candidato As Integer = 5
        Dim pruebaDivisor As Integer
        Dim esPrimo As Boolean
        Dim numPrimos As Integer = 2
        Dim limiteSuperior As Integer
        Console.Write("Introduce el limite al que llegar: ")
        limiteSuperior = Console.ReadLine
        fichero.WriteLine("2")
        fichero.WriteLine("3")
        While candidato <= limiteSuperior
            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
                fichero.WriteLine(candidato)
            End If
            candidato += 2
            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
                fichero.WriteLine(candidato)
            End If
            candidato += 4
        End While
        fichero.Write("Hora de comienzo:")
        fichero.WriteLine(horaComienzo)
        fichero.WriteLine("Hora de final:")
        fichero.WriteLine(Now)
        fichero.Close()
        Console.Write("Fin")
        Console.Read()
    End Sub
End Module

Como cazar un primo gigante

Este fin de semana imposible por problemas con la agenda (mañana quedada en montain bike, comida familiar, cena con amigos, fiestas de un pueblo, el domingo a recuperarse y otra comida familiar)

Pero a partir del domingo por la tarde, a la caza de un primo grande. Aviso que no va a ser el más grande. Nos conformaremos con alguno que haya sido considerado muy grande en el pasado.

¿Cómo lo vamos a hacer?

Primero ir a la web que mejor información tiene sobre esta cosas. Además parece que hay un montón de locos que se dedican a publicar en este sitio los primos más grandes conocidos que van obteniendo. El sitio es este: http://primes.utm.edu/notes/by_year.html#table2.

En el enlace concreto que he puesto aparecen los primos más grandes descubiertos a lo largo de la historia.

1.-Antes de la era de las computadoras.

Desde antes de las computadoras los números de Mersenne (amigo de Fermat) han tenido gran importancia. Al principio hubo un error histórico consistente en pensar que todos los números de Mersenne eran primos. Muchos si, y era un buen método para obtener primos grandes, pero no todos.

En la Wikipedia tenemos la definición de “número primo de Mersenne”. Cuidado, se refiere a aquellos números de Mersenne que son primos porque todos no lo son.

También conviene leer su biografía.

Voy a tirar de un librito de matemáticas para centrarnos más…
En el año 1644 el monje francés Marin Mersenne publica “Cogitata Physica-Mathematica” en el que afirma que los números Mn = (2 ^ n) -1 son primos para 2,3,5,7,13,17,19,31,67,127,257 y son compuestos para el resto de valores de n menores que 257.

En 1947 se descubrió que M67 y M257 no son primos. Y también que M61, M89 y M107 si lo eran. Esto es lo de menos.

Algunos pensaron que Mn es primo siempre que n sea primo pero fallaron porque por ejemplo M11 no es primo.

Otros han pensado que Mn es primo cuando n sea un número de Mersenne, pero tampoco funciona porque cuando se llega a M13 falla.

2.-En la era de la electrónica.
Aquí es donde estamos. La lista de primos grandes que nos muestran empieza en 1951 y llega al 2006. Vemos que casi todos son números de Mersenne.

¿Qué tienen de especial estos números?

En esta página http://primes.utm.edu/prove/prove3_2.html#test nos dan la explicación matemática que nos aseguran que es muy ¿divertida? A mi en estos momentos me supera así que prefiero no seguir por aquí. Si que nos quedamos con algo muy importante: All of the Mersenne records were found using the Lucas-Lehmer test.

Ahora buscamos ese test en Wikipedia que nos lo explicará de forma muy sencilla: http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer
De todas formas el test tal y como viene es lioso porque no se ven los números de Mersenne.

Entonces vemos que hay una entrada más apropiada con nombre "Test de Lucas-Lehmer para números de Mersenne":
http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer_para_n%C3%BAmeros_de_Mersenne

Ahora ya lo vemos todo más claro. Hay que generar una sucesión.
Los primeros términos de esta sucesión son 4, 14, 194, 37634, ...
En un sitio llamado OEIS (The On-Line Encyclopedia of Integer Sequences) identifican la secuencia como "A003010": http://www.research.att.com/~njas/sequences/A003010

Al final lo que tenemos es lo siguiente:



Lo que haremos es esto:

1. Buscar un Mn grande con ayuda de algún método de exponenciación binaria.
2. Comprobar si Mn es primo calculando previamente la secuencia para n-2.
   

Nota: Si hay un campeón que quiera comprobar la demostración del test de Lucas-Lehmer que haga clic aquí

Gran avance

Bueno, ante la desesperación de tener que esperar más de 2 horas para obtener los primos que hay entre el número 1 y el 100.000.000 la solución ha sido convertir el programa Visual Basic a C++.

De esta forma los tiempos se han reducido un montón.

Con el límite en 100.000 tardabamos 3 segundos.
Ahora esos 9592 primos se logran en menos de 1 segundo.

Con el límite en 1.000.000 se tardaba 14 segundos. Ahora se consiguen los 78.498 primos en unos 2 segundos.

Poniendo el límite en 100.000.000, se lograban los 5.761.455 primos en 2 horas 14 minutos 58 segundos y ahora los conseguimos los 5761455 primos en 14 minutos y 26 segundos.

Cambios en el programa
El programa no lo he hecho exactamente igual. En lugar de usar formularios Windows he creado un proyecto de consola Win32. Por lo tanto no hay un cuadro de lista donde acumular los primos. Lo que he hecho es generar un fichero de texto donde se van guardando los primos que se descubren. Esto es algo que lógicamente hace el programa muchísimo más lento que si no los almacenáramos.

Para saber lo que tarda el programa en obtener esos primos he utilizado la función clock() de la librería estándar. El tiempo de ejecución se almacena al final del fichero de texto.
Lo que ocurre es que para ejecuciones rápidas de pocos segundos esta función no va del todo bien. En lugar de 1 segundo indica que ha necesitado 8 segundos. En lugar de 2 segundos indica 25. En cambio cuando la ejecución ha tardado 14 minutos y 26 segundos ha clavado el tiempo.

Como curiosidad, indicar que los 5.761.455 primos obtenidos, en el fichero de texto ocupan 55.528Kb.

Sin más hay va el programita en C++:

#include "stdafx.h"
#include 
#include 
using namespace std;
#include 

int _tmain(int argc, _TCHAR* argv[])
{
    ofstream fs("primos.txt");

 clock_t clock(void);

 int candidato = 5;
 int pruebaDivisor;
 int esPrimo;
    int numPrimos = 2;
 int limiteSuperior;

 printf("Introduce el limite al que llegar: ");
 scanf("%d",&limiteSuperior);

    fs << 2 << endl;
 fs << 3 << endl;
    while(candidato <= limiteSuperior)
 {
  pruebaDivisor = 5;
        esPrimo = 1;
            while(pruebaDivisor * pruebaDivisor <= candidato)
   {
                if(candidato % pruebaDivisor == 0)
    {
                    esPrimo = 0;
                    break;
    }
                pruebaDivisor += 2;
   }
   if(esPrimo == 1)
    fs << candidato << endl;

            candidato += 2;
            
   pruebaDivisor = 5;
            esPrimo = 1;
            while(pruebaDivisor * pruebaDivisor <= candidato)
   {
                if((candidato % pruebaDivisor) == 0)
    {
                    esPrimo = 0;
                    break;
    }
                pruebaDivisor += 2;
   }
   if(esPrimo == 1)
    fs << candidato << endl;

            candidato += 4;
  }
 
 fs << "Desde el inicio: " << clock()/CLK_TCK << " segundos\n";

 fs.close();
 cin.get();
  return 0;
}

Pequeña variación

Ayer probé un pequeño cambio en el programita VB.NET.
Se trata de que en lugar de usar una variable para saber si toca sumar 2 y luego 4, hacer esas operaciones de forma secuencial duplicando código.

Es verdad que el programa ahora es más feo y que algunas veces se sobrepasa el límite que ha fijado el usuario, pero el código es ligeramente más rápido así que yo creo que hay que darlo por bueno.

Los tiempos son:

Para un límite fijado en 100.000.000 la versión anterior tardaba 2 horas 17 minutos 26 segundos y ahora tarda 2 horas 14 minutos 58 segundos.

        Dim candidato As Long = 5
        Dim pruebaDivisor As Long
        Dim esPrimo As Boolean
        Dim numPrimos As Long = 2
        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
            candidato += 2
            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
            candidato += 4
        End While
        lstPrimos.EndUpdate()
        Me.lblFIn.Text = Now

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

Esos revoltosos números primos

Puede que alguien haya tenido una genial idea para ser el campeón de los números primos.

Imaginaros que observando los numeros generados con el programita vemos un patrón que siguen algunos números primos. Si conseguimos una pauta que asegure que los números que lo cumplan son primos...fácilmente podriamos superar el mayor número primo conocido.

Pongo un ejemplo:

Con el programa podemos ver que el número 97 es primo.
El número 907 también es primo.
El 9907 también es primo.
Y el 99907 es primo.
También son primos el 999907 y el 9999907.

Pero ¡mierda!, 99999907 NO ES PRIMO. Mi gozo en un pozo.

Ahora lo más seguro es que nos entre la curiosidad sobre el divisor de ese número tan raro.

Venga, no hay que ser tan vago. Disfruta un poco programando las 4 líneas para saberlo.

Para los vagonetis mañana el programita en vb.net.

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

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

Ante todo disculpas

¡Que pasada! Escribí mi último post el 19 de julio y encima lo dejé sin terminar. Realmente se me han acumulado un montón de temas y no he podido dedicar ni tiempo.

Respecto al tema del último post, si mal no recuerdo era como poder tratar enteros gigantes. Concretamente vamos a hacer un programita que nos diga si un entero es primo o no. Luego buscaremos el mayor número primo descubierto y lo meteremos al programa.

Lo más interesante va a ser dejar el programa en ejecución y ver que pasa. ¿Lo veremos terminar? Yo creo que antes perderé la paciencia.

Empecemos con el programa. He decidido hacerlo en Visual Basic .NET. ¿Por qué? Bueno, creo que es el lenguaje en el que mejor me manejo sobre todo por la ayuda integrada en el visual studio. Más adelante igual lo pasamos a otro lenguaje y compararemos la velocidad de ejecución.

En cuanto a como almacenar un número gigante, es obvio que no podemos utilizar los tipos enteros del lenguaje. Sea cual sea el lenguaje a utilizar todos son tipos limitados. Tendremos que utilizar el tipo string y almacenar el número como una cadena de caracteres alfanumérica.

Bueno, esta vez espero publicar el solucionario más pronto que tarde.

Saludos.