Рекурсивно простые числа - это последовательность простых чисел, такая что

p(1) = 2
p(n) = the p(n-1)th prime

Вот пример того, как можно вычислить 4-й Рекурсивно Премьер Прайм.

p(4) = the p(3)th prime
p(3) = the p(2)th prime
p(2) = the p(1)th prime
p(1) = 2
p(2) = the 2nd prime
p(2) = 3
p(3) = the 3rd prime
p(3) = 5
p(4) = the 5th prime
p(4) = 11

Вы должны написать программу или функцию, которая, если дано n, выдает n-ную рекурсивную простую первую строку.

Вы можете использовать индексирование на основе 0, если хотите, и в этом случае вы должны указать это в своем ответе.

Это код-гольф, поэтому цель состоит в том, чтобы минимизировать количество байтов.

Тестовые случаи

1 -> 2
2 -> 3
3 -> 5
4 -> 11
5 -> 31
6 -> 127
7 -> 709
8 -> 5381
9 -> 52711

Соответствующая запись OEIS : OEIS A007097

Оазис , 3 байта

Программа 0-проиндексирована . Код:

<q2

Использует формулу: a (n) = nth_prime (a (n-1) - 1) , с базовым случаем a (0) = 2 .

Объяснение кода:

  2   = a(0)

<     # Decrement a(n - 1) to get a(n - 1) - 1
 q    # prime(a(n - 1) - 1)

Попробуйте онлайн!

На самом деле 7 байтов

1@⌠DP⌡n

Попробуйте онлайн!

Объяснение:

1@⌠DP⌡n
1        push 1
 @       swap 1 with n
  ⌠DP⌡n  do the following n times:
   DP      decrement, prime at index

Mathematica, 16 байтов

Nest[Prime,1,#]&

Анонимная функция. Принимает число в качестве ввода и возвращает число в качестве вывода.

Желе , 5 4 байта

1 байт благодаря @Dennis.

1ÆN¡

Попробуйте онлайн!

объяснение

1        Starting with n = 1,
 ÆN      replace n by the nth prime
   ¡     (input) times.

JavaScript (ES6), 71 байт

p=(n,x=1)=>n?p(n-1,(N=y=>x?N(++y,x-=(P=z=>y%--z?P(z):z==1)(y)):y)(1)):x

Ungolfed, у вас есть три отдельные рекурсивные функции:

P=(n,x=n)=>n%--x?P(n,x):x==1
N=(n,x=1)=>n?N(n-P(++x),x):x
p=(n,x=1)=>n?p(n-1,N(x)):x

• Pопределяет, nявляется ли простое число;
• N находит n простое число;
• p рекурсивно работает N на 1 nвремя ввода .

MATL , 6 байтов

1i:"Yq

Попробуйте онлайн!

объяснение

1      % Push 1
i      % Input n
:      % Range [1 2 ... N]
"      % For each (that is, do the following N times)
  Yq   %   k-th prime, where k is the input
       % End for each (implicit)
       % Display stack (implicit)

R, 98 93 байта

5 байтов благодаря @smci

Вот ужасно неэффективное рекурсивное решение:

f<-function(m,n=1){j<-1;for(i in 1:n){j<-numbers::nextPrime(j)};a<-ifelse(m==0,j,f(m-1,j));a}

Тестовый вывод:

f(6)
[1] 127

f(10)        ### takes almost a minute... YIKES!!!
[1] 648391

Баш + коммунальные услуги, 55

Поскольку мы делаем рекурсивные простые числа, вот рекурсивный ответ:

((SHLVL-2<$1))&&primes 2|sed -n "`$0 $1`{p;q}"||echo 1

Поскольку подсчет уровней рекурсии основан на $SHLVLвстроенной переменной, то ответ может быть отключен, если вы уже имеете несколько уровней оболочки. Вероятно, поэтому этот ответ не работает на TIO.

Если это не хорошо, то вот более обычный ответ:

Баш + коммунальные услуги, 58

for((i=$1;i--;));{
n=`primes 2|sed -n "$n{p;q}"`
}
echo $n

Попробуйте онлайн .

Haskell , 58 байт

1-индексированных

f 1=2;f n=[x|x<-[2..],all((>)2.gcd x)[2..x-1]]!!(f(n-1)-1)

Попробуйте онлайн!

Объяснение:

Использует тот же трюк с доступом к первому списку с 0 индексами, что и ответ Аднана .
По существу, прямо следуют спецификации в противном случае.

f 1=2; -- base case
f n= -- main case
    [x|x<-[2..],all((>)2.gcd x)[2..x-1]]             -- list of all primes
    [x|x<-[2..],                                     -- consider all numbers
                               [2..x-1]              -- consider all smaller numbers
                all((>)2.gcd x)                      -- is coprime with them?
                    (>)2.                            -- 2 is greater than
                         gcd x                       -- gcd(x,lambda input)
                                        !!(f(n-1)-1) -- access the
                                                     -- f(n-1)-th 1-indexed prime

05AB1E , 4 байта

ÎF<Ø

Попробуйте онлайн!

объяснение

ÎF<Ø
Î    # Push 0 and input
 F   # Do input times...
  <   # Decrement
   Ø  # Get the nth prime (0-indexed) with n being the top of the stack

Чудо , 23 байта

p\.{1\2@:^(- p -#0 1)1P

1-индексироваться. Использование:

p\.{1\2@:^(- p -#0 1)1P}; p 3

объяснение

p\.{                #. Pattern matching syntax
  1\2               #. Base case p(1)=2
  @:^(- p -#0 1)1P  #. Other cases p(n)=nthprime(p(n-1)-1)
                    #. nthprime is 0-indexed
}                   #. Trailing bracket is optional in this case