Это число простое?

195

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

Списки кода Rosetta представлены языками идиоматических подходов к тестированию простоты: один использует тест Миллера-Рабина, а другой - пробное деление . Однако «самый идиоматический» часто не совпадает с «самым коротким». Чтобы сделать Programming Puzzles и Code Golf доступным сайтом для Code Golf, эта задача состоит в том, чтобы составить каталог кратчайшего подхода на каждом языке, похожего на «Hello, World!» и Гольф, ты идеальный для хорошего! ,

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

задача

Напишите полную программу, которая, учитывая строго положительное целое число n в качестве входных данных, определяет, является ли n простым, и печатает истинное или ложное значение соответственно.

Для этой задачи целое число является простым, если оно имеет ровно два строго положительных делителя. Обратите внимание, что это исключает 1 , который является его единственным строго положительным делителем.

Ваш алгоритм должен быть детерминированным (т. Е. Производить правильный вывод с вероятностью 1) и теоретически должен работать для сколь угодно больших целых чисел. На практике вы можете предположить, что входные данные могут храниться в вашем типе данных, если программа работает для целых чисел от 1 до 255.

вход

  • Если ваш язык способен читать из STDIN, принимать аргументы командной строки или любую другую альтернативную форму ввода данных пользователем, вы можете прочитать целое число как его десятичное представление, унарное представление (используя выбранный вами символ), байтовый массив (большой или little endian) или однобайтовый (если это ваш самый большой тип данных в вашем языке).

  • Если (и только если) ваш язык не может принять какой-либо пользовательский ввод, вы можете жестко закодировать ввод в вашей программе.

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

    Для оценки выставьте программу, соответствующую вводу 1 .

Выход

Вывод должен быть записан в STDOUT или ближайшую альтернативу.

Если возможно, вывод должен состоять исключительно из истинного или ложного значения (или его строкового представления), за которым может следовать одна новая строка.

Единственным исключением из этого правила является постоянный вывод интерпретатора вашего языка, который не может быть подавлен, например приветствие, цветовые коды ANSI или отступы.

Дополнительные правила

  • Речь идет не о поиске языка с кратчайшим подходом к первичному тестированию, а о поиске кратчайшего подхода в каждом языке. Поэтому ни один ответ не будет помечен как принятый.

  • Материалы на большинстве языков будут оцениваться в байтах в соответствующей существующей кодировке, обычно (но не обязательно) UTF-8.

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

    Некоторые языки, такие как папки , немного сложнее оценить. Если вы сомневаетесь, пожалуйста, спросите на Meta .

  • В отличие от наших обычных правил, не стесняйтесь использовать язык (или языковую версию), даже если он новее этой задачи. Если кто-то хочет злоупотребить этим, создавая язык, в котором пустая программа выполняет тест на простоту, то поздравляю с подготовкой очень скучного ответа.

    Обратите внимание, что должен быть переводчик, чтобы представление можно было проверить. Разрешается (и даже поощряется) самостоятельно писать этот переводчик для ранее не реализованного языка.

  • Если выбранный вами язык является тривиальным вариантом другого (потенциально более популярного) языка, у которого уже есть ответ (например, диалекты BASIC или SQL, оболочки Unix или тривиальные производные Brainfuck, такие как Headsecks или Unary), рассмотрите возможность добавления примечания к существующему ответу, который такое же или очень похожее решение также является самым коротким на другом языке.

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

  • Если они не были отменены ранее, применяются все стандартные правила игры в гольф , включая http://meta.codegolf.stackexchange.com/q/1061 .

В качестве примечания, пожалуйста, не понижайте скучные (но действительные) ответы на языках, где не так много в гольфе; они все еще полезны для этого вопроса, так как он пытается собрать каталог настолько полно, насколько это возможно. Тем не менее, делайте в первую очередь upvote ответы на языках, где автор фактически должен был приложить усилия для игры в гольф.

Каталог

Фрагмент стека в нижней части этого поста создает каталог из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общей таблицы лидеров.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

## Perl, 43 + 2 (-p flag) = 45 bytes

Вы также можете сделать имя языка ссылкой, которая будет отображаться во фрагменте кода:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Показать фрагмент кода

code-golf number number-theory primes decision-problem Деннис
источник
Могу ли я принимать входные данные как отрицательные числа, где abs (входной) будет число, которое я тестирую?
Стэн Струм
Нет, входное значение является строго положительным целым числом.
Деннис
1
@LyndonWhite Это был задуман как каталог (например, «Здравствуй, мир!» ) Тестов простоты, поэтому унифицированный формат представления казался предпочтительным. Я сожалею, что это одно из двух решений по этой проблеме, а другое позволяет проводить только тесты на детерминированную первичность.
Денис
1
@ Shaggy Похоже, вопрос для мета.
Деннис
1
Да, это то, что я думал. Я позволю тебе сделать почести, видя, как это ваш вызов.
Лохматый

Ответы:

226

Привет, мир! 13

hello, world!
histocrat
источник
83
Вы просто создали этот язык, просто для этого представления? ;)
ETHproductions
41
@ETHproductions Похоже, последний коммит был 10 дней назад.
Geobits
39
Я надеялся, что язык будет немного лучше, прежде чем ссылаться на него, но этот вызов был опубликован, и я не смог устоять.
гистократ
31
Я бы почти сказал, что зависание на входе 1 - это правильная функциональность.
iamnotmaynard
22
Самое приятное в этом то, что программа не просто встроенная, каждый персонаж играет свою роль в получении правильного результата.
ETHproductions
157

Гексагония , 29 байт

.?'.).@@/'/.!.>+=(<.!)}($>(<%

Читаемая версия этого кода:

   . ? ' .
  ) . @ @ /
 ' / . ! . >
+ = ( < . ! )
 } ( $ > ( <
  % . . . .
   . . . .

Пояснение: Он проверяет, существует ли число от 2 до n-1, которое делит n.

Инициализация:

Запишите n в одну ячейку памяти и n-1 в другую:

   . ? ' .
  . . . . .
 . . . . . .
+ = ( . . . .
 . . . . . .
  . . . . .
   . . . .

Особый случай n = 1:

Выведите 0 и завершите

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . .
 . . . . . .
  . . . . .
   . . . .

Петля

Рассчитайте n% a и уменьшите a. Завершить, если a = 1 или n% a = 0.

   . . . .
  ) . . . /
 ' / . . . >
. . . . . . .
 } ( $ > ( <
  % . . . .
   . . . .

Случай а = 1:

Увеличьте 0 до 1, распечатайте его и завершите. (Указатель инструкций работает в направлении NE и проходит от восточного угла к юго-западному углу. И $ гарантирует, что он игнорирует следующую команду)

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . )
 . . $ . . <
  . . . . .
   . . . .

Случай% n = 0:

Выведите 0 и завершите (указатель инструкции запускается SW и переходит в верхнюю часть к @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
Etoplay
источник
61
Черт возьми, это один впечатляющий первый пост. :) Я назначу щедрость прямо сейчас (я награжу ее через 7 дней, чтобы привлечь больше внимания к вашему ответу). Добро пожаловать в PPCG!
Мартин Эндер,
35
Отличный ответ! +1 для " считываемых версий этого кода: <...> " :-)
agtoever
68

Гексагония , 218 92 58 55 байт

Обратите внимание: этот ответ был жестко побежден Etoplay решением с длиной стороны 4 .

)}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[

Первая в истории нетривиальная (т.е. нелинейная) программа Hexagony! Он основан на том же квадратичном факторе, что и ответ Sp3000 на Лабиринт . Начав с шестигранника размера 10, мне удалось сжать его до размера 5. Однако я смог повторно использовать некоторый дублирующий код, и в коде все еще есть куча неиспользуемых операций, поэтому размер 4 мог бы просто быть возможным

объяснение

Чтобы разобраться в коде, нам сначала нужно его развернуть. Hexagony добавляет любой исходный код к следующему центрированному шестиугольному числу с помощью no-ops ( .), то есть 61. Затем он переставляет код в обычный шестиугольник соответствующего размера:

     ) } ? } .
    = ( . . ] =
   } = ' . } . }
  ~ . / % * . . &
 . = & { . < . . .
  . . . = | > ( <
   . . } ! = . .
    . & @ \ [ .
     . . . . .

Это довольно сильно связано с пересечением и перекрытием путей выполнения и множественных указателей инструкций (IP). Чтобы объяснить, как это работает, давайте сначала посмотрим на версию без заглядывания, где поток управления не проходит через границы, используется только один IP, а пути выполнения максимально просты:

             . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
          . . . . . . . . . . @ . . . . .
         . . . . . . . . . . ! . . . . . .
        . . . . . . . . . . % . . . . . . .
       . . . . . . . . . . ' . . . . . . . .
      . . . . . . . . . . & . . . . . . . . .
     . . . . . . . . . . { . . . . . . . . . .
    . . . . . . . . . . * . . . . . . . . . . .
   . . . . . . . . . . = . . . . . . . . . . . .
  . . . . . . . . . . } . . . . . . . . . . . . .
 ) } ? } = & { < . . & . . . . . . . . . . . . . .
  . . . . . . . > ( < . . . . . . . . . . . . . .
   . . . . . . = . . } . . . . . . . . . . . . .
    . . . . . } . . . = . . . . . . . . . . . .
     . . . . | . . . . | . . . . . . . . . . .
      . . . . * . . . ) . . . . . . . . . . .
       . . . . = . . & . . . . . . . . . . .
        . . . . > } < . . . . . . . . . . .
         . . . . . . . . . . . . . . . . .
          . . . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
             . . . . . . . . . . . . .

Примечание: приведенный выше код начинается с выполнения первой строки, в которой нет никаких операций. Затем, когда IP-адрес достигает северо-восточного края, он переходит в самый левый угол ( )), где начинается фактический код.

Прежде чем мы начнем, несколько слов о разметке памяти Hexagony. Это немного похоже на ленту Брейнфука на стероидах. На самом деле это не лента, а сама шестиугольная сетка (бесконечная), где каждое ребро имеет целочисленное значение, которое изначально равно 0 (а в отличие от стандартного Brainfuck значения являются знаковыми целыми числами произвольной точности). Для этой программы мы будем использовать четыре ребра:

введите описание изображения здесь

Мы будем вычислять факториал на ребро А , отсчитывать наш вход на края С и сохранить другую копию ввода (для по модулю) на ребра D . B используется как временное ребро для вычислений.

Указатель памяти (MP) начинается с края A и указывает на север (это важно для перемещения MP вокруг). Теперь вот первый бит кода:

)}?}=&{

)увеличивает ребро A в 1качестве основы факториала. }заставляет MP поворачивать направо, то есть двигаться к краю C (указывая на северо-восток). Здесь мы читаем ввод как целое число с ?. Затем мы сделаем еще один поворот направо на край D с }. =переворачивает MP, таким образом, что она указывает на вершину совместно с C . &копирует значение из C (вход) в D - значение копируется слева, потому что текущее значение не положительное (ноль). Наконец, мы заставляем MP повернуть налево назад к C с помощью {.

Далее, <это технически ветвь, но мы знаем, что текущее значение положительно, поэтому IP всегда будет направлен в сторону >. Ветвь хит от боковых действует как зеркало, таким образом, что IP -по горизонтали снова движется, по направлению к (, который уменьшает значение в C .

Следующая ветвь, <на самом деле, сейчас ветка. Вот как мы переходим от цикла n-1к 1. В то время как текущее значение в C положительно, IP поворачивает направо (чтобы выполнить цикл). Как только мы достигнем нуля, он повернет налево.

Давайте посмотрим на цикл "тело". Это |простые зеркала, >и <они снова используются как зеркала. Это означает, что фактическое тело цикла сводится к

}=)&}=*}=

}перемещает MP к ребру B , =меняет направление на вершину ABC . )увеличивает значение: это актуально только для первой итерации, где значение B по-прежнему равно нулю: мы хотим убедиться, что оно положительное, чтобы следующая инструкция &копировала правого соседа, т.е. A , то есть текущее значение факториала вычисление, в B .

}затем перемещает MP к A , =полностью изменяет его, чтобы стоять перед общей вершиной. *умножает оба соседей, то есть края B и C и сохраняет результат в . Наконец, у нас есть еще один, чтобы вернуться к C , по-прежнему лицом к вершине ABC .}=

Я надеюсь , что вы можете увидеть , как это вычисляет факториал n-1в A .

Итак, теперь мы сделали это, счетчик цикла в C равен нулю. Мы хотим возвести в квадрат факториал и затем взять по модулю входные данные. Вот что делает этот код:

&}=*{&'%!@

Поскольку C равен нулю, &копирует левый сосед, т.е. факториала в . переходит к B и сохраняет произведение двух копий факториала (т.е. квадрат) в B . возвращается к С , но не меняет MP. Мы знаем , что текущее значение теперь положительное, поэтому ввод копий из D в C . МП в обратном направлении вправо, т.е. на . Помните, квадрат факториала в B , а вход в C . Так что вычисляет , именно то, что мы ищем.}=*{&'%(n-1)!^2 % n!выводит результат в виде целого числа (0 или 1) и @завершает программу.

Ладно, но это была не изгнанная версия. А как насчет версии для гольфа? Вам нужно знать еще две вещи о гексагонии:

  1. Края обернуть вокруг. Если IP попадает на край шестиугольника, он переходит на противоположный край. Это неоднозначно, когда IP попадает прямо в угол, поэтому попадание в угол также действует как ветвь: если текущее значение положительное, IP переходит к краю сетки справа, в противном случае к левому.
  2. На самом деле 6 IP. Каждый из них начинается в другом углу, двигаясь вдоль края по часовой стрелке. Только один из них активен за один раз, что означает, что вы можете просто игнорировать остальные 5 IP-адресов, если они вам не нужны. Вы можете переключиться на следующий IP (по часовой стрелке) с помощью ]и на предыдущий с помощью [. (Вы также можете выбрать определенный с помощью #, но это в другой раз.)

Есть также несколько новых команд в нем: \и /зеркала , как |и ~умножает текущее значение на -1.

Так как же версия без гольфа переходит в версию с гольфом? Линейный код настройки )}?}=&{и базовая структура цикла можно найти здесь:

        ) } ? } .  ->
       . . . . . .
      . . . . . . .
     . . . . . . . .
->  . = & { . < . . .
     . . . . . > ( <
      . . . . . . .
       . . . . . .
        . . . . .

Теперь тело цикла пересекает ребра несколько раз, но самое главное, фактические вычисления передаются на предыдущий IP (который начинается в левом углу, двигаясь на северо-восток):

        ) . . . .
       = . . . ] .
      } = . . } . .
     ~ . / . * . . .
    . . . . . . . . .
     . . . = . > ( <
      . . } . = . .
       . & . \ [ .
        . . . . .

После отскока от ветви в направлении юго-востока, IP оборачивается по краю до двух =в верхнем левом углу (которые вместе являются запретными), а затем отскакивает от /. ~Инвертирует знак текущего значения, что важно для последующих итераций. IP снова обходит тот же край и, наконец, попадает [туда, где управление передается другому IP.

Теперь выполняется этот, ~}=)&}=*}который отменяет отрицание, а затем просто запускает тело цикла без гольфа (минус =). Наконец, он попадает к тому, ]какие руки возвращаются к исходному IP. (Обратите внимание, что в следующий раз, когда мы выполним этот IP-адрес, он начнется с того места, где остановился, поэтому сначала он достигнет угла. Нам нужно, чтобы текущее значение было отрицательным, чтобы IP-адрес мог вернуться обратно к северо-западному краю. вместо юго-восточного.)

Как только исходный IP-адрес возобновляет управление, он отскакивает от \, выполняет оставшиеся, =а затем нажимает >для подачи в следующую итерацию цикла.

Теперь действительно безумная часть: что происходит, когда цикл заканчивается?

        ) . . . .
       . ( . . ] =
      . . ' . } . }
     . . . % * . . &
    . . . . . . . . .
     . . . = | . . <
      . . } ! . . .
       . & @ . . .
        . . . . .

IP перемещается на северо-восток от <и оборачивается к северо-восточной диагонали. Таким образом, он попадает в тот же путь выполнения, что и тело цикла ( &}=*}]). Что на самом деле довольно круто, потому что это именно тот код, который мы хотим выполнить на данном этапе, по крайней мере, если мы добавим еще один =}(потому что }=}это эквивалентно {). Но как это фактически не входит в более ранний цикл снова? Потому что ]меняется на следующий IP, который теперь является (пока что не использованным) IP, который начинается в верхнем правом углу, двигаясь на юго-запад. Оттуда IP продолжается вдоль края, переносится в верхний левый угол, перемещается вниз по диагонали, отскакивает от |и заканчивается в момент @выполнения последнего бита линейного кода:

=}&)('%!@

( )(Конечно, это не работает - мне пришлось добавить, (потому что )он уже был там.)

Фу ... какой беспорядок ...

Мартин Эндер
источник
Приятно! Насколько это ново? Кроме того, вы можете создать страницу esolangs всякий раз, когда получаете стабильную версию
mbomb007,
18
@ mbomb007 Я реализовал язык два дня назад (и разработал его за два или три дня до этого). И да, я определенно добавлю страницу esolangs, но я думаю, что спецификация еще не на 100% стабильна (например, есть еще 3 неназначенные команды). Как только я почувствую, что он более стабилен, я добавлю его как в esolangs, так и в нашу метапост.
Мартин Эндер,
Под расширенным гексом он оборачивается в самый левый угол ( 1) . О чем 1ты там говоришь?
mbomb007,
@ mbomb007 исправлено. )Обыкновение быть 1.
Мартин Эндер
5
+1 только за уровень детализации в вашем объяснении того, как это работает. Если бы появилось больше языков с примером, в котором больше людей могли бы использовать их: D
jdarling
66

Pyth, 4 байта

}QPQ

Отпечатки Trueили False.

orlp
источник
12
Я знаю, что это старый, но теперь вы можете сделать это так: P_Q и сохранить 1 байт.
drobilc
14
Теперь это возможно сP_
Blue
3
@drobilc Вы можете вырезать Q, как EOF, когда функция ожидает аргумент, она использует ввод
Stan Strum
55

Сетчатка , 16 байт

^(?!(..+)\1+$)..

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

Начнем с классики: обнаружение простых чисел с помощью регулярного выражения . Ввод должен быть дан в унарном виде , используя любой повторяющийся печатный символ. Набор тестов включает в себя преобразование из десятичного в унарный для удобства.

Программа Retina, состоящая из одной строки, обрабатывает эту строку как регулярное выражение и печатает количество совпадений, найденных во входных данных, что будет 0для составных чисел и 1простых чисел.

Предварительный просмотр гарантирует, что ввод не является составным: при обратном отслеживании будут проверяться все возможные подстроки (не менее 2 символов) (..+), а предварительный просмотр пытается сопоставить остальную часть ввода, повторяя то, что было записано здесь. Если это возможно, это означает, что вход имеет делитель больше 1, но меньше, чем он сам. Если это так, то отрицательный прогноз приводит к сбою сопоставления. Для простых чисел такой возможности нет, и матч продолжается.

Единственная проблема заключается в том, что этот запрос также принимает 1, поэтому мы исключаем это, сопоставляя по крайней мере два символа с ...

Мартин Эндер
источник
На самом деле это нерегулярное выражение, так как простые числа не образуют обычный язык.
PyRulez
@PyRulez Большинство реальных регулярных выражений гораздо мощнее, чем теоретическая концепция регулярных выражений. Я улучшил формулировку, хотя.
Мартин Эндер
1
Самые мощные движки "regex", открытые прямо сейчас, имеют мощность распознавания, равную мощности линейных ограниченных автоматов. Стандартное регулярное выражение проблемы, рекурсия шаблона, неограниченный просмотр и неограниченный просмотр назад - все, что вам нужно для контекстно-зависимого анализа (хотя обратные ссылки и тому подобное обычно помогают усложнить эффективный анализ), и у некоторых есть все. Даже не заводите меня на движки, которые позволяют встраивать код в регулярные выражения.
eaglgenes101
52

CJam, 4 байта

qimp

CJam имеет встроенный оператор для тестирования простоты.

Питер Тейлор
источник
18
В качестве альтернативы:limp
Sp3000
43
pimpмой cjam
Flawr
12
pimpобъективно больше сутенера
MickLH
1
Вы также можете сделатьl~mp
Коровы крякают
12
@Cyoce, qчитает строку ввода, iанализирует ее как целое число и mpявляется встроенной. В CJam есть две группы встроенных двухсимвольных: начинаются «расширенные» и начинаются e«математические»m
Питер Тейлор
48

HTML + CSS, 254 + n макс * 28 байт

Мы можем проверить простоту с помощью регулярных выражений. Mozilla имеет @document, который определяется как:

@document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# {
  <group-rule-body>
}

Для фильтрации элементов с помощью CSS на основе текущего URL. Это один проход, поэтому мы должны сделать два шага:

  1. Получите информацию от пользователя. Этот вход должен как-то отражаться в текущем URL.
  2. Ответьте пользователю как можно меньше кода.

1. Получение информации

Самый короткий путь, который я могу понять, чтобы получить ввод и перенести его на URL, это GETформа с флажками. Для регулярного выражения нам просто нужна уникальная строка для подсчета появлений.

Итак, начнем с этого (61 байт):

<div id=q><p id=r>1<p id=s>0</div><form method=GET action=#q>

Мы получили два уникальных <p>s, чтобы указать, является ли введенное число простым (1) или нет (0). Мы также определяем форму и ее действие.

Далее следуют n max флажков с тем же именем (n max * 28 байт):

<input type=checkbox name=i>

Затем следует элемент submit (34 байта):

<input name=d value=d type=submit>

2. Показать ответ

Нам нужен CSS (159 байт), чтобы выбрать <p>для отображения (1 или 0):

#q,#s,#q:target{display:none}#q:target{display:block}@-moz-document regexp(".*\\?((i=on&)?|(((i=on&)(i=on&)+?)\\4+))d=d#q$"){#s{display:block}#r{display:none}}

»Попробуйте это на codepen.io (только Firefox)

mınxomaτ
источник
12
+1: это мое самое любимое злоупотребление HTML, и такие вещи, которые заставляют меня любить codegolf.
кот
Это, безусловно, интересно, но я не уверен, удовлетворяет ли это правилам этой задачи. В частности, я не думаю, что он соответствует Вашему алгоритму [...], теоретически должен работать для сколь угодно больших целых чисел. Не могли бы вы также использовать регулярное выражение для значения поля ввода?
Деннис
@ Деннис Может быть. Наверное, даже. Но это не решит проблему, которую вы упомянули. Я оставляю это здесь как неконкурентную запись, потому что это самая тематическая задача для этого.
2015 года
Почему нет? Если у вас есть однозначное число в поле ввода, ваш код больше не будет зависеть от максимального числа.
Деннис
5
Хм, я думал об этом немного больше, и на самом деле нет никакой разницы между наличием только x флажков и интерпретатором, который имеет только y-битные числа. Не обращайте внимания на мой предыдущий комментарий.
Деннис
40

Гексагония , 28 байт

Так как Etoplay абсолютно обеспокоил меня по этому вопросу , я почувствовал, что должен переиграть его единственный другой ответ .

?\.">"!*+{&'=<\%(><.*.'(@>'/

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

Я использую теорему Вильсона, как Мартин сделал в своем ответ : Учитывая n, I выход(n-1!)² mod n

Вот это программа развернулась:

   ? \ . "
  > " ! * +
 { & ' = < \
% ( > < . * .
 ' ( @ > ' /
  . . . . .
   . . . .

И вот читаемая версия:

Очень читаемый

Объяснение:

Программа имеет три основных этапа: инициализация , факториал и вывод .

Модель памяти гексагонии представляет собой бесконечную гексагональную сетку. Я использую 5 ячеек памяти, как показано на этой диаграмме:

Память

Я буду ссылаться на эти местоположения (и целые числа, хранящиеся в них) по их меткам на этой диаграмме.

Инициализация:

Инициализация

Указатель инструкций ( IP ) начинается в верхнем левом углу и идет на восток. Указатель памяти ( MP ) начинается с IN .

Во-первых, ?читает число из ввода и сохраняет его в IN . IP остается на голубом пути, отражаемый \. Последовательность "&(перемещает MP назад и влево (к A ), копирует значение из IN в A и уменьшает его.

Затем IP выходит из одной стороны шестиугольника и снова входит в другую сторону (на зеленый путь). Он выполняет '+который перемещает MP в B и копирует то , что было в . перенаправляет IP на запад.<

Факториал:

Я вычисляю факториал особым образом, так что возведение в квадрат это легко. Я храню n-1!в B и C следующим образом.

Факториал

Указатель инструкций начинается с синего пути в восточном направлении.

='меняет направление МП и перемещает его назад к C . Это эквивалентно тому, чтобы {=иметь, =где это было полезно позже.

&{копирует значение из к C , затем перемещает MP обратно в . Затем IP следует по зеленому пути, ничего не делая, прежде чем достигнуть красного пути, ударившись о оранжевый путь.\

С помощью (>мы уменьшаем A и перенаправляем IP East. Здесь он поражает ветку: <. Для положительного А мы продолжаем идти по оранжевой дорожке. В противном случае IP направляется на северо-восток.

'*перемещает MP в B и сохраняет A * C в B . Это (n-1)*(n-2)где первоначальный вклад был n. IP - затем поступает обратно в исходную петлю и продолжает декремента и не умножая до А достигает 0. (вычисления n-1!)

NB . В следующих циклах &сохраняет значение из B в C , так как C имеет положительное значение, сохраненное в нем. Это очень важно для вычисления факториала.

Выход:

Выход

Когда А достигает 0. Вместо этого ветвь направляет IP по синему пути.

=*реверсирует MP и сохраняет значение B * C в A . Затем IP выходит из шестиугольника и снова входит в зеленый путь; выполнение "%. Это перемещает MP в OUT и вычисляет A mod IN или (n-1!)² mod n.

Следующее {"действует как запрет, так как они отменяют друг друга. !печатает окончательный вывод и *+'(выполняются до завершения: @.

После выполнения (с вводом 5) память выглядит так:

Memory2

Прекрасные изображения потока управления были сделаны с использованием Hexagony Coloror Тимви .

Спасибо Мартину Эндеру за создание всех изображений, так как я не смог сделать это на своем ПК.

H.PWiz
источник
Что вы используете для этих диаграмм памяти? Я видел Esoteric IDE, но не смог заставить его работать ...
NieDzejkob
@NieDzejkob тебе лучше спросить Мартина в чате, так как он все равно сделал их для меня.
H.PWiz
@NieDzejkob Да, диаграмма памяти может быть экспортирована из EsoIDE. chat.stackexchange.com/rooms/27364/… если вы хотите поговорить об этом еще немного.
Мартин Эндер
34

Морнингтон Полумесяц , 2448 байт

Мы вернулись в Лондон!

Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Hammersmith
Take Circle Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take Circle Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Victoria
Take Circle Line to Temple
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Victoria
Take Circle Line to Aldgate
Take Circle Line to Victoria
Take Circle Line to Victoria
Take District Line to Upminster
Take District Line to Embankment
Take Circle Line to Embankment
Take Northern Line to Angel
Take Northern Line to Moorgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take District Line to Upney
Take District Line to Cannon Street
Take District Line to Acton Town
Take District Line to Acton Town
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Hammersmith
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Ruislip
Take Piccadilly Line to Ruislip
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Mornington Crescent

Timwi был очень любезен, чтобы реализовать станции управления потоками Templeи Angelв Esoteric IDE, а также добавить ввод и анализ целочисленных значений в спецификацию языка.

Этот, вероятно, лучше, чем «Hello, World!», Потому что на этот раз я написал сценарий CJam, чтобы помочь мне найти кратчайший путь между любыми двумя станциями. Если вы хотите использовать его (хотя я не знаю, почему кто-то захочет ...), вы можете воспользоваться онлайн-переводчиком . Вставьте этот код:

"Mornington Crescent"
"Cannon Street"
]qN/{'[/0=,}$:Q;{Q{1$#!}=\;_oNo'[/1>{']/0="[]"\*}%}%:R;NoQ{R\f{f{\#)}:+}:*},N*

Здесь первые две строки - это станции, которые вы хотите проверить. Также вставьте содержимое этой вставки в окно ввода.

Вывод покажет вам, какие линии доступны на этих двух станциях, а затем список всех станций, которые соединяют эти две станции, отсортированные по длине названий станций. Он показывает их все, потому что иногда лучше использовать более длинное имя, либо потому, что оно позволяет использовать более короткую линию, либо потому, что станция особенная (например, Банк или Храм), так что вы хотите ее избежать. Есть некоторые крайние случаи, когда две станции не соединены какой-либо другой станцией (в частности, линии Метрополитен и Район никогда не пересекаются), и в этом случае вам придется выяснить что-то еще. ;)

Что касается фактического кода MC, он основан на квадратично-факториальном подходе, как и многие другие ответы, потому что MC имеет умножение, деление и по модулю. Также я подумал, что один цикл будет удобен.

Одна из проблем заключается в том, что циклы являются циклами do-while, а уменьшение и увеличение является дорогостоящим, поэтому я не могу легко вычислить (n-1)!(для n > 0). Вместо этого я вычисляю, n!а затем делю nна в конце. Я уверен, что есть лучшее решение для этого.

Когда я начал писать это, я подумал, что хранение -1в Hammersmith было бы хорошей идеей, поэтому я могу уменьшить цену дешевле, но в итоге это может стоить больше, чем сэкономлено. Если я найду терпение, чтобы повторить это, я мог бы попытаться просто держать -1в Upminster, чтобы я мог использовать Hammersmith для чего-то более полезного.

Мартин Эндер
источник
10
Лондонский Тьюринг завершен?
Рохан Джхунджхунвала
1
@RohanJhunjhunwala вероятно
Мартин Эндер
Вау! Мне нравится видеть хорошо продуманные вопросы. Мне особенно нравится видеть вопросы, где вы должны написать программу, чтобы написать программу.
Rohan Jhunjhunwala
27

Brachylog (V2), 1 байт

ṗ

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

Брахилог (V1), 2 байта

#п

При этом используется встроенный предикат #p - Prime, который ограничивает его ввод простым числом.

Brachylog - моя попытка создать версию Prolog для Code Golf, которая является декларативным языком для гольфа Code, в котором используется возврат и объединение.

Альтернативное решение без встроенного: 14 байтов

ybbrb'(e:?r%0)

Вот разбивка кода выше:

y            The list [0, …, Input]
bbrb         The list [2, …, Input - 1]
'(           True if what's in the parentheses cannot be proven; else false
     e           Take an element from the list [2, …, Input - 1]
     :?r%0       The remainder of the division of the Input but that element is 0
)
Fatalize
источник
1
Возможно, вы захотите отредактировать версию этого в Brachylog 2 и в посте, теперь, когда синтаксис короче байта.
1
@ ais523 Правда, готово.
фатализировать
Отвечает ли Брахилог 2 задним числом?
Скотт Милнер
1
@ScottMilner Да, но это явно разрешено в этой задаче: «В отличие от наших обычных правил, не стесняйтесь использовать язык (или языковую версию), даже если он новее этой задачи»
Fatalize
26

Haskell, 49 байтов

Используя следствие xnor к теореме Вильсона :

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
Линн
источник
Не будет ли это сделать короче main=interact$\n-> ...?
Джон Дворак
2
Противоположно, нет! Учтите, что вам нужно interact...readгде-то там, что делает его намного длиннее, чем просто readLn. Зачастую doнотация может быть более краткой, чем вы могли бы ожидать, особенно когда альтернативой является лямбда.
Линн
24

Лабиринт , 29 байт

1
?
:
}  +{%!@
(:'(
 } {
 :**

Читает целое число из STDIN и выводит ((n-1)!)^2 mod n. Теорема Вильсона довольно полезна для этой задачи.

Программа начинается в верхнем левом углу, начиная с 1 которого умножает вершину стека на 10 и добавляет 1. Это способ Лабиринта строить большие числа, но, поскольку стеки Лабиринта заполнены нулями, конечный эффект такой, как если бы мы просто нажал 1.

?затем читает nиз STDIN и :дублирует его. }переходит nна вспомогательный стек, который будет использоваться в конце для модуля. (затем декрементыn , и мы готовы начать вычисление квадрата факториала.

Наш второй : (дубликат) находится на стыке, и здесь вступают в игру функции управления потоком данных Лабиринта. На перекрестке после выполнения инструкции, если вершина стека положительна, мы поворачиваем направо, для отрицательного мы поворачиваем налево, а для нуля - прямо. Если вы попытаетесь повернуть, но ударите стену, Лабиринт заставит вас повернуть в другом направлении.

Поскольку n = 1, поскольку вершина стека nуменьшается, или 0мы идем прямо вперед. Затем мы нажимаем на запрет, 'за которым следует еще один декрет, (который ставит нас на -1. Это отрицательно, поэтому мы поворачиваем налево, выполняя +plus ( -1 + 0 = -1), {чтобы перейти nот вспомогательного стека к основному и %по модулю ( -1 % 1 = 0). Затем мы выводим с !и заканчиваем с @.

На n > 1втором :мы повернем направо. Затем мы перемещаем }наш скопированный счетчик циклов во вспомогательный стек, дублируем :и умножаем дважды **, прежде чем сдвинуть счетчик назад {и уменьшить его (. Если мы все еще уверены, что мы пытаемся повернуть направо, но не можем, поэтому Лабиринт заставляет нас повернуть налево, продолжая цикл. В противном случае вершина стека - это наш счетчик цикла, который был уменьшен до 0, который мы +добавляем к нашему вычисленному ((n-1)!)^2. Наконец, мы nвернемся назад {по модулю %, выводим !и завершаем работу @.

Я сказал, что 'это не работает, но его также можно использовать для отладки. Запуск с -dфлагом, чтобы увидеть состояние стека каждый раз, когда 'передается!

Sp3000
источник
2
Квадрат факториала - это действительно крутой трюк :)
Линн
@ Mauris Спасибо! Мне нужно отдать должное, где это происходит - я впервые увидел трюк, используемый xnor здесь
Sp3000
5
Yay, первый ответ Лабиринт не написан мной! :)
Мартин Эндер
24

Утилиты Bash + GNU, 16

  • 4 байта сохранены благодаря @Dennis

  • 2 байта сохранены благодаря @Lekensteyn

factor|awk NF==2

Ввод - одна строка, взятая из STDIN. Вывод - пустая строка для фальси и непустая строка для истины. Например:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
Цифровая травма
источник
2
Круто, узнал о другом coreutil. Вы можете удалить два символа, посчитав количество полей:factor|awk NF==2
Lekensteyn
@Lekensteyn - спасибо - по какой-то причине я пропустил ваш комментарий раньше :)
Цифровая травма
Я собирался опубликовать что-то похожее, только дольше и без AWK. Красиво сделано.
Дэвид Конрад
21

Java, 126 121 байт

Я думаю, нам нужен ответ Java для табло ... так вот простой цикл пробного деления:

class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}

Как обычно для Java, требование «полной программы» делает это намного больше, чем было бы, если бы это была функция, в основном из-за mainсигнатуры.

В развернутом виде:

class P{
    public static void main(String[]a){
        int i=2,n=Short.valueOf(a[0]);
        for(;i<n;)
            n=n%i++<1?0:n;
        System.out.print(n>1);
    }
}

Редактировать: Исправлено и изменено Петром в комментариях. Спасибо!

Geobits
источник
Багги: он сообщает, что 1это главное. В противном случае можно было бы сэкономить 4 символа, убрав pи сказавfor(;i<n;)n=n%i++<1?0:n;System.out.print(n>0);
Питер Тейлор
2
OTOH class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}работает
Питер Тейлор
6
изменение строки 3 на 'long i = 2, n = Long.valueOf (a [0]); `не приводит к изменению длины, но расширяет диапазон допустимых входных данных.
Джеймс К Полк
4
Вместо .valueOfвы можете использовать new, как в new Short(a[0]), или new Long(a[0]), что немного короче.
ECS
3
Вы можете сохранить 4 байта, используя интерфейс и сбросив publicмодификатор.
RamenChef
18

Brain-Flak , 112 108 байт

({}[()]){((({})())<>){{}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}}}<>{{}}([]{})

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

Как это устроено

Первоначально первый стек будет содержать положительное целое число n , второй стек будет пустым.

Начнем с уменьшения n следующим образом.

(
  {}      Pop n.
  [()]    Yield -1.
)       Push n - 1.

n = 1

Если n = 1 равно нулю, цикл while

{
  ((({})())<>)
  {
    {}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}
  }
}

полностью пропущен Наконец, оставшийся код выполняется.

<>    Switch to the second stack (empty).
{}    Pop one of the infinite zeroes at the bottom.
{<>}  Switch stacks while the top on the active stack is non-zero. Does nothing.
(
  []    Get the length of the active stack (0).
  {}    Pop another zero.
)     Push 0 + 0 = 0.

n> 1

Если n - 1 не равно нулю, мы входим в цикл, который n = 1 пропускает. Это не «настоящий» цикл; код выполняется только один раз. Достигается следующее.

{                   While the top of the active stack is non-zero:
  (
    (
      ({})                Pop and push n - 1.
      ()                  Yield 1.
    )                   Push n - 1 + 1 = n.
    <>                  Switch to the second stack. Yields 0.
  )                   Push n + 0 = n.
                      We now have n and k = n - 1 on the first stack, and n on
                      the second one. The setup stage is complete and we start
                      employing trial division to determine n's primality.
  {                   While the top of the second stack is non-zero:
    {}                  Pop n (first run) or the last modulus (subsequent runs),
                        leaving the second stack empty.
    <>                  Switch to the first stack.
    (
      (
        {}                  Pop n from the first stack.
        <
          (
            (
              {}              Pop k (initially n - 1) from the first stack.
              [()]            Yield -1.
            )               Push k - 1 to the first stack.
            ()              Yield 1.
            <>              Switch to the second stack.
          )               Push k - 1 + 1 = k on the second stack.
        >               Yield 0.
      )               Push n + 0 = n on the second stack.
      <>              Switch to the first stack.
    )               Push n on the first stack.
    <>              Switch to the second stack, which contains n and k.
                    The first stack contains n and k - 1, so it is ready for
                    the next iteration.
    {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}  Compute and push n % k.
  }               Stop if n % k = 0.
}               Ditto.

n% k вычисляется с использованием 42-байтового алгоритма модуля из моего ответа теста делимости .

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

<>    Switch to the first stack, which contains n and k - 1, where k is the
      largest integer that is smaller than n and divides n evenly.
      If (and only if) n > 1 is prime, k = 1 and (thus) k - 1 = 0.
{     While the top of the first stack is non-zero:
  {}    Pop it.
}     This pops n if n is prime, n and k - 1 if n is composite.
(
  []    Yield the height h of the stack. h = 1 iff n is prime).
  {}    Pop 0.
)     Push h + 0 = h.
Деннис
источник
2
Вам не нужно вставлять последние 0 в стек, так как истинного 1 сверху достаточно; таким образом вы можете сохранить два байта, удалив последний {}.
Стивен Х.
1
Хм, я порваюсь С одной стороны, вопрос гласит, что результат должен состоять исключительно из истинного или ложного значения и 1 0представляет собой два значения. С другой стороны, мы принимаем массивы до тех пор, пока язык считает их правдивыми или ложными, а множественные элементы стека - самая близкая вещь, которую Brain-Flak имеет к массивам. Может быть стоит принять это к мета.
Деннис
Я проверил с создателем Brain-Flak, что 1 0это правда. chat.stackexchange.com/transcript/message/32746241#32746241
Стивен Х.
3
Соответствующее обсуждение мета: Истина в Brain-Flak и аналогичных основанных на стеке языках
Деннис
17

R, 37 29 байт

n=scan();cat(sum(!n%%1:n)==2)

Использует пробное деление. scan()читает целое число из STDIN и cat()записывает в STDOUT.

Мы генерируем вектор длины, nсостоящий из целых чисел от 1 до nпо модулю n. Мы проверяем, равно ли каждое из них 0, с помощью negating ( !), которое возвращает логическое значение, которое истинно, когда число равно 0, и ложно, когда оно больше 0. Сумма логического вектора - это число истинных элементов, и для простых чисел мы ожидаем единственные ненулевые модули равны 1, и nпоэтому мы ожидаем, что сумма будет равна 2.

Сохранено 8 байтов благодаря flodel!

Алекс А.
источник
С f=function(x)sum(!x%%1:x)==2его помощью можно сделать это за 28 байтов.
Мутадор
2
@ AndréMuta Для этой задачи все материалы должны быть полными программами, а не просто функциями. Спасибо за предложение, хотя.
Алекс А.
17

TI-BASIC, 12 байтов

2=sum(not(fPart(Ans/randIntNoRep(1,Ans

Довольно просто. randIntNoRep(дает случайную перестановку всех целых чисел от 1 до Ans.

Это немного нарушает правила; потому что списки в TI-BASIC ограничены 999 элементами, которые я интерпретировал

Предположим, что входные данные могут быть сохранены в вашем типе данных

Это означает, что можно предположить, что все типы данных соответствуют входным данным. ОП согласен с этой интерпретацией.

Раствор 17 байт , который на самом деле работает до 10 ^ 12 или так:

2=Σ(not(fPart(Ans/A)),A,1,Ans
lirtosiast
источник
@toothbrush TI-BASIC - это токенизированный язык, поэтому каждый токен здесь равен одному байту, за исключением randIntNoRep(двух.
lirtosiast
+1 Ах, я никогда раньше не видел TL-BASIC. Спасибо, что сообщили мне
Зубная щетка
1
Хотя, это немного несправедливо, не так ли ...? Я должен написать язык игры в гольф, который требует только 1-4 байта (идентификатор вопроса), а затем параметры. Он выберет лучший ответ на понятном ему языке, выполнит его (передав любые параметры) и вернет результат ... Интересно, нарушает ли это правила? :-)
Зубная щетка
@toothbrush В защиту TI-BASIC: для переводчика это не более несправедливо, чем односимвольные команды Pyth и CJam, а TI-BASIC более читабелен.
lirtosiast
1
Правда. Мне не нравятся такие языки, поскольку решения практически на всех других языках длиннее ... хотя недавно я победил CJam с VB6 ! : -]
Зубная щетка
15

PARI / GP, 21 байт

print(isprime(input))

Работает на смехотворно большие входы, потому что именно такие вещи предназначены для PARI / GP.

Линн
источник
6
isprimeделает APR-CL доказательством первичности, поэтому немного замедляется, поскольку входные данные становятся очень большими. ispseudoprime(input)выполняет вероятный первичный тест AES BPSW, который будет намного быстрее для более чем 100 цифр. До сих пор нет известных контрпримеров после 35 лет. Версия 2.1 и более ранние версии Pari, выпущенные до 2002 года, используют другой метод, который может легко дать ложные результаты, но никто не должен использовать это.
DanaJ
15

TI-BASIC, 24 байта

Обратите внимание, что программы TI-Basic используют систему токенов, поэтому подсчет символов не возвращает действительное значение байта программы.

Upvote Томас Ква ответ , это лучше.

:Prompt N
:2
:While N≠1 and fPart(N/Ans
:Ans+1
:End
:N=Ans

Образец:

N=?1009
                         1
N=?17
                         1
N=?1008
                         0
N=?16
                         0

Теперь возвращает, 0если не простое число, или 1если это так.

Zenohm
источник
3
Разве квадратный корень не является оптимизацией, которая вам не нужна, чтобы программа была правильной?
Мартин Эндер,
Зачем вам нужно делить на два?
Geobits
Я всегда люблю ответы TI-BASIC.
Грант Миллер
15

Стека кошек , 62 + 4 = 66 байт

*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Должен запускаться с -lnфлагами командной строки (следовательно, +4 байта). Принты 0для составных чисел и 1простых чисел.

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

Я думаю, что это первая нетривиальная программа Stack Cats.

объяснение

Краткое введение в Stack Cats:

  • Stack Cats работает с бесконечной лентой стеков, а головка ленты направлена ​​на текущий стек. Каждый стек изначально заполнен бесконечным количеством нулей. Обычно я игнорирую эти нули в своей формулировке, поэтому, когда я говорю «дно стека», я имею в виду самое низкое ненулевое значение, а если я говорю «стек пуст», я имею в виду, что на нем только нули.
  • Перед запуском программы a -1помещается в начальный стек, а затем весь ввод помещается поверх этого. В этом случае из-за -nфлага входные данные читаются как десятичное целое число.
  • В конце программы текущий стек используется для вывода. Если -1внизу есть значок, он будет проигнорирован. Опять же, из-за -nфлага значения из стека просто печатаются как десятичные целые числа, разделенные переводом строки.
  • Stack Cats - это обратимый программный язык: любой фрагмент кода можно отменить (без отслеживания явной истории Stack Cats). Точнее говоря, чтобы перевернуть любой кусок кода, вы просто отражаете его, например, <<(\-_)становитесь (_-/)>>. Эта цель разработки накладывает довольно жесткие ограничения на то, какие операторы и конструкции потоков управления существуют в языке, и какие функции можно вычислять в состоянии глобальной памяти.

  • В довершение всего, каждая программа Stack Cats должна быть самосимметричной. Вы можете заметить, что это не относится к приведенному выше исходному коду. Вот для чего этот -lфлаг: он неявно отражает код слева, используя первый символ для центра. Следовательно, фактическая программа:

    [<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Эффективное программирование всего кода крайне нетривиально и не интуитивно понятно, и еще не совсем понятно, как человек может это сделать. Мы грубо форсировали такую ​​программу для более простых задач, но не смогли бы подобраться к ней вручную. К счастью, мы нашли базовый шаблон, который позволяет игнорировать одну половину программы. Хотя это, безусловно, неоптимально, в настоящее время это единственный известный способ эффективного программирования в Stack Cats.

Таким образом, в этом ответе шаблон указанного шаблона выглядит следующим образом (есть некоторые различия в том, как он выполняется):

[<(...)*(...)>]

Когда программа запускается, стековая лента выглядит так (например, для ввода 4):

     4    
... -1 ...
     0
     ^

В [движении верхней части стека влево (и лента головы вместе) - мы называем это «толкая». И <движется лента в одиночку. Итак, после первых двух команд мы получили следующую ситуацию:

...   4 -1 ...
    0 0  0
    ^

Теперь (...)это цикл, который можно довольно легко использовать в качестве условного: цикл вводится и остается только тогда, когда вершина текущего стека положительна. Поскольку в настоящее время он равен нулю, мы пропускаем всю первую половину программы. Сейчас центр команды есть *. Это просто XOR 1, то есть он переключает младший значащий бит вершины стека, и в этом случае превращает 0в 1:

... 1 4 -1 ...
    0 0  0
    ^

Теперь мы сталкиваемся с зеркальным отображением (...). На этот раз в верхней части стека является положительным , и мы делаем ввести код. Прежде чем мы рассмотрим, что происходит в скобках, позвольте мне объяснить, как мы будем заключать в конце: мы хотим убедиться, что в конце этого блока у нас снова будет положительное значение на ленте (так, чтобы цикл завершается после одной итерации и используется просто как линейный условный оператор), что стек справа содержит вывод и что стек справа от этого содержит a -1. Если это так, мы покидаем цикл, >перемещаемся к выходному значению и ]помещаем его в -1так, чтобы у нас был чистый стек для вывода.

Ничего не поделаешь. Теперь внутри скобок мы можем делать все, что захотим, чтобы проверить первичность, при условии, что мы гарантируем, что все настроено, как описано в предыдущем параграфе в конце (что может быть легко сделано с некоторым толчком и движением ленты). Сначала я попытался решить проблему с помощью теоремы Уилсона, но в итоге получилось более 100 байтов, потому что факториальное вычисление в квадрате на самом деле довольно дорого в Stack Cats (по крайней мере, я не нашел короткого пути). Так что вместо этого я пошел с пробным разделением, и это действительно оказалось намного проще. Давайте посмотрим на первый линейный бит:

>:^]

Вы уже видели две из этих команд. Кроме того, :меняются два верхних значения текущего стека и ^XORs второе значение в верхнее значение. Это создает :^общий шаблон для дублирования значения в пустом стеке (мы вытягиваем ноль поверх значения, а затем превращаем ноль в 0 XOR x = x). Итак, после этого раздел нашей ленты выглядит так:

         4    
... 1 4 -1 ...
    0 0  0
         ^

Алгоритм пробного деления, который я реализовал, не работает для ввода 1, поэтому в этом случае мы должны пропустить код. Мы можем легко сопоставить 1с 0и всем остальным положительных значений с *, так вот как мы это делаем:

*(*...)

То есть мы превращаемся 1в 0пропускаемую большую часть кода, если мы действительно получим 0, но внутри мы немедленно отменим, *чтобы мы вернули наше входное значение. Нам просто нужно еще раз убедиться, что мы заканчиваем положительным значением в конце скобок, чтобы они не начинали цикл. Внутри условного выражения мы перемещаем один стек вправо с помощью >и затем запускаем основной цикл деления проб:

{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}

Скобки (в отличие от круглых скобок) определяют цикл другого типа: это цикл «do-while», то есть он всегда выполняется по крайней мере для одной итерации. Другое отличие - условие завершения: при входе в цикл Stack Cat запоминает верхнее значение текущего стека ( 0в нашем случае). Цикл будет выполняться до тех пор, пока это же значение снова не появится в конце итерации. Это удобно для нас: в каждой итерации мы просто вычисляем остаток от следующего потенциального делителя и перемещаем его в этот стек, в котором мы запускаем цикл. Когда мы находим делитель, остаток равен 0и цикл останавливается. Мы попробуем делители, начиная с, n-1а затем уменьшим их до 1. Это означает, что а) мы знаем, что это закончится, когда мы достигнем1самое позднее и б) мы можем затем определить, является ли число простым или нет, проверяя последний делитель, который мы пробовали (если это 1простое число, в противном случае это не так).

Давайте доберемся до этого. В начале есть короткий линейный участок:

<-!<:^>[:

Вы знаете, что большинство из этих вещей делают сейчас. Новые команды есть -и !. Stack Cats не имеет операторов увеличения или уменьшения. Однако он имеет -(отрицание, т.е. умножение на -1) и !(побитовое НЕ, т.е. умножение на -1и уменьшение). Они могут быть объединены в приращение !-или уменьшение -!. Таким образом, мы уменьшаем копию nверхней части -1, затем делаем еще одну копию nв стеке слева, затем извлекаем новый пробный делитель и помещаем его внизу n. Итак, на первой итерации мы получаем это:

      4       
      3       
... 1 4 -1 ...
    0 0  0
      ^

На последующих итерациях 3завещание будет заменено следующим делителем теста и т. Д. (Тогда как две копии nвсегда будут иметь одинаковое значение в этой точке).

((-<)<(<!-)>>-_)

Это вычисление по модулю. Поскольку циклы заканчиваются на положительных значениях, идея состоит в том, чтобы начинать -nи многократно добавлять пробный делитель dк нему, пока мы не получим положительное значение. Как только мы это сделаем, мы вычтем результат из, dи это даст нам остаток. Сложность в том, что мы не можем просто поместить -nвершину стека и запустить цикл, который добавляет d: если вершина стека отрицательна, цикл не будет введен. Таковы ограничения обратимого языка программирования.

Поэтому, чтобы обойти эту проблему, мы начинаем с nвершины стека, но отрицаем ее только на первой итерации. Опять же, это звучит проще, чем оказывается ...

(-<)

Когда вершина стека положительна (т. Е. Только на первой итерации), мы ее отрицаем -. Тем не менее, мы не можем просто сделать, (-)потому что тогда мы не будем выходить из цикла, пока не -будет применен дважды. Таким образом, мы перемещаем одну ячейку влево, <потому что мы знаем, что там есть положительное значение 1. Хорошо, теперь мы надежно отрицаем nпервую итерацию. Но у нас есть новая проблема: головка ленты на первой итерации теперь находится в другом положении, чем на любой другой. Нам нужно закрепить это, прежде чем мы пойдем дальше. Следующее <перемещает головку ленты влево. Ситуация на первой итерации:

        -4       
         3       
...   1  4 -1 ...
    0 0  0  0
    ^

И на второй итерации (помните, что мы добавили dодин раз -nсейчас):

      -1       
       3       
... 1  4 -1 ...
    0  0  0
    ^

Следующее условие снова объединяет эти пути:

(<!-)

На первой итерации головка ленты указывает на ноль, поэтому это полностью пропускается. На последующих итерациях головка ленты указывает на единицу, поэтому мы выполняем это, перемещаемся влево и увеличиваем там ячейку. Поскольку мы знаем, что ячейка начинается с нуля, теперь она всегда будет положительной, поэтому мы можем выйти из цикла. Это гарантирует, что мы всегда получим два стека слева от основного стека и теперь можем вернуться назад >>. Затем в конце цикла по модулю мы делаем -_. Вы уже знаете -. _заключается в вычитании , что ^должен XOR: если вершина стека aи значение Ниже bон заменяет aс b-a. Так как мы первый отрицается , aхотя, -_заменяет aс b+a, тем самым добавивd в наш текущий итог.

После завершения цикла (мы достигли положительного значения) лента выглядит так:

        2       
        3       
... 1 1 4 -1 ...
    0 0 0  0
        ^

Самое левое значение может быть любым положительным числом. На самом деле это число итераций минус одна. Теперь есть еще один короткий линейный бит:

_<<]>:]<]]

Как я уже говорил ранее, нам нужно вычесть результат из, dчтобы получить фактический остаток ( 3-2 = 1 = 4 % 3), поэтому мы просто сделаем _еще раз. Далее нам нужно очистить стек, который мы увеличивали слева: когда мы пробуем следующий делитель, он снова должен быть равен нулю, чтобы первая итерация работала. Таким образом, мы перемещаемся туда и помещаем это положительное значение в другой стек помощников, <<]а затем возвращаемся в наш операционный стек с другим >. Мы вытягиваем dс :и возвращаем его обратно на -1с, ]а затем перемещаем остаток в наш условный стек с <]]. Это конец цикла пробного деления: это продолжается до тех пор, пока мы не получим нулевой остаток, и в этом случае стек слева содержитnНаибольший делитель (кроме n).

После того, как цикл заканчивается, мы просто *<соединяем пути с входом 1снова. Он *просто превращает ноль в a 1, который нам понадобится чуть позже, и затем мы переходим к делителю с помощью <(так что мы находимся в том же стеке, что и для ввода 1).

На данный момент это помогает сравнить три различных вида входных данных. Во-первых, особый случай, n = 1когда мы не делали ничего из того, что делали в пробном подразделении:

         0    
... 1 1 -1 ...
    0 0  0
         ^

Тогда в нашем предыдущем примере n = 4составное число:

    2           
    1    2 1    
... 1 4 -1 1 ...
    0 0  0 0
         ^

И, наконец, n = 3простое число:

    3           
    1    1 1    
... 1 3 -1 1 ...
    0 0  0 0
         ^

Так что для простых чисел у нас есть 1в этом стеке, а для составных чисел у нас 0либо положительное число, либо больше, чем 2. Мы превращаем эту ситуацию в 0или, что 1нам нужно, с помощью следующего финального фрагмента кода:

]*(:)*=<*

]просто толкает это значение вправо. Затем *используются для упрощения условной ситуации значительно: переключая значащий бит, мы переходим 1(прайм) в 0, 0(композит) в положительное значение 1, а все остальные положительные значения по- прежнему будут оставаться положительными. Теперь нам просто нужно различать 0положительное. Вот где мы используем другое (:). Если вершина стека 0(и вход был простым), это просто пропускается. Но если вершина стека положительна (а входное значение было составным числом), это заменяет его на 1, так что теперь мы имеем 0для составного и1для простых чисел - только два разных значения. Конечно, они противоположны тому, что мы хотим вывести, но это легко исправить с помощью другого *.

Теперь осталось только восстановить шаблон стеков, ожидаемый нашей окружающей средой: ленточная головка с положительным значением, результат в верхней части стека справа и один -1в стеке справа от этого . Это для чего =<*. =меняет местами вершины двух соседних стеков, тем самым перемещая -1вправо от результата, например, для ввода 4снова:

    2     0       
    1     3       
... 1 4   1 -1 ...
    0 0 0 0  0
          ^

Затем мы просто двигаемся влево <и превращаем этот ноль в единицу с *. И это все.

Если вы хотите глубже изучить работу программы, вы можете воспользоваться опциями отладки. Либо добавьте -dфлаг и вставьте "туда, где вы хотите видеть текущее состояние памяти, например, как это , или используйте -Dфлаг, чтобы получить полный след всей программы . В качестве альтернативы вы можете использовать EsotericIDE от Timwi, который включает в себя интерпретатор Stack Cats с пошаговым отладчиком.

Мартин Эндер
источник
3
>:^]должен быть официальным логотипом Stack Cats
Алекс А.
14

Haskell, 54 байта

import Data.Numbers.Primes
main=readLn>>=print.isPrime

Ничего особенного объяснить.

Ними
источник
1
Та же оценка может быть достигнута (хотя и очень неэффективно) без внешних библиотек, используя теорему Уилсона:main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1
Линн
9
Мы можем даже сделать короче: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0это 49 байтов.
Линн
4
@ Маурис: Хорошо. Пожалуйста, опубликуйте это как отдельный ответ.
Ними,
14

Рубин, 15 + 8 = 23 байта

p$_.to_i.prime?

Образец прогона:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
manatwork
источник
Хе-хе, я знал, что где-то в Ruby будет встроено встроенное ПО, но я не мог потрудиться его найти, поэтому ответил в C. +1.
Уровень Река Сент
@steveverrill, я знал это, потому что это очень помогло Project Euler.
Манатур
14

JavaScript, 39 36 байт

Сохранено 3 байта благодаря продуктам ETH:

for(i=n=prompt();n%--i;);alert(1==i)

Отображает true для простого числа, false в противном случае.

Цикл for проверяет каждое число i от n-1 до делителя i . Если первый найденный делитель равен 1, то это простое число.

Предыдущее решение (39 байт):

for(i=n=prompt();n%--i&&i;);alert(1==i)

Как был оставлен ненужный тест:

for(i=2,n=prompt();n%i>0&&i*i<n;i++);alert(n%i>0) //49: Simple implementation: loop from 2 to sqrt(n) to test the modulo.
for(i=2,n=prompt();n%i>0&&i<n;i++);alert(n==i)    //46: Replace i*i<n by i<n (loop from 2 to n) and replace n%i>0 by n==i
for(i=2,n=prompt();n%i&&i<n;i++);alert(n==i)      //44: Replace n%i>0 by n%i
for(i=2,n=prompt();n%i&&i++<n;);alert(n==i)       //43: Shorten loop increment
for(i=n=prompt();n%--i&&i>0;);alert(1==i)         //41: Loop from n to 1. Better variable initialization.
for(i=n=prompt();n%--i&&i;);alert(1==i)           //39: \o/ Replace i>0 by i

Я разместил только 39-байтовое решение, потому что лучший ответ JavaScript был уже 40 байт.

Хеди
источник
2
Добро пожаловать в Программирование Пазлов и Code Golf!
Деннис
2
Отличный ответ! На &&iсамом деле ничего не делает в этой программе, так что вы можете удалить его.
ETHproductions
следует добавить n>1к последнему условию, хотя, если вы не хотите 1быть основным.
Тит
1
@Titus Если вход 1для цикла for будет выполнен n%--iодин раз: 1%0возвращает NaNи останавливает цикл. Когда alertвызывается iуже равно 0так 1==iвозвращается false.
Хеди
2
я <2 (и немного текста)
Scheintod
13

Улитки, 122

Ввод должен быть дан в унарном формате. Цифры могут быть любым сочетанием символов, кроме символов новой строки.

^
..~|!(.2+~).!~!{{t.l=.r=.}+!{t.!.!~!{{r!~u~`+(d!~!.r~)+d~,.r.=.(l!~u~)+(d!~l~)+d~,.l.},l=(.!.)(r!~u~)+(d!~!.r~)+d~,.r.!.

В этом языке сопоставления двухмерных шаблонов состояние программы состоит только из текущего местоположения сетки, набора ячеек, которые были сопоставлены, и положения в коде шаблона. Также незаконно путешествовать на подобранный квадрат. Это сложно, но можно хранить и извлекать информацию. Ограничение на перемещение в согласованную ячейку может быть преодолено путем обратного отслеживания, телепортации ( t) и утверждений ( =, !), которые оставляют сетку неизмененной после завершения.

Факторизация 25

Факторизация для нечетного составного числа начинается с выделения некоторого набора взаимно несмежных ячеек (синий на диаграмме). Затем из каждой желтой ячейки программа проверяет наличие одинакового количества не синих ячеек по обе стороны от соседней синей ячейки, перемещаясь туда и обратно между двумя сторонами. Диаграмма показывает этот шаблон для одной из четырех желтых ячеек, которые необходимо проверить.

Аннотированный код:

^                         Match only at the first character
..~ |                     Special case to return true for n=2
!(.2 + ~)                 Fail for even numbers
. !~                      Match 1st character and fail for n=1
!{                        If the bracketed pattern matches, it's composite.
  (t. l=. r=. =(.,~) )+   Teleport to 1 or more chars and match them (blue in graphic)
                          Only teleport to ones that have an unmatched char on each side.
                          The =(.,~) is removed in the golfed code. It forces the
                          teleports to proceed from left to right, reducing the
                          time from factorial to exponential.
  !{                      If bracketed pattern matches, factorization has failed.
    t . !. !~             Teleport to a square to the left of a blue square (yellow in diagram)
    !{                    Bracketed pattern verifies equal number of spaces to
                          the left or right of a blue square.
      {              
        (r!~ u~)+         Up...
        (d!~!. r~)+       Right...
        d~,               Down...
        . r . =.          Move 1 to the right, and check that we are not on the edge;
                          otherwise d~, can fall off next iteration and create and infinite loop
        (l!~ u~)+         Up...
        (d!~ l~)+         Left...
        d ~,              Down...
        . l .             Left 1
      } ,                 Repeat 0 or more times
      l  =(. !.)          Check for exactly 1 unused char to the left
      (r!~ u~)+           Up...
      (d!~!. r~)+         Right...
      d ~,                Down...
      . r . !.
    }
  }
}
feersum
источник
13

C 67 байт

i,n;main(p){for(scanf("%d",&i),n=i;--i;p=p*i*i%n);putchar(48+p%n);}

Печатает !1(значение Фальси, по определению Питера Тейлора ), 0 если (n-1)!^2 == 0 (mod n)и 1иначе.

РЕДАКТИРОВАТЬ : После некоторого обсуждения в чате, puts("!1"+p%n)кажется , кажется немного обманом, поэтому я заменил его. Результат на один байт длиннее.

РЕДАКТИРОВАТЬ : Исправлено для больших входов.

Более короткие решения

56 байт : как рекомендовано в комментариях pawel.boczarski, я мог бы получить ввод в унарном виде, прочитав количество аргументов командной строки:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);putchar(48+p%n);}

вызывая программу как

$ ./a.out 1 1 1 1 1
1                        <-- as 5 is prime

51 байт : если вы разрешите «вывод» с помощью кодов возврата:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
Линн
источник
Ваше решение может быть сокращено с использованием унарного представления (количество аргументов командной строки), как в моем решении, опубликованном. Вы можете сбрить несколько байтов при вызове scanf.
pawel.boczarski
puts("!1"+p%n)Как вы могли бы сделать a+bдля char*ценностей?
Эрик Outgolfer
Если строка "!1"начинается с адреса a, то a+1вы найдете строку "1".
Линн
@Lynn О, я думал , что это было для конкатенации (да, лучше оставить , что к strcat(const char*,const char*).)
Эрик Outgolfer
Не могли бы вы изменить p=p*i*i%nнаp*=i*i%n
Альберт Реншоу
12

Python 3, 59 байт

Теперь использует input()вместо аргументов командной строки. Благодаря @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
uno20001
источник
Использование входных данных input()будет намного короче
бета-распад,
Спасибо, я уже писал с использованием input (), но я забыл обновить свой ответ. Еще раз спасибо!
uno20001 11.09.15
4
52 байт: n=m=int(input()),print(all(n%m for m in range(2,n)))
Джон Лион
1
Ты серьезно. Потратьте 25 дополнительных символов для ускоренного квадратичного ускорения? Здесь мы ненавидим байты . Каждый час, минуту и ​​секунду нашей жизни мы проводим, избавляясь от девятнадцатого байта. (Шучу. Но мы не проводим оптимизацию времени, которая увеличивает продолжительность программы.)
CalculatorFeline
2
Используйте n%i<1вместо этого.
Эрик Outgolfer
12

APL, 40 13 байт

2=+/0=x|⍨⍳x←⎕

Trial деление с тем же алгоритмом , как мой R ответ . Мы назначаем xвходные данные из STDIN ( ⎕) и получаем остаток для xделения на каждое целое число от 1 до x. Каждый остаток сравнивается с 0, что дает нам вектор единиц и нулей, указывающих, какие целые числа делятся x. Это суммируется с помощью, +/чтобы получить количество делителей. Если это число равно 2, это означает, что единственными делителями являются 1 и x, и, таким образом,x является простым.

Алекс А.
источник
12

Python 2, 44

P=n=1
exec"P*=n*n;n+=1;"*~-input()
print P%n

Как и в ответе Python на Sp3000 , но избегает сохранения входных данных, считая переменную nот 1входного значения.

XNOR
источник
12

Шаблон метапрограммирования C ++. 166 131 119 байт.

Код компилируется, если константа простое, и не компилируется, если составная или 1.

template<int a,int b=a>struct t{enum{x=t<a,~-b>::x+!(a%b)};};
template<int b>struct t<b,0>{enum{x};};
int _[t<1>::x==2];

(все переводы строк, кроме финального, исключены в «реальной» версии).

Я полагаю, что «ошибка компиляции» является ошибочным возвращаемым значением для языка метапрограммирования. Обратите внимание, что он не связывает (поэтому, если вы передадите ему простое число, вы получите ошибки связывания) как полноценная программа на C ++.

Значение для проверки является целым числом в последней «строке».

живой пример .

Yakk
источник