Écrivez un programme ou une fonction qui génère / renvoie les 10000 premiers nombres premiers indexés.

Si nous appelons le n ^e premier p(n), cette liste est

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

car

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

Les failles standard sont interdites et les méthodes de sortie standard sont autorisées. Vous pouvez répondre avec un programme complet, une fonction nommée ou une fonction anonyme.

MATLAB / Octave, 25 octets

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

Cela ne devient pas beaucoup plus simple que cela.

Python, 72 octets

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]

Cela se termine par une "erreur d'index de liste hors plage" après l'impression des 10 000 numéros, ce qui est autorisé par défaut .

Utilise la méthode du théorème de Wilson pour générer une liste ldes nombres premiers jusqu'au 10000e nombre premier. Ensuite, imprime les nombres premiers avec les positions dans la liste, décalés de 1 pour l'indexation zéro, jusqu'à ce que nous manquions de limites après le 10000e nombre premier-e premier.

De manière pratique, la limite supérieure de 1366661peut être estimée comme 82e5/6ce qui est 1366666.6666666667, en enregistrant un caractère.

J'aimerais une méthode à boucle unique, en imprimant des nombres premiers indexés au fur et à mesure que nous les ajoutons, mais cela semble plus long.

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 octets

p:<:p:i.1e4

Sort les nombres premiers au format

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

Explication

        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 octets

Prime@Prime@Range@1*^4&

Fonction pure renvoyant la liste.

Haskell, 65 octets

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

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

Pas très vite. Comment ça marche: pest la liste infinie de nombres premiers (vérifiant naïvement tous les mod x ys pour y dans [2..x-1]). Prenez les premiers 10000éléments de la liste que vous obtenez lorsque 0:p!!(obtenir le nième élément de p) est mappé p. Je dois ajuster la liste des nombres premiers d'où je prends les éléments en ajoutant un nombre (-> 0:), car la fonction d'index ( !!) est basée sur zéro.

PARI / GP, 25 octets

apply(prime,primes(10^4))

AWK - 129 octets

... ouais ... trop longtemps pour gagner des points pour la compacité ... mais peut-être peut-il gagner un peu d'honneur pour la vitesse?

Le xdossier:

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

Fonctionnement:

$ 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

Lisible:

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

Le programme calcule un flux de nombres premiers en utilisant une L«bande de nombres» contenant des nombres premiers sautant Lpour signaler les nombres voisins déjà connus pour avoir un diviseur. Ces nombres premiers sautants avancent tandis que la «bande de nombres» Lest coupée numéro par numéro depuis son début.

Le fait de couper la tête de bande L[n]étant vide signifie qu'il n'y a pas de diviseur (principal) connu.

L[n]détenir une valeur signifie que cette valeur est un nombre premier et connu pour se diviser n.

Donc, soit nous avons trouvé un diviseur premier, soit un nouveau premier. Ensuite, ce nombre sera avancé au suivant L[n+m*p]sur la bande trouvée vide.

C'est comme le tamis d'Eratosthène "tiré à travers une bouteille de Klein". Vous agissez toujours sur le début de la bande. Au lieu de tirer des multiples de nombres premiers à travers la bande, vous utilisez les nombres premiers déjà trouvés comme curseurs sautant loin du début de la bande par plusieurs distances de leur propre valeur jusqu'à ce qu'une position libre soit trouvée.

Alors que la boucle externe génère une décomposition principale ou non principale par boucle, les nombres premiers trouvés sont comptés et stockés sous Pforme de clé, la valeur de cette paire (clé, valeur) n'est pas pertinente pour le flux du programme.

Si leur clé ise trouve Pdéjà dans ( i in P), nous avons un premier de la race p (p (i)).

Fonctionnement:

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

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

Tenez compte du fait que ce code n'utilise pas de tables principales précalculées externes.

Du temps pris sur mon bon vieux Thinkpad T60, donc je pense qu'il mérite d'être appelé rapidement.

Testé avec mawket gawksur Debian8 / AMD64

CJam, 19 ans

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

Vous pouvez l' essayer en ligne , mais vous aurez besoin d'un peu de patience: p

Pour mémoire, le dernier numéro est 1366661.

Perl, 55 octets

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

Utilise le module de @DanaJMath::Prime::Util pour perl (chargé avec le pragma ntheory). Obtenez-le avec:

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

05AB1E, 7 octets (non concurrent)

Code:

4°L<Ø<Ø

Essayez-le en ligne! , notez que j'ai changé le 4en a 2. Si vous avez beaucoup de temps, vous pouvez changer le 2dos 4, mais cela prendra beaucoup de temps. J'ai besoin de fixer l'algorithme pour cela.

Explication:

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