Escriba un programa o función que genere / devuelva los primeros 10000 números primos indexados con números primos.

Si llamamos a la ^enésima prima p(n), esta lista es

3, 5, 11, 17, 31, 41, 59 ... 1366661

porque

p(p(1)) = p(2) = 3
p(p(2)) = p(3) = 5
p(p(3)) = p(5) = 11
p(p(4)) = p(7) = 17
...
p(p(10000)) = p(104729) = 1366661

Las lagunas estándar están prohibidas y los métodos de salida estándar están permitidos. Puede responder con un programa completo, una función con nombre o una función anónima.

MATLAB / Octave, 25 bytes

p=primes(2e6)
p(p(1:1e4))

No es mucho más sencillo que esto.

Python, 72 bytes

P=p=1;l=[]
while p<82e5/6:l+=P%p*[p];P*=p*p;p+=1
for x in l:print l[x-1]

Esto termina con un "error de índice de lista fuera de rango" después de imprimir los números 10000, que está permitido de manera predeterminada .

Utiliza el método del Teorema de Wilson para generar una lista lde los números primos hasta el número 10000. Luego, imprime los números primos con las posiciones en la lista, desplazadas por 1 para la indexación cero, hasta que nos quedemos sin límites después del número 10000.

Convenientemente, el límite superior de 1366661se puede estimar como lo 82e5/6que es 1366666.6666666667, ahorrando un carbón.

Me gustaría un método de bucle único, que imprima números primos indexados a medida que los agreguemos, pero parece ser más largo.

P=p=1;l=[]
while p<104730:
 l+=P%p*[p]
 if len(l)in P%p*l:print p
 P*=p*p;p+=1

J, 11 bytes

p:<:p:i.1e4

Emite los primos en el formato

3 5 11 17 31 41 59 67 83 109 127 ...

Explicación

        1e4  Fancy name for 10000
      i.     Integers from 0 to 9999
    p:       Index into primes: this gives 2 3 5 7 11 ...
  <:         Decrement each prime (J arrays are 0-based)
p:           Index into primes again

Mathematica, 26 25 23 bytes

Prime@Prime@Range@1*^4&

Función pura que devuelve la lista.

Haskell, 65 bytes

p=[x|x<-[2..],all((>0).mod x)[2..x-1]]
f=take 10000$map((0:p)!!)p

Salidas: [3,5,11,17,31,41,59,67,83,109,127.....<five hours later>...,1366661]

No muy rapido. Cómo funciona: pes la lista infinita de primos (ingenuamente verificando todos los mod x ys para y en [2..x-1]). Tome los primeros 10000elementos de la lista que obtiene cuando se asigna 0:p!!(obtener el enésimo elemento de p) p. Tengo que ajustar la lista de números primos de donde tomo los elementos anteponiendo un número (-> 0:), porque la función de índice ( !!) está basada en cero.

PARI / GP, 25 bytes

apply(prime,primes(10^4))

AWK - 129 bytes

... bueno ... demasiado tiempo para ganar puntos por compacidad ... pero ¿tal vez pueda ganar algo de honor por la velocidad?

El xarchivo:

BEGIN{n=2;i=0;while(n<1366662){if(n in L){p=L[n];del L[n]}else{P[p=n]=++i;if(i in P)print n}j=n+p;while(j in L)j=j+p;L[j]=p;n++}}

Corriendo:

$ awk -f x | nl | tail
  9991  1365913
  9992  1365983
  9993  1366019
  9994  1366187
  9995  1366327
  9996  1366433
  9997  1366483
  9998  1366531
  9999  1366609
 10000  1366661

Legible:

BEGIN {
        n=2
        i=0
        while( n<1366662 ) {
                if( n in L ) {
                        p=L[n]
                        del L[n]
                } else {
                        P[p=n]=++i
                        if( i in P ) print n
                }
                j=n+p
                while( j in L ) j=j+p
                L[j]=p
                n++
        }
}

El programa calcula una secuencia de números primos utilizando Lcomo "cinta de números" que contiene números primos encontrados saltando Lpara marcar los números cercanos que ya se sabe que tienen un divisor. Estos números primos saltantes avanzarán mientras la "cinta de números" Lse corta número por número desde su comienzo.

Si se corta el cabezal de la cinta al L[n]estar vacío, no hay divisor (primario) conocido.

L[n]mantener un valor significa que este valor es primo y se sabe que divide n.

Entonces, hemos encontrado un divisor primo o un nuevo primo. Luego, este primer avance se avanzará al siguiente L[n+m*p]en la cinta que se encuentre vacía.

Esto es como el Tamiz de Eratóstenes "tirado a través de una botella de Klein". Siempre actúas en el inicio de la cinta. En lugar de disparar múltiplos de primos a través de la cinta, usted usa los primos que ya se encuentran como cursores que saltan del inicio de la cinta por múltiples distancias de su propio valor hasta que se encuentra una posición libre.

Si bien el ciclo externo genera una decisión principal o no primaria por ciclo, los números primos encontrados se cuentan y almacenan Pcomo clave, el valor de este par (clave, valor) no es relevante para el flujo del programa.

Si su clave ya iestá en P( i in P), tenemos un primo de la raza p (p (i)).

Corriendo:

$ time awk -f x.awk | wc -l
10000

real    0m3.675s
user    0m3.612s
sys     0m0.052s

Tenga en cuenta que este código no utiliza tablas primas precalculadas externas.

Tiempo empleado en mi viejo Thinkpad T60, así que creo que merece ser llamado rápido.

Probado con mawky gawken Debian8 / AMD64

CJam, 19

3D#{mp},_1e4<:(\f=p

Puedes probarlo en línea , pero necesitarás un poco de paciencia: p

Para el registro, el último número es 1366661.

Perl, 55 bytes

use ntheory':all';forprimes{print nth_prime$_,$/}104729

Utiliza el módulo de @DanaJMath::Prime::Util para perl (cargado con el pragma ntheory). Consíguelo con:

cpan install Math::Prime::Util
cpan install Math::Prime::Util::GMP

05AB1E, 7 bytes (no competitivos)

Código:

4°L<Ø<Ø

Pruébalo en línea! , tenga en cuenta que he cambiado el 4a 2. Si tiene mucho tiempo, puede cambiar la 2parte de atrás 4, pero esto llevará mucho tiempo. Necesito ajustar el algoritmo para esto.

Explicación:

4°       # Push 10000 (10 ^ 4)
  L      # Create the list [1 ... 10000]
   <     # Decrement on every element, [0 ... 9999]
    Ø    # Compute the nth prime
     <   # Decrement on every element
      Ø  # Compute the nth prime