Escreva um programa ou função que produz / retorna os primeiros 10000 números primos indexados a prim.

Se chamarmos o ^enésimo primeiro p(n), esta lista será

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

As brechas padrão são proibidas e os métodos de saída padrão são permitidos. Você pode responder com um programa completo, uma função nomeada ou uma função anônima.

MATLAB / oitava, 25 bytes

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

Não é muito mais simples do que isso.

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]

Isso termina com um "erro de índice fora da faixa da lista" depois de imprimir os 10000 números, o que é permitido por padrão .

Usa o método Theorem de Wilson para gerar uma lista ldos primos até o 10000º primo. Em seguida, imprime os números primos com as posições na lista, deslocadas por 1 para indexação zero, até ficarmos sem limites após o 10000º primo -ésimo primo.

Convenientemente, o limite superior de 1366661pode ser estimado como 82e5/6o que é 1366666.6666666667, economizando um carvão animal.

Eu gostaria de um método de loop único, imprimindo números primos indexados à medida que os adicionamos, mas parece ser mais longo.

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

Produz os números primos no formato

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

Explicação

        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&

Função pura retornando a lista.

Haskell, 65 bytes

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

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

Não é muito rápido. Como funciona: pé a lista infinita de números primos (verificando ingenuamente todos os mod x ys por y in [2..x-1]). Pegue os primeiros 10000elementos da lista que você obtém quando 0:p!!(obter o enésimo elemento de p) é mapeado p. Eu tenho que ajustar a lista de números primos de onde eu pego os elementos acrescentando um número (-> 0:), porque a função de índice ( !!) é zero.

PARI / GP, 25 bytes

apply(prime,primes(10^4))

AWK - 129 bytes

... ok ... tempo demais para ganhar pontos por compacidade ... mas talvez consiga ganhar alguma honra pela velocidade?

O xarquivo:

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++}}

Corrida:

$ 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

Legível:

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++
        }
}

O programa calcula um fluxo de números primos usando Lcomo "fita de números" segurando números primos pulando Lpara sinalizar os números próximos já conhecidos por terem um divisor. Esses primos de salto avançam enquanto a "fita de números" Lé cortada número por número desde o início.

Ao cortar a cabeça da fita L[n]vazia, não há um divisor (principal) conhecido.

L[n]manter um valor significa que esse valor é primo e conhecido por dividir n.

Então, encontramos um divisor primo ou um novo primo. O ths prime será avançado para o próximo L[n+m*p]na fita que estiver vazia.

É como a peneira de Eratóstenes "puxada pela garrafa de Klein". Você sempre age no início da fita. Em vez de disparar múltiplos primos pela fita, use os primos já encontrados como cursores que saltam para longe da fita iniciando por várias distâncias de seu próprio valor até encontrar uma posição livre.

Enquanto o loop externo gera uma decisão de prime ou não de prime por loop, os primos encontrados são contados e armazenados Pcomo chave, o valor desse par (chave, valor) não é relevante para o fluxo do programa.

Se a chave deles já estiver iem P( i in P), temos um primo da raça p (p (i)).

Corrida:

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

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

Leve em consideração que esse código não usa tabelas primárias pré-calculadas externas.

Tempo gasto no meu bom e velho Thinkpad T60, então acho que ele merece ser chamado rapidamente.

Testado com mawke gawkno Debian8 / AMD64

CJam, 19

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

Você pode experimentá-lo online , mas precisará de um pouco de paciência: p

Para o registro, o último número é 1366661.

Perl, 55 bytes

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

Usa o módulo @DanaJMath::Prime::Util para perl (carregado com o pragma ntheory). Obtenha com:

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

05AB1E, 7 bytes (não concorrente)

Código:

4°L<Ø<Ø

Experimente online! , note que eu mudei o 4para a 2. Se você tiver muito tempo, poderá 2voltar para 4, mas isso levará uma muito tempo. Eu preciso apertar o algoritmo para isso.

Explicação:

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