Напишите программу или функцию, которая выводит / возвращает первые 10000 простых индексированных простых чисел.

Если мы называем n- ^е простое число p(n), этот список

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

так как

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

Стандартные лазейки запрещены, а стандартные методы вывода разрешены. Вы можете ответить с помощью полной программы, именованной функции или анонимной функции.

MATLAB / Octave, 25 байтов

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

Это не становится намного проще, чем это.

Python, 72 байта

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]

Это завершается «списком ошибок вне диапазона» после печати 10000 номеров, что разрешено по умолчанию .

Использует метод теоремы Вильсона для генерации списка lпростых чисел до 10000-го простого числа. Затем печатает простые числа с позициями в списке, сдвинутыми на 1 для индексации нулями, пока мы не исчерпаем границы после 10000-го простого числа.

Удобно то , что верхняя граница 1366661может быть оценена как 82e5/6что 1366666.6666666667, экономя символ.

Я бы хотел использовать однопетлевой метод печати простых индексированных простых чисел по мере их добавления, но он кажется более длинным.

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 байт

p:<:p:i.1e4

Выводит простые числа в формате

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

объяснение

        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 байта

Prime@Prime@Range@1*^4&

Чистая функция, возвращающая список.

Haskell, 65 байт

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

Выходы: [3,5,11,17,31,41,59,67,83,109,127.....<five hours later>...,1366661]

Не очень быстро Как это работает: pбесконечный список простых чисел (наивно проверяя все mod x ys на y в [2..x-1]). Возьмите первые 10000элементы списка, которые вы получаете, когда 0:p!!(получить n-й элемент p) отображается на p. Мне нужно настроить список простых чисел, из которых я беру элементы, добавив одно число (-> 0:), потому что функция индекса ( !!) основана на нуле.

PARI / GP, 25 байтов

apply(prime,primes(10^4))

AWK - 129 байт

... хорошо ... слишком долго, чтобы выиграть очки за компактность ... но может быть, это может получить некоторую честь за скорость?

xФайл:

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

Бег:

$ 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

Удобочитаемый:

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

Программа вычисляет поток простых чисел, используя L«ленту чисел», содержащую найденные простые числа, прыгающие вокруг, Lчтобы отметить соседние числа, о которых уже известно, что они имеют делитель. Эти прыжковые простые числа будут продвигаться, пока «лента чисел» Lотрубается числом по номеру с самого начала.

Отрезание головки ленты L[n]пусто означает, что не существует известного (простого) делителя.

L[n]удержание значения означает, что это значение является простым и, как известно, делится n.

Так что либо мы нашли простой делитель, либо новый простой. Затем это простое число перейдет к следующему L[n+m*p]на ленте, найденной пустой.

Это похоже на Сито Эратосфена, «вытащившего бутылку Кляйна». Вы всегда действуете в начале ленты. Вместо того, чтобы запускать несколько простых чисел через ленту, вы используете уже найденные простые числа, поскольку курсоры, отскакивающие от ленты, начинают на несколько дистанций своего значения до тех пор, пока не будет найдена свободная позиция.

В то время как внешний цикл генерирует одно простое или не простое решение для цикла, найденные простые числа подсчитываются и сохраняются в Pкачестве ключа, значение этой пары (ключ, значение) не имеет отношения к потоку программы.

Если их ключ iнаходится в Pуже ( i in P), у нас есть простое число породы p (p (i)).

Бег:

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

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

Примите во внимание, что этот код не использует внешние предварительно вычисленные простые таблицы.

Время заняло мой старый добрый Thinkpad T60, поэтому я считаю, что его стоит назвать быстрым.

Протестировано с mawkи gawkна Debian8 / AMD64

CJam, 19

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

Вы можете попробовать это онлайн , но вам нужно немного терпения: p

Для записи, последний номер 1366661.

Perl, 55 байт

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

Использование @DanaJ «ы Math::Prime::Utilмодуль для Perl (загружается с прагмой ntheory). Получите это с:

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

05AB1E, 7 байтов (не конкурирует)

Код:

4°L<Ø<Ø

Попробуйте онлайн! , Примечание , что я изменил 4в 2. Если у вас много времени, вы можете поменять 2спину на 4, но это займет много времени. Мне нужно закрепить алгоритм для этого.

Объяснение:

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