¿Alguien sabe de algun programa que me permita calcular números primos por ejemplo del 1 al billón?

Pensaría que lo mejor es que tú mismo escribieras el programa. De paso podrías probar técnicas de codificación.

Lo primero, para probar si un número es primo, es intentar dividirlo por todos los números anteriores. Escribiré mi algoritmo en un pseudo C.

bool es_primo(long n) 
  { 
    for(long i=2; i 
      { 
        if( n%i == 0 ) return false; 
      } 
    return true; 
  } 

Asumo aquí que long es suficientemente grande para almacenar números del orden de un billón (10121012), para lo cual requiero de 40 bits. Dependiendo el sistema, long puede ser 32 bits o 64 bits; en el primer caso tendría problemas y tengo que hacer el algoritmo más complejo. Si programo en Python no tengo que preocuparme por el tamaño.

Otro problema con este algoritmo, es que si quiero evaluar todos los primos desde n=2n=2 hasta n≤1012n≤1012, tendré que repetir el llamado a función casi un billón de veces, y dentro de cada llamado, estoy iterando hasta n−3n−3 veces dentro de la función. La complejidad es cuadrática, aunque la mayor parte de los llamados a la función devuelve muy rápido (la mitad de las veces, tengo una respuesta cuando i=2i=2).

Una pequeña mejora, que reduce a la mitad las pruebas, es que si nn es impar, sólo pruebo con divisores impares. Si 22 no divide a nn, tampoco lo hará 44, ni 66, ni 88, ni 1010, etc. Así que primero pruebo si es par, y luego busco entre los impares:

bool es_primo(long n) 
  { 
    if( n==2 ) return true;       /* 2 siempre es primo */ 
    if( n%2 == 0 ) return false;  /* si n es par, no es primo */ 
    for(long i=3; i 
      { 
        if( n%i == 0 ) return false; 
      } 
    return true; 
  } 

Aquí me ahorro varias pruebas innecesarias, pero la complejidad del algoritmo es aún alta.

La siguiente optimización es la siguiente. Si ii divide a nn, entonces existe un número pp, tal que i×p=ni×p=n. Pero i>n−−√i>n, entonces p<n−−√p; ya que p≥n−−√p≥n, entonces i×p>n−−√×n−−√i×p>n×n y i×p>ni×p>n, lo que contradice la igualdad. Así que si nn tiene un divisor propio no trivial, entonces nn tiene un divisor menor o igual a su raíz cuadrada.

Nuestro algoritmo optimizado va entonces así:

bool es_primo(long n) 
  { 
    if( n==2 ) return true;      /* 2 siempre es primo */ 
    if( n%2 == 0 ) return false; /* si n es par, no es primo */ 
    for(long i=3; i*i<=n; i+=2 ) /* pruebo impares hasta raiz(n) */ 
      { 
        if( n%i == 0 ) return false; 
      } 
    return true; 
  } 

La complejidad del algoritmo bajó de nn a n−−√n para cada nn, o de n2n2 a n112n112 para buscar todos los números.

La siguiente optimización. Así como descartamos probar los pares diferentes a 2, podemos descartar los múltiplos impares de 3, y los múltiplos de 5, y de 7… En fin, podemos descartar todos los números no primos, y probar sólo con los números primos menores o iguales a n−−√n.

long primos[BUFFER_SIZE]; 
 
bool es_primo(long n) 
  { 
    for(int i=0; primos[i]*primos[i]<=n; i++) { 
      { 
        if( n%primos[i] == 0) return false; 
      } 
    return true; 
  } 

Para que esto funcione se supone que primos debe tener ya todos los posibles números primos hasta n−−√n. Así que necesitamos llenar el vector, o conocer los primos. Por ejemplo si sólo quiero probar los números hasta el 100 para ver si son primos tendría que definir a primos como:

long primos[5] = { 2, 3, 5, 7, 11 }; 

(Nota, con el 11 no se probará divisibilidad, pero es necesario como condición de cierre en el for.)

Pero necesito conocer entonces cuales son los números primos. Así que la siguiente mejora es buscar los números primos e irlos guardando.

long primos[BUFFER_SIZE]; 
 
bool es_primo(long n) 
  { 
    for(int i=0; primos[i]*primos[i]<=n; i++) { 
      { 
        if( n%primos[i] == 0) return false; 
      } 
    return true; 
  } 
 
long buscar_primos(long max) 
  { 
    long i=0; 
    for(long n=2; n 
      { 
        if(es_primo(n)) 
          { 
            primos[i++] = n; 
          } 
      } 
  } 

Ahora, nuestro programa principal puede ser algo como esto:

void main() 
  { 
    long m = buscar_primos(1000000000000l); 
    printf("Hay %ld primos antes del billón\n", m); 
    printf("Estos son:\n"); 
    for(long p=0; p 
      { 
        printf("%13ld\n", p); 
      } 
  } 

Sin embargo este programa tiene todavía un problema grande: memoria.

Lo primero es que necesito que el vector de primos sea lo suficientemente grande. En principio podría asegurar que si BUFFER_SIZE es un billón, no tendré problemas. Pero para ello necesito una memoria que almacene un billón de números. Dado que cada número long de 64 bits me ocupa 8 octetos, necesito casi 8 TB (terabyte) de memoria sólo para almacenar el arreglo. Y eso es irreal con la tecnología actual.

Pero no necesitamos un billón. Puedo lograr un estimado de cuantos números primos hay entre 1 y un billón, utilizando el teorema de densidad de los números primos, y encuentro que serán algo menos de 36.200 millones de números primos, y para almacenarlos me bastan 270 GB (gigabytes).

Esto es aún mucha memoria. Sin embargo, puedo optimizar mejor el algoritmo. La razón del vector es almacenar los primos menores o iguales a n−−√n, donde nn es el valor que quiero saber si es primo o no. Si voy a buscar todos los primos menores o iguales a un billón, necesito almacenar los primos menores o iguales a un millón. Aquí puedo hacer dos cosas. Primero, ya no necesito almacenar un billón de números, o 36 mil millones, sino que son sólo un millón (tope), o algo menos de 72.400 primos. Adicionalmente necesito sólo 20 bits para almacenar al mayor de esos números primos, así que puedo utilizar enteros de 32 bits, que me ocupan sólo 4 octetos. La memoria que necesito, por lo tanto, es de 283 kB (kilobytes). Esto ya es razonable en un computador casero moderno.

Sin embargo, no puedo usar el truco de almacenar todos los primos encontrados e imprimirlos luego.

Así que el programa final sería el siguiente:

#include  
#include  
#define BUFFER_SIZE 72400 
 
int32_t primos[BUFFER_SIZE]; 
int max_idx=0; 
 
int es_primo(int64_t n) 
  { 
    int i; 
    int32_t raiz = (int32_t)sqrt((double)n); 
    for( i=0; i 
      { 
        if( n % (int64_t)primos[i] == 0 ) return FALSE; 
      } 
    if(max_idx < BUFFER_SIZE) 
      { 
        primos[max_idx] = n; 
        max_idx++; 
      } 
    return TRUE; 
  } 
 
void main() 
  { 
    int64_t n; 
    int c=0; 
    printf("Los primos antes del billón son:\n"); 
    for( n=2; n<1000000000000l; n++ ) 
      { 
        if( es_primo(n) ) 
          { 
             printf("%13ld\n", n); 
             c++; 
          } 
      } 
    printf("Para un total de %d números primos.\n", c); 
  } 

No garantizo que el programa funcione, ni que sea rápido. Igual este programa imprimirá en pantalla más de 36 mil millones de números, de los cuales más de 32 mil millones tienen 12 cifras. Si en lugar de pantalla, redireccionas todo a un archivo de texto, será un archivo de 472 GB de tamaño (asegúrate de tener medio tera de disco libre). Si redireccionas a una impresora que imprime 60 líneas por página, serán 600 millones de páginas. Si imprime 60 páginas por minuto, serán 7 mil días imprimiendo (20 años). (si imprimes a varias columnas, podrían ser 6 columnas y durar 3 años y medio imprimiendo.)

Usé C en el ejemplo para mostrar los problemas de memoria que se presentan en este tipo de programas. Otros lenguajes de programación esconden esos problemas (el programador no tiene que pensar en ellos a detalle) pero esos problemas están ahí.

Es posible hacer algunas optimizaciones adicionales, pero los problemas básicos están ahí.

P.D. (edición)
Probé el programa hasta 10 millones y funciona. Tarda 8 segundos en ejecutarse en mi PC si se redirecciona a un archivo (el cual mide 9 MB) y me arroja 664.579 primos entre 2 y 9.999.991 .

Hasta 100 millones, tarda 150 segundos, el archivo final mide 80 MB
y me arroja 5.761.455 primos entre 2 y 99.999.989.