11 millones de números primos

[ixMike]

"11 millones de números primos" o "sobre la evolución personal en la programación".

Muy buenas.

Pasaba por aquí, y no he podido evitar dar a conocer un pequeño proyecto sin importancia al que me he estado dedicando últimamente. Bueno, tendría que contaros la historia, ¡y es que a 11 millones de números primos no se llega así como así! Y menos con los pocos conocimientos de programación con los que empecé.

Procedure ContarHistoria(AQuien: TDestinatario);
begin
If AQuien=GenteDelClubDelphi then
begin
PedirAlgo('¡Camarero, una ronda y un platico de jamón y queso!');
SoltarElRollo('
En fin, "once upon a time in my home", cuando llevaba poco tiempo en el fascinante mundo de la programación en Delphi (bueno, la programación en general) se me ocurrió hacer un simple programa que pudiera descomponer un número en sus factores primos. Pero entonces pensé «Necesitaré una lista de números primos», así que al programa tuve que añadirle un generador de números primos. Le indicabas un rango de números (del 2 al 1000, por ejemplo), e iba comprobando si todos los números comprendidos en ese rango eran primos. Observé que me salió bastante bien: el rango 2-1000 me lo sacaba en muy pocos segundos. Los números se almacenaban en un TMemo, y yo me encargaba de añadirlos a un archivo llamado "primos.txt". Después, cada vez que abría el programa, "primos.txt" se cargaba en otro TMemo (para hacerlo bonito, más que nada), y esa era la lista de primos a la que accedía el descomponedor en factores primos.

Todo iba "bien", hasta que, claro, no tenía suficientes números primos, a la hora de calcular descomposiciones de números muy grandes. Así que tuve que agrandar la lista de números primos, pero a partir del 100.000, el cálculo empezaba a resultar demasiado lento. Y ahí fue donde realicé las primeras optimizaciones al código: dejé de comprobar los números pares (pues obviamente no son primos), a la hora de comprobarlos tampoco probaba con divisores pares (pues si el número a comprobar no era par pues perdía el tiempo con esos cálculos). Además descubrí el "Memo.Lines.BeginUpdate". ¡Violá! De repente tenía ante mí un código que me pareció tremendamente rápido. Empecé a calcular primos hasta que, cuando iba por el rango 2.000.000-2.100.000 (me parece recordar) la cosa se volvía otra vez lenta: tardaba alrededor de un minuto en calcularlo.

A partir de ahí la cosa quedó un poco abandonada, si eso de vez en cuando hacía crecer el rango 100.000 más, sacando unos pocos miles de números primos.

Pero hace poco, anteayer concretamente, lo vi y me dije «¿Y si aplico todo lo que he aprendido y realizado estos años para optimizar el código al máximo?». Y así hice. Primero pasé del TStringList al TIntegers, un objeto que creé hace tiempo con otra necesidad, y que se puede deducir qué es y cómo funciona (y si no, pues lo digo, es como TStringList, pero en vez de Strings almacena Integers). Además me dejé de interfaz gráfica (porque llevo tres días sin mouse y el IDE de Delphi sin mouse...). Así que creaba un .dpr vacío, y empezaba el programa de cero. La entrada y salida de datos la hacía con parámetros (que son fáciles de utilizar con la consola o teniendo instalado FileMenuTools).

Lo primero fue crear dos programas, el ttn.exe y el ntt.exe, que transforman un archivo de texto con números listados en un archivo con números listados (que es el que puede cargar y guarda el TIntegers). Después optimicé un poco más el código para comprobar si un número es primo o no (antes comprobaba si era divisible por todos los números impares hasta su mitad, pero matemáticamente sólo es necesaria esta comprobación hasta llegar a su raíz cuadrada truncada). Además desarrollé otro método (que con el TStringList resultaba lentísimo), y es comprobar que el número no es divisible por ningún número primo menor que su raíz cuadrada truncada.

Pero lo de crear un programa que creara primos en un rango ya no me era suficiente, y realicé otro que aumenta el rango de los primos ya calculados. Por ejemplo, ahora que ya había calculado primos del 1 al 3.500.000, pues con sólo decirle que aumentara el rango en 500.000, ya tenía los primos del 1 al 4.000.000, pero ¡ya!, porque no tardó casi nada en realizar el cálculo. Así que fui probando (esto ya ayer por la tarde) y... en unos pocos minutos... ¡ya tenía 11 millones y pico de números primos! Los que van del 1 al 200.000.000.
');
end;
end;

Si cuando empecé con la idea de descomponer un número en sus factores primos alguien me hubiese dicho que en un par de años (o tres) habría realizado un programa que va por comandos, que utiliza un objeto tan potente como TStringList pero que funciona con Integers y que está hecho por mí, y que los primeros 11 millones de números primos se calcularían en unos 10 minutos, no sé cómo habría reaccionado. Supongo que no me lo habría creído. O habría pensado que habría necesitado miles de líneas de código, ¡cuando sólo tiene unas 250!. Y eso que me dedico a la programación por afición (bueno, ahora en la universidad doy C en clase de informática).

¡Ah! Casi se me olvida. Subo el código de los programas, con una breve explicación de su funcionamiento, y una lista de los primeros números primos (los que puedo decir de cabeza) en formato lista de texto y en formato lista numérica. ¡A ver si alguien se anima y lo optimiza un poco más!.

Saludos a todos (y espero no haberos aburrido con la historia).