¿Cuántos números primos hay dentro de los primeros 100.000 números naturales? La respuesta a esta pregunta nunca me interesó y me sigue sin interesar, pero el método para obtener la respuesta tiene su gracia.

Al leer el libro de Simon Singh «The Code Book«, me ha cautivado la parte en la que describe el descubrimiento del algoritmo de clave pública, que se utiliza hoy día en casi todas las comunicaciones cifradas a través de Internet. Por ejemplo, la seguridad del sistema RSA, basado en números primos, se centra en el esfuerzo que requiere factorizar un número muuuy grande (mayor que 10¹⁰⁰).

Y buceando por la Wikipedia di con el artículo sobre la criba de Eratóstenes, en el que se describe el algoritmo más sencillo, aunque no el más eficiente, para calcular todos los primos por debajo de un número determinado. En este artículo hay código en varios lenguajes mayoritarios, pero se echa en falta la versión en SQL. Así que, señoras y señores, aquí está la implementación del algoritmo que nadie había pedido, utilizando la base de datos SQLite desde Java mediante JDBC (es necesario el driver, que se puede descargar aquí).

Primes.java

[java]
package com.cotrino.primes;

import java.sql.SQLException;

/**
* Prime number calculator using SQL
*
* @author José Cotrino (https://www.cotrino.com)
*/
public class Primes {
static long N = 0;
static long primes = 0;
static boolean fileDB = false;

public Primes() {
DB db;
if (fileDB)
db = new DB("primes.db");
else
db = new DB(":memory:");
db.createTables();
db.massiveInsert(N);
try {
db.executeUpdate("UPDATE tbl_primes SET isPrime=0 "
+ "WHERE id IN "
+ "(SELECT tbl_primes.id*B.id FROM tbl_primes "
+ "INNER JOIN tbl_primes AS B "
+ "ON tbl_primes.id>=B.id AND tbl_primes.id*B.id + " AND B.isPrime=1);");
} catch (SQLException e) {
System.err.println("Calculation failed! " + e);
}
primes = db
.getLong("SELECT COUNT(id) FROM tbl_primes WHERE isPrime=1;");
db.close();
}

public static void main(String[] args) {
if (args.length < 2) {
System.err
.println("Please specify the amount of numbers "
+ "where to search for primes (e.g. 1000) and "
+ "if the DB should be file- or memory-based (true/false).");
System.exit(1);
}
long time = System.currentTimeMillis();
N = Long.parseLong(args[0]);
fileDB = Boolean.parseBoolean(args[1]);
new Primes();
time = System.currentTimeMillis() – time;
long memory = Math
.round(java.lang.Runtime.getRuntime().totalMemory() / 1000000);
System.out
.println("Numbers\t\tPrimes\t\tFileDB\t\tMemory\t\tDuration\n"
+ N + "\t\t" + primes + "\t\t" + fileDB + "\t\t"
+ memory + "MB\t\t" + time + "ms");
}
}
[/java]

DB.java



[java]
package com.cotrino.primes;

import java.sql.*;

/**
*
* SQLite database handler for prime number calculator
* @author José Cotrino
* (https://www.cotrino.com)
*/
public class DB {
private Connection conn;
private Statement stat;

public DB(String databaseName) {
try {
Class.forName("org.sqlite.JDBC");
conn = DriverManager.getConnection("jdbc:sqlite:" + databaseName);
stat = conn.createStatement();
} catch (SQLException e) {
} catch (ClassNotFoundException e) {
}
}

public void executeUpdate(String query) throws SQLException {
stat.executeUpdate(query);
}

public ResultSet executeQuery(String query) throws SQLException {
return stat.executeQuery(query);
}

public long getLong(String query) {
long value = 0;
try {
ResultSet rs = executeQuery(query);
while (rs.next()) {
value = rs.getLong(1);
}
rs.close();
} catch (SQLException e) {
System.err.println("Query failed: " + query);
}
return value;
}

public void massiveInsert(long N) {
try {
PreparedStatement prep = conn
.prepareStatement("INSERT INTO tbl_primes values (?, ?);");
for (long i = 2; i prep.setLong(1, i);
prep.setInt(2, 1);
prep.addBatch();
}
conn.setAutoCommit(false);
prep.executeBatch();
conn.setAutoCommit(true);
} catch (SQLException e) {
System.err.println("Value insertion failed!");
}
}

public void close() {
try {
conn.close();
} catch (SQLException e) {
}
}

public void createTables() {
try {
executeUpdate("DROP TABLE IF EXISTS tbl_primes;");
executeUpdate("CREATE TABLE tbl_primes "
+ "(id INTEGER PRIMARY KEY, isPrime INTEGER);");
} catch (SQLException e) {
System.err.println("Table creation failed!");
}
}
}
[/java]

Una vez compilado y empaquetado, se ejecuta por ejemplo con este comando:
java -jar Primes.jar 100000 false

Estos son los resultados que devuelve este programa en un portátil viejuno con un procesador Pentium M 1.6 GHz y 1 GB de memoria. Hay una diferencia apreciable entre utilizar la base de datos en memoria o en fichero, aunque como la parte fundamental del algoritmo se ejecuta con una sola consulta SQL, las operaciones tienen lugar en memoria.

En los resultados se observa claramente que este método no es lineal y deja de ser útil para números grandes. El número de primos, por cierto, no incluye el ‘1’.

Antes de esta implementación, hice un intento en Perl por el sencillo algoritmo de dividir cada número entre todos los primos anteriores. Aunque la división es una operación más compleja y lenta que la multiplicación (como se utiliza en la criba de Eratóstenes), sin embargo el algoritmo da mejores resultados para números grandes. Aquí se puede ver una gráfica de los segundos que tarda en encontrar cada 10.000 números primos al calcular todos los primos por debajo de 100 millones.

La ejecución tardó 5.929 segundos (1 hora y 39 minutos) y dio como resultado que entre 0 y 100 millones hay 5.761.455 números primos.

prime.pl

[perl]
#!/usr/bin/perl
## Prime number calculator
# @author José Cotrino (https://www.cotrino.com)
#
use strict;
use warnings;
use Benchmark;

[/perl]