Tulis program atau fungsi yang menampilkan / mengembalikan 10.000 nomor prima yang diindeks perdana.

Jika kita menyebut n ^th prima p(n), daftar ini adalah

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

karena

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

Celah standar dilarang, dan metode keluaran standar diizinkan. Anda dapat menjawab dengan program lengkap, fungsi bernama, atau fungsi anonim.

MATLAB / Oktaf, 25 byte

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

Tidak jauh lebih mudah dari ini.

Python, 72 byte

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]

Ini berakhir dengan "daftar indeks di luar jangkauan kesalahan" setelah mencetak angka 10000, yang diizinkan secara default .

Menggunakan metode Teorema Wilson untuk menghasilkan daftar lbilangan prima hingga perdana ke-10.000. Kemudian, cetak bilangan prima dengan posisi dalam daftar, bergeser 1 untuk pengindeksan nol, sampai kita kehabisan batas setelah perdana ke-10.000 perdana.

Dengan mudah, batas atas 1366661dapat diperkirakan seperti 82e5/6apa 1366666.6666666667, menghemat char.

Saya ingin metode loop tunggal, mencetak bilangan prima yang diindeks saat kami menambahkannya, tetapi tampaknya lebih lama.

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 byte

p:<:p:i.1e4

Output bilangan prima dalam format

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

Penjelasan

        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 byte

Prime@Prime@Range@1*^4&

Fungsi murni mengembalikan daftar.

Haskell, 65 byte

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

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

Tidak terlalu cepat. Cara kerjanya: padalah daftar bilangan prima tak terbatas (secara naif memeriksa semua mod x ys untuk y in [2..x-1]). Ambil 10000elemen pertama dari daftar yang Anda dapatkan saat 0:p!!(dapatkan elemen ke-n p) dipetakan p. Saya harus menyesuaikan daftar bilangan prima di mana saya mengambil elemen dari dengan menambahkan satu nomor (-> 0:), karena fungsi indeks ( !!) berbasis nol.

PARI / GP, 25 byte

apply(prime,primes(10^4))

AWK - 129 byte

... oookay ... terlalu lama untuk memenangkan poin untuk kekompakan ... tapi mungkin itu bisa mendapatkan kehormatan untuk kecepatannya?

The xFile:

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

Berlari:

$ 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

Dapat dibaca:

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 ini menghitung aliran bilangan prima menggunakan Lsebagai "pita angka" memegang bilangan prima ditemukan melompat Luntuk menandai nomor-nomor terdekat yang sudah diketahui memiliki pembagi. Primer melompat ini akan maju sementara "pita angka" Ldipotong nomor dengan angka dari awal.

Sementara memotong kepala kaset L[n]menjadi kosong berarti tidak ada pembagi (prime) yang diketahui.

L[n]memegang nilai berarti, nilai ini prima dan dikenal untuk membagi n.

Jadi, kami telah menemukan pembagi utama atau perdana baru. Kemudian perdana akan maju ke berikutnya L[n+m*p]pada rekaman ditemukan kosong.

Ini seperti Saringan Eratosthenes "ditarik melalui botol Klein". Anda selalu bertindak atas rekaman itu. Alih-alih menembakkan beberapa bilangan prima melalui pita, Anda menggunakan bilangan prima yang sudah ditemukan sebagai kursor yang melompat menjauh dari pita mulai dari berbagai jarak nilainya sendiri sampai posisi bebas ditemukan.

Sementara loop luar menghasilkan satu prime atau tidak prime decission per loop, bilangan prima yang ditemukan dihitung dan disimpan Psebagai kunci, nilai pasangan (kunci, nilai) ini tidak relevan untuk aliran program.

Jika kunci mereka ikebetulan Psudah di ( i in P), kami memiliki prima dari jenis p (p (i)).

Berlari:

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

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

Memperhatikan bahwa kode ini tidak menggunakan tabel prime prakalkulasi eksternal.

Waktu yang dihabiskan untuk Thinkpad T60 lama saya yang baik, jadi saya pikir pantas untuk dipanggil cepat.

Diuji dengan mawkdan gawkpada Debian8 / AMD64

CJam, 19

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

Anda dapat mencobanya secara online , tetapi Anda perlu sedikit kesabaran: hlm

Sebagai catatan, angka terakhir adalah 1366661.

Perl, 55 byte

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

Penggunaan @DanaJ 's Math::Prime::Utilmodul untuk perl (sarat dengan pragma yang ntheory). Dapatkan dengan:

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

05AB1E, 7 byte (tidak bersaing)

Kode:

4°L<Ø<Ø

Cobalah online! , perhatikan bahwa saya telah mengubah 4menjadi 2. Jika Anda memiliki banyak waktu, Anda dapat mengubah 2kembali 4, tetapi ini akan memakan banyak waktu. Saya perlu kencangkan algoritma untuk ini.

Penjelasan:

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