Пролог (SWI) , 134 128 127 124 байтов
Этот ответ является частью сотрудничества между мной и 0 '. Мы оба работали над этим вместе, единственная причина, по которой я публикую это, в том, что я выиграл «Рок, бумага, ножницы».
\Q-->{Q=1};"(",\N,")",\B,{findnsols(N,I,(between(2,inf,I),\+ (between(3,I,U),0=:=I mod(U-1))),L)->append(_,[Y],L),Q is Y*B}.
Попробуйте онлайн!
объяснение
Этот ответ является прекрасным примером того, что делает гольф в прологе веселым.
Этот ответ использует мощную систему Prologs для определенных грамматик. Вот наша грамматика немного раскололась.
head(1)-->[].
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
prime(N,Y):-
findnsols(N,I,(
between(2,inf,I),
isprime(I)
),L),
append(_,[Y],L),!.
Первое правило построения:
head(1)-->[].
Это говорит Прологу, что пустая строка соответствует 1.
Наше второе правило построения немного сложнее.
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
Это говорит нам о том, что любая непустая строка содержит скобки вокруг предложения с теми же правилами, справа от предложения с теми же правилами.
Это также говорит нам, что значение этого условия ( Q) следует правилу:
{prime(N,Y),Q is Y*B}
Разбивая это, Qэто произведение 2 чисел Yи B. Bэто просто значение предложения слева и Yэто Nпростое число, где Nэто значение предложения в скобках.
Это правило охватывает оба правила формирования дерева факторов
- Умножение конкатенации
- Вложение занимает n-е простое число
Теперь для определения предикатов. В негольфированной версии присутствуют два предиката (в моем собственном коде я переместил цепочку предикатов вперед). Здесь есть два соответствующих предиката isprime/1, которые соответствуют простому числу и prime/2, которые, учитывая Nи Y, соответствуют тогда, когда Yэто Nпростое число. Сначала мы имеем
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
Это работы довольно стандартного определения первичности, мы настаиваем на том, что между 2 и 2 I, включая 2, нет Iделения, но это не делит I.
Следующий предикат также довольно прост
prime(N,Y):-
findnsols(N,I,(
between(2,inf,I),
isprime(I)
),L),
append(_,[Y],L),!.
Мы используем, findnsolsчтобы найти первые Nчисла, которые являются простыми, затем мы возвращаем последнее. Хитрость в том, что хотя findnsolsне гарантируется поиск наименьших N простых чисел, из-за способа обработки SWI betweenвсегда найдутся меньшие простые числа. Это, однако, означает, что мы должны сократить, чтобы не найти больше простых чисел.
Гольфы
Мы можем переслать причину в нашем коде дважды. Так isprimeкак используется только один раз, его определение может быть перемещено внутри prime. Следующим является перемещение primeнепосредственно внутри DCG, однако, поскольку мы используем врезку, primeчтобы не findnsolsсоздавать слишком много простых чисел, у нас есть небольшая проблема. Cut, разрезает весь DCG вместо того, что мы хотим. После небольшой копки документации мы обнаружили, что она once/1может быть использована только для вырезания этой части, но не всей DCG. Однако, больше копания документации показало, что ->оператор мог также использоваться, чтобы выполнить подобную задачу. ->Оператор примерно эквивалентен ,!,поэтому мы переместили наш разрез на другую сторону append/3и заменить его ->.
В предикатах (и правилах) SWI-Prolog операторы могут быть заданы как имена, что позволяет нам убрать обычно необходимые скобки. Таким образом, мы можем сохранить 6 байтов, вызывая правило \.
