Cincuenta millones de números primos
En la página The first fifty million primes [1] se pueden descargar los primeros 50 millones de números primos. Viene en 50 ficheros de texto comprimidos con ZIP.
Cada fichero tiene un millón de números primos distribuidos en varias columnas. Este formato va bien para echar un vistazo pero no para automatización. Necesito un sólo número primo por línea. Para realizar la transformación usé el código de scan.php
El primer número primo es el 2 y el último el 982451653 (casi un millardo)
El presente código puede factorizar desde el número 1 hasta el cuadrado del último primo, es decir, hasta 965211250482432409 (casi un trillón)
Generador de primos
Otra opción es generar nuestro propio archivo de primos mediante el código PrimeGenerator.java.
Los tiempos de cálculo son los siguientes:
Nº de primos | Último primo | Tiempo | Nº bytes | md5sum |
---|---|---|---|---|
1 | 2 | 0,006 seg | 2 | |
10 | 29 | 0,033 seg | 26 | b4ecb8c52d4e27c810a39c03db12398f |
100 | 541 | 0,077 seg | 371 | d15b7c0eea41a2f13a008e88d4d16bf7 |
1000 | 7919 | 0,441 seg | 4803 | 0c6eef860dd89d8321d0921b2eda2446 |
10000 | 104729 | 4,642 seg | 58982 | 667f99ebe87fc49cc2412234845f61bc |
100000 | 1299709 | 52,882 seg | 710484 | bfb9d413506195fa7c731b57e16e1901 |
1000000 | 15485863 | 665,190 seg | 8245905 | d21960bf14feb65190e5540c2996d0df |
Lectura secuencial de los números primos
Para realizar la factorización necesito acceder secuencialmente a los números primos contenidos en los ficheros
prime1.txt
, prime2.txt
... prime50.txt
.
Para ello cree una clase que va abriendo y cerrando los ficheros a medida que se va leyendo los primos de uno en uno.
-
Código PHP
Mediante la clase Primes.php podemos realizar el siguiente bucle:
$primes = new Primes();
while ($primes->hasNext()) {
echo $primes->next();
}
$primes->close(); -
Código Java
Mediante la clase Primes.java el bucle queda como:
Primes primes = new Primes();
while (primes.hasNext()) {
int prime = primes.next();
System.out.println(prime);
}
primes.close(); -
Código C++
Mediante la clase Primes.cpp el bucle es así:
Primes primes;
while (primes.hasNext()) {
long prime = primes.next();
cout << prime << "\n";
}
primes.close();
Comparativa: PHP vs Java vs C++
Cálculo del tiempo de ejecución para leer todos los primos almacenados en los ficheros:
Comando | Tiempo | Versión |
---|---|---|
$ php TestPrimes.php | 39 segundos | PHP 7.0.22 |
$ javac TestPrimes.java $ java TestPrimes |
11 segundos | OpenJDK 1.8 |
$ g++ TestPrimes.cpp -o TestPrimes.exe $ ./TestPrimes.exe |
10 segundos | g++ 5.4.0 |
Java es mucho más rápido que PHP y prácticamente tan rápido como C++
Factorización de un número grande
-
Código PHP
Método para factorizar en la clase Factoring.php:
/*
Factoriza el número indicado
Desde 1 hasta 965_211_250_482_432_409 (LAST_PRIME^2)
360 --> array(2=>3, 3=>2, 5=>1)
12 --> array(2=>2, 3=>1)
20 --> array(2=>2, 5=>1)
17 --> array(17=>1)
*/
public static function gmpFactoring($number) { // GMP = GNU Multiple Precision
$result = $number;
$root = gmp_sqrt($number);
if (gmp_cmp($number, 0) <= 0) return array(); // Negative or zero
elseif (gmp_cmp($number, 1) == 0) return array(1=>1); // One
elseif (gmp_cmp($root, Primes::LAST_PRIME) > 0) return array(); // Overflow
$primes = new Primes();
$factors = array();
while ($primes->hasNext()) {
$prime = $primes->next();
if (gmp_cmp($result, 1) == 0) break;
elseif (gmp_cmp($prime, $root) > 0) {
$factors[gmp_strval($result)] = 1;
break;
}
$exponent = 0;
for(;;) {
list($quotient, $remainder) = gmp_div_qr($result, $prime);
if (gmp_cmp($remainder, 0) != 0) break;
$exponent++;
$result = $quotient;
$root = gmp_sqrt($result);
if ($exponent > 60) break; // Avoid infinite iterations
}
if ($exponent >= 1) $factors[$prime] = $exponent;
}
$primes->close();
return $factors;
}La biblioteca GMP permite trabajar con números enteros de cualquier longitud.
Se instala con el comando:$ sudo apt-get install php-gmp
-
Código Java
Método para factorizar en la clase Factoring.java:
/*
Factoriza el número indicado
360 --> Map[2:3, 3:2, 5:1]
12 --> Map[2:2, 3:1]
20 --> Map[2:2, 5:1]
17 --> Map[17:1]
*/
public static Map<Long,Byte> factoring(long number) {
long result = number;
long root = (long)Math.sqrt(number);
Map<Long,Byte> factors = new TreeMap<Long,Byte>();
if (number <= 0) return factors; // Negative or zero
else if (number == 1) { factors.put(1L, (byte)1); return factors; } // One
else if (root > Primes.LAST_PRIME) return factors; // Overflow
Primes primes = new Primes();
while (primes.hasNext()) {
long prime = primes.next();
if (result == 1) break;
else if (prime > root) {
factors.put(result, (byte)1);
break;
}
byte exponent = 0;
for(;;) {
long quotient = result / prime;
long remainder = result % prime;
if (remainder != 0) break;
exponent++;
result = quotient;
root = (long)Math.sqrt(result);
if (exponent > 60) break; // Avoid infinite iterations
}
if (exponent >= 1) factors.put(prime, exponent);
}
primes.close();
return factors;
}El tipo
long
en Java utiliza 64 bits. El rango de valores es de ±9 trillones.
Comparativa: PHP vs Java
Tiempo de ejecución para factorizar números de 18 dígitos:
Número
Factores |
$ php TestFactoring.php … |
$ javac TestFactoring.java
$ java TestFactoring … |
---|---|---|
965211250482432409
=9824516532 |
204 segundos | 14 segundos |
888888888888888888
=23×32×7×11×13×19×37×52579×333667 |
0,02 segundos | 0,04 segundos |
614889782588491410
=2×3×5×7×11×13×17×19×23×29×31×37×41×43×47 |
0,00 segundos | 0,01 segundos |
576460752303423488
=259 |
0,00 segundos | 0,01 segundos |
576460752303423487
179951×3203431780337 |
0,47 segundos | 0,15 segundos |
444444444444444440
=23×5×2071723×5363222357 |
0,50 segundos | 0,15 segundos |
394906913903735329
[2]
=394906913903735329 |
140 segundos | 9 segundos |
157486901972400000
=27×36×55×74×113×132 |
0,00 segundos | 0,01 segundos |
133049351085651000
=23×33×53×73×113×133×173 |
0,00 segundos | 0,02 segundos |
123456789123456789
=32×7×11×13×19×3607×3803×52579 |
0,00 segundos | 0,03 segundos |
123456789000000000
=29×32×59×3607×3803 |
0,00 segundos | 0,02 segundos |
100000000000000001
=11×103×4013×21993833369 |
0,04 segundos | 0,05 segundos |
100000000000000000
=217×517 |
0,00 segundos | 0,01 segundos |
El cálculo suele ser instantáneo a menos que haya algún primo muy grande en los factores
Uso de Java a través de PHP
La siguiente función PHP usa Java para realizar el cálculo del factorial
function factoringThroughJava($number) {
$number = escapeshellarg($number);
$result = shell_exec("java Factoring $number");
$result = trim($result, "\n");
return $result;
}
Formulario de factorización
Bot de Telegram
Telegram es una aplicación de mensajería que podemos instalar en nuestro móvil o acceder vía web.telegram.org.
Si abrimos un chat buscando al usuario @matematicas_bot podremos factorizar números de hasta 18 dígitos.
Enlaces
- [1] The first fifty million primes
- primes.utm.edu/lists/small/millions
- [2] 394906913903735329 es un primo de 18 cifras
- mimosa.pntic.mec.es/jgomez53/matema/conocer/primos.htm