Napisz program lub funkcję, która generuje / zwraca pierwsze 10000 liczb pierwszych z indeksowaniem liczb pierwszych.

Jeśli nazwiemy n- ^tą liczbą pierwszą p(n), ta lista jest

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

bo

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

Standardowe luki są zabronione i dozwolone są standardowe metody wyjściowe. Możesz odpowiedzieć za pomocą pełnego programu, funkcji o nazwie lub funkcji anonimowej.

MATLAB / oktawa, 25 bajtów

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

To nie staje się prostsze niż to.

Python, 72 bajty

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]

Kończy się to „błędem indeksu listy poza zakresem” po wydrukowaniu 10000 liczb, co jest domyślnie dozwolone .

Używa metody Twierdzenia Wilsona do wygenerowania listy lliczb pierwszych do 10000. liczby pierwszej. Następnie wypisuje liczby pierwsze z pozycjami na liście, przesuniętymi o 1 w celu zindeksowania zera, aż skończy się limit po 10000-tej liczbie pierwszej.

Korzystnie, górna granica 1366661może być określona jako 82e5/6co jest 1366666.6666666667, oszczędzając char.

Chciałbym metody pojedynczej pętli, drukując liczby pierwsze z indeksowaniem liczb pierwszych, gdy je dodamy, ale wydaje się, że jest ono dłuższe.

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 bajtów

p:<:p:i.1e4

Wysyła liczby pierwsze w formacie

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

Wyjaśnienie

        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 bajtów

Prime@Prime@Range@1*^4&

Czysta funkcja zwracająca listę.

Haskell, 65 bajtów

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

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

Niezbyt szybko. Jak to działa: pjest nieskończoną listą liczb pierwszych (naiwnie sprawdzając wszystkie mod x ys dla y in [2..x-1]). Weź pierwsze 10000elementy listy, które otrzymasz, gdy 0:p!!(pobierz n-ty element p) jest zmapowany p. Muszę dostosować listę liczb pierwszych, z których pobieram elementy, przygotowując jedną liczbę (-> 0:), ponieważ funkcja indeksu ( !!) jest oparta na zerach.

PARI / GP, 25 bajtów

apply(prime,primes(10^4))

AWK - 129 bajtów

... okay ... zbyt długo, aby zdobyć punkty za zwartość ... ale może może zyskać trochę honoru za szybkość?

xPliku:

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

Bieganie:

$ 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

Czytelny:

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

Program oblicza strumień liczb pierwszych, używając Ljako „taśmy liczb” przytrzymującej znalezione liczby pierwsze skaczące dookoła, Laby oznaczyć pobliskie liczby, o których już wiadomo, że mają dzielnik. Te skaczące liczby pierwsze będą się przesuwać, podczas gdy „taśma liczb” Lbędzie od początku odcinana numer po numerze.

Odcięcie L[n]pustej głowicy oznacza, że ​​nie ma znanego (podstawowego) dzielnika.

L[n]trzymanie wartości oznacza, że ​​ta wartość jest liczbą pierwszą i wiadomo, że dzieli n.

Więc albo znaleźliśmy główny dzielnik, albo nowy pierwszy. Wtedy pierwsza liczba zostanie przesunięta do następnej L[n+m*p]na taśmie, która jest pusta.

To jest jak sito Eratostenesa „wyciągnięte przez butelkę Kleina”. Zawsze działasz na początku taśmy. Zamiast strzelać wielokrotnością liczb pierwszych przez taśmę, używamy liczb pierwszych już znajdujących się, ponieważ kursory odskakują od taśmy zaczynając od wielu odległości o własnej wartości, aż do znalezienia wolnej pozycji.

Podczas gdy zewnętrzna pętla generuje jedną pierwszą lub nie pierwszą decymcję na pętlę, znalezione liczby pierwsze są liczone i zapisywane Pjako klucz, wartość tej pary (klucz, wartość) nie ma znaczenia dla przebiegu programu.

Jeśli izdarzy się, że ich klucz jest Pjuż w ( i in P), mamy liczbę pierwszą rasy p (p (i)).

Bieganie:

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

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

Weź pod uwagę, że ten kod nie korzysta z zewnętrznych wstępnie obliczonych tabel głównych.

Czas poświęcony mojemu staremu dobremu Thinkpadowi T60, więc myślę, że zasługuje na to, aby nazwać go szybko.

Testowane mawki gawkna Debian8 / AMD64

CJam, 19

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

Możesz spróbować online , ale będziesz potrzebować odrobiny cierpliwości: str

Dla przypomnienia ostatnia liczba to 1366661.

Perl, 55 bajtów

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

Zastosowania @DanaJ „s Math::Prime::Utilmoduł Perl (ładowany pragmie ntheory). Zdobądź dzięki:

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

05AB1E, 7 bajtów (niekonkurujące)

Kod:

4°L<Ø<Ø

Wypróbuj online! , zauważ , że zmieniłem 4na 2. Jeśli masz dużo czasu, możesz zmienić 2powrót na 4, ale zajmie to dużo czasu. W tym celu muszę naprawić algorytm.

Wyjaśnienie:

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