«

»

Feb 02 2009

Calcular números primos con SQL

¿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 10100).

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

package com.cotrino.primes;

import java.sql.SQLException;

/**
 * Prime number calculator using SQL
 *
 * @author José Cotrino (http://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");
	}
}

DB.java

package com.cotrino.primes;

import java.sql.*;

/**
 *
 * SQLite database handler for prime number calculator
 * @author José Cotrino
 * (http://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!");
		}
	}
}


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.

Máximo numero Primos Fichero/Memoria Uso de memoria Duración
100 25 memoria 5MB 180ms
100 25 fichero 5MB 711ms
1.000 168 memoria 5MB 221ms
1.000 168 fichero 5MB 1042ms
10.000 1229 memoria 5MB 761ms
10.000 1229 fichero 5MB 1753ms
100.000 9592 memoria 6MB 15283ms (15 sec)
100.000 9592 fichero 6MB 18018ms (18 sec)
1.000.000 78498 memoria 58MB 1209350ms (20 min)
1.000.000 78498 fichero 58MB 1303905ms (21 min)

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

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

open( OUT,  ">primes.txt" );
open( STAT, ">primes_stat.txt" );
my $t0 = new Benchmark;

# first primes are 1, 2, 3, 5, 7...
# we will skip multiples of 1, 2 & 5 using other methods, not dividing
my @list = ( 3, 7 );

# just for statistics purposes
my $n             = 0;
my $m             = 0;
my $previousTimer = new Benchmark;
my $currentTimer;

my $i = 11;
while ( $i < 100000000 ) {
	my $isPrime = 1;
	my $i_text  = $i . "";

	# avoid multiples of 5
	if ( $i_text =~ m/5$/ ) {
		$isPrime = 0;
	}
	else {
		my $sqrt = sqrt($i);

		# divide $i against all primes lower or equal than sqrt($i)
		for (
			my $j = 0 ;
			$j < scalar(@list) and $isPrime == 1 and $list[$j] <= $sqrt ;
			$j++
		  )
		{
			if ( $i % $list[$j] == 0 ) {
				$isPrime = 0;
			}
		}
	}

	if ( $isPrime == 1 ) {
		push @list, $i;
		print OUT "$i ";

		# count the time it takes to calculate each 10000 prime numbers
		$n++;
		if ( $n >= 10000 ) {
			$n = 0;
			$m++;
			$currentTimer = new Benchmark;
			if ( timestr( timediff( $currentTimer, $previousTimer ) ) =~
				m/^(.+)\s+/ )
			{
				print STAT $m . " " . $1 . "\n";
			}
			$previousTimer = $currentTimer;
		}
	}
	$i += 2; # avoid multiples of 2
}
my $t1 = new Benchmark;
my $td = timediff( $t1, $t0 );
print "Execution took:", timestr($td), "\n";
print scalar(@list) . " numbers found\n";
close(OUT);
close(STAT);

system("gnuplot plot.cfg");

Artículos relacionados:

FacebookRedditMeneameotros