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:

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:

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:

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