Factorizar números de teléfono en números primos

Código en Java y PHP para poder factorizar números grandes como teléfonos en el menor tiempo posible

5 elevado a 2 por 7 por 11 elevado a 3

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 primoTiempoNº bytesmd5sum
120,006 seg2
10290,033 seg26b4ecb8c52d4e27c810a39c03db12398f
1005410,077 seg371d15b7c0eea41a2f13a008e88d4d16bf7
100079190,441 seg48030c6eef860dd89d8321d0921b2eda2446
100001047294,642 seg58982667f99ebe87fc49cc2412234845f61bc
100000129970952,882 seg710484bfb9d413506195fa7c731b57e16e1901
100000015485863665,190 seg8245905d21960bf14feb65190e5540c2996d0df

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:

ComandoTiempoVersió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

Comentarios

Proinf.net, ©2003-2018 ci 3.1.9 (CC) Esta obra está bajo una licencia de Creative Commons Este software está sujeto a la CC-GNU GPL