Wierzcie lub nie, nie mamy jeszcze wyzwania golfowego dla prostego testu pierwotności . Chociaż może nie być to najciekawsze wyzwanie, szczególnie w przypadku „zwykłych” języków, w wielu językach może być niepraktyczne.

Kod Rosetta zawiera listy według języka idiomatycznych podejść do testowania pierwszorzędności, jedną z nich konkretnie z testem Millera-Rabina, a drugą z podziałem próby . Jednak „najbardziej idiomatyczny” często nie pokrywa się z „najkrótszym”. Aby uczynić Programming Puzzle i Code Golf stroną, na której można grać w golfa kodu, wyzwanie to polega na stworzeniu katalogu najkrótszego podejścia w każdym języku, podobnego do „Hello, World!” i zagraj w golfa na dobre! .

Co więcej, możliwość wdrożenia testu pierwszeństwa jest częścią naszej definicji języka programowania , więc wyzwanie to będzie również służyć jako katalog sprawdzonych języków programowania.

Zadanie

Napisz pełny program, który, biorąc pod uwagę ściśle dodatnią liczbę całkowitą n jako dane wejściowe, określa, czy n jest liczbą pierwszą, i wypisuje odpowiednio wartość prawdy czy fałszu .

Na potrzeby tego wyzwania liczba całkowita jest liczbą pierwszą, jeśli ma dokładnie dwa ściśle dodatnie dzielniki. Zauważ, że wyklucza to 1 , który jest jej jedynym ściśle dodatnim dzielnikiem.

Twój algorytm musi być deterministyczny (tj. Generować poprawne wyjście z prawdopodobieństwem 1) i teoretycznie powinien działać na dowolnie duże liczby całkowite. W praktyce można założyć, że dane wejściowe mogą być przechowywane w typie danych, o ile program działa na liczbach całkowitych od 1 do 255.

Wejście

• Jeśli Twój język jest w stanie czytać ze STDIN, akceptować argumenty wiersza poleceń lub dowolną alternatywną formę wprowadzania danych przez użytkownika, możesz odczytać liczbę całkowitą jako jej dziesiętną reprezentację, jednowymiarową (za pomocą wybranego znaku), tablicę bajtów (dużą lub little endian) lub jednobajtowy (jeśli jest to największy typ danych w Twoim języku).

• Jeśli (i tylko jeśli) Twój język nie może zaakceptować żadnego rodzaju danych wejściowych użytkownika, możesz na stałe zakodować dane wejściowe w swoim programie.

  W takim przypadku zakodowana liczba całkowita musi być łatwa do wymiany. W szczególności może pojawić się tylko w jednym miejscu w całym programie.

  W celu punktacji prześlij program odpowiadający wkładowi 1 .

Wynik

Dane wyjściowe należy zapisać do STDOUT lub najbliższej alternatywy.

Jeśli to możliwe, dane wyjściowe powinny składać się wyłącznie z wartości prawdziwości lub fałszu (lub ich reprezentacji ciągu), opcjonalnie po nich pojedyncza nowa linia.

Jedynym wyjątkiem od tej reguły jest stałe wyjście interpretera twojego języka, którego nie można stłumić, takie jak powitanie, kody kolorów ANSI lub wcięcia.

Dodatkowe zasady

• Nie chodzi o znalezienie języka z najkrótszym podejściem do testowania podstawowego, chodzi o znalezienie najkrótszego podejścia w każdym języku. Dlatego żadna odpowiedź nie zostanie oznaczona jako zaakceptowana.

• Zgłoszenia w większości języków będą oceniane w bajtach w odpowiednim wcześniej istniejącym kodowaniu, zwykle (ale niekoniecznie) UTF-8.

  Na przykład język Piet będzie oceniany w kodach, co jest naturalnym wyborem dla tego języka.

  Niektóre języki, takie jak Foldery , są trudne do zdobycia. W razie wątpliwości proszę pytać na Meta .

• W przeciwieństwie do naszych zwykłych zasad, możesz swobodnie używać języka (lub wersji językowej), nawet jeśli jest nowszy niż to wyzwanie. Jeśli ktoś chce to nadużyć, tworząc język, w którym pusty program wykonuje test pierwotności, gratuluje utorowania drogi dla bardzo nudnej odpowiedzi.

  Pamiętaj, że musi być tłumacz, aby można było przetestować zgłoszenie. Dozwolone jest (a nawet zachęcane) samodzielne pisanie tego tłumacza dla wcześniej niewdrożonego języka.

• Jeśli twój wybrany język jest trywialną odmianą innego (potencjalnie bardziej popularnego) języka, który ma już odpowiedź (pomyśl dialekty BASIC lub SQL, powłoki Unix lub trywialne pochodne Brainfuck, takie jak Headsecks lub Unary), rozważ dodanie uwagi do istniejącej odpowiedzi, która: to samo lub bardzo podobne rozwiązanie jest również najkrótsze w innym języku.

• Dozwolone są wbudowane funkcje testowania pierwotności . Wyzwanie to ma na celu skatalogowanie najkrótszego możliwego rozwiązania w każdym języku, więc jeśli krótsze jest użycie wbudowanego w swoim języku, skorzystaj z niego.

• O ile nie zostały one wcześniej anulowane, obowiązują wszystkie standardowe zasady gry w golfa , w tym http://meta.codegolf.stackexchange.com/q/1061 .

Na marginesie, proszę nie głosować nudnych (ale ważnych) odpowiedzi w językach, w których nie ma wiele do golfa; są one nadal przydatne w tym pytaniu, ponieważ próbuje skompilować katalog tak kompletny, jak to możliwe. Jednak przede wszystkim oceniaj odpowiedzi w językach, w których autor musiał włożyć wysiłek w golfa kodu.

Katalog

Fragment kodu na dole tego postu generuje katalog na podstawie odpowiedzi a) jako listy najkrótszych rozwiązań dla każdego języka oraz b) jako ogólnej tabeli wyników.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:

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

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 57617; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

Witaj świecie! , 13

hello, world!

Sześciokąt , 29 bajtów

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

Czytelna wersja tego kodu to:

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

Objaśnienie: Sprawdza, czy istnieje liczba od 2 do n-1, która dzieli n.

Inicjalizacja:

Napisz n w jednej komórce pamięci, a n-1 w drugiej:

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

Przypadek specjalny n = 1:

Wydrukuj 0 i zakończ

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

Pętla

Oblicz n% a i zmniejsz a. Zakończyć, jeśli a = 1 lub n% a = 0.

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

Przypadek a = 1:

Zwiększ 0 do 1, wydrukuj i zakończ. (Wskaźnik instrukcji biegnie w kierunku NE i zapętla się od wschodniego rogu do południowo-zachodniego rogu. A $ upewnia się, że ignoruje następne polecenie)

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

Przypadek a% n = 0:

Wydrukuj 0 i zakończ (wskaźnik instrukcji uruchamia SW i zapętla na górze do @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .

Sześciokąty , 218 92 58 55 bajtów

Uwaga: Ta odpowiedź została solidnie pobita przez rozwiązanie 4 o długości boku przez Etoplay.

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

Pierwszy w historii nietrywialny (tj. Nieliniowy) program sześciokątny! Opiera się na tym samym podejściu do kwadratu czynnikowego, co odpowiedź Labiryntu Sp3000 . Po rozpoczęciu pracy z sześciokątem o rozmiarze 10 udało mi się go skompresować do rozmiaru 5. Byłem jednak w stanie ponownie użyć trochę zduplikowanego kodu, a kod nadal zawiera sporo niepotrzebnych operacji, więc rozmiar 4 może po prostu dać.

Wyjaśnienie

Aby zrozumieć kod, najpierw musimy go rozwinąć. Heksagonia wstawia dowolny kod źródłowy do następnej wyśrodkowanej liczby heksagonalnej za pomocą no-ops ( .), czyli 61. Następnie przestawia kod na zwykły sześciokąt o odpowiednim rozmiarze:

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

Jest to dość mocno golfa ze skrzyżowaniem i nakładającymi się ścieżkami wykonania oraz wieloma wskaźnikami instrukcji (IP). Aby wyjaśnić, jak to działa, spójrzmy najpierw na wersję bez golfa, w której przepływ sterowania nie przechodzi przez krawędzie, używany jest tylko jeden adres IP, a ścieżki wykonywania są tak proste, jak to możliwe:

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

^{Uwaga dodatkowa: powyższy kod zaczyna się od wykonania pierwszego wiersza, który jest pełen braków operacji. Następnie, gdy adres IP dotrze do północno-wschodniej krawędzi, zawija się do lewego skrajnego rogu (the )), gdzie zaczyna się rzeczywisty kod.}

Zanim zaczniemy, słowo o układzie pamięci Hexagony. To trochę jak taśma Brainfuck na sterydach. W rzeczywistości nie jest to taśma, ale sama siatka heksagonalna (nieskończona), gdzie każda krawędź ma wartość całkowitą, która początkowo wynosi 0 (i w przeciwieństwie do standardowego Brainfuck, wartości są liczbami całkowitymi o dowolnej precyzji). W tym programie użyjemy czterech krawędzi:

Będziemy obliczyć silnię na brzegu A , odliczanie nasze wejście na skraju C i przechowywać kolejną kopię wejścia (dla modulo) na krawędzi D . B jest używany jako tymczasowa krawędź do obliczeń.

Wskaźnik pamięci (MP) zaczyna się na krawędzi A i wskazuje na północ (jest to ważne, aby przesunąć MP wokół siebie). Oto pierwszy fragment kodu:

)}?}=&{

)zwiększa krawędzi A na 1podstawę silni. }sprawia, że ​​MP wykonuje obrót w prawo, tj. przesuwa się do krawędzi C (wskazując na północny wschód). Tutaj czytamy dane wejściowe jako liczbę całkowitą z ?. Następnie skręcamy w prawo do krawędzi D za pomocą }. =odwraca MP, tak, że wskazuje na wierzchołku wspólnego z C . &kopiuje wartość z C (wejście) do D - wartość jest kopiowana od lewej, ponieważ bieżąca wartość nie jest dodatnia (zero). Wreszcie, wykonujemy MP wziąć lewej zawrócić do C z {.

Następnie <jest technicznie gałąź, ale wiemy, że bieżąca wartość jest dodatnia, więc adres IP zawsze skręci w prawo w kierunku >. Oddział hit z aktami ubocznych jak lustro, tak że porusza się poziomo IP znowu w kierunku (, który zmniejsza wartość w C .

Następna gałąź <jest teraz właściwie gałęzią. W ten sposób zapętlamy od n-1do 1. Podczas gdy bieżąca wartość w C jest dodatnia, IP skręca w prawo (aby wykonać pętlę). Gdy osiągniemy zero, skręci w lewo.

Spójrzmy na pętlę „body”. Są |to proste zwierciadła, >i <są również ponownie używane jako zwierciadła. Oznacza to, że rzeczywiste ciało pętli sprowadza się do

}=)&}=*}=

}przesuwa MP na krawędź B , =odwraca kierunek w stronę wierzchołka ABC . )zwiększa wartość: dotyczy to tylko pierwszej iteracji, w której wartość B jest wciąż równa zero: chcemy upewnić się, że jest dodatnia, tak aby następna instrukcja &kopiowała prawego sąsiada, tj. A , tj. bieżącą wartość silni obliczeń, do B .

}następnie przesuwa MP do A , =odwraca go ponownie w stronę wspólnego wierzchołka. *zwielokrotnia zarówno sąsiadów, czyli krawędzie B i C i zapisuje wynik w . Wreszcie, mamy kolejną, aby powrócić do C , wciąż stojąc naprzeciwko wierzchołka ABC .}=

Mam nadzieję, że można zobaczyć, jak to oblicza silnię n-1w A .

Więc teraz to zrobiliśmy, licznik pętli w C wynosi zero. Chcemy wyrównać silnię, a następnie wziąć moduł z danymi wejściowymi. Tak działa ten kod:

&}=*{&'%!@

Ponieważ C jest zero, &kopie lewy sąsiad, czyli silni w . przenosi się do B i zapisuje iloczyn dwóch egzemplarzach silnia (tj placu) w B . wraca do C , ale nie odwraca MP. Wiemy, że obecna wartość jest dodatnia, więc wejście kopie z D na C . MP do tyłu w prawo, czyli na . Pamiętaj, że plac jest silnia w B i wejście jest w C . Więc oblicza , dokładnie to, czego szukasz.}=*{&'%(n-1)!^2 % n!wypisuje wynik jako liczbę całkowitą (0 lub 1) i @kończy działanie programu.

Okej, ale to była wersja bez golfa. Co z wersją golfową? Musisz wiedzieć jeszcze dwie rzeczy o Hexagony:

1. Krawędzie się zawijają. Jeśli IP uderza w krawędź sześciokąta, przeskakuje na przeciwną krawędź. Jest to dwuznaczne, gdy IP uderza prosto w narożnik, więc uderzenie w narożnik działa również jak gałąź: jeśli bieżąca wartość jest dodatnia, IP przeskakuje do krawędzi siatki po prawej stronie, w przeciwnym razie do lewej strony.
2. W rzeczywistości jest 6 adresów IP. Każdy z nich zaczyna się w innym rogu, poruszając się wzdłuż krawędzi w kierunku zgodnym z ruchem wskazówek zegara. Tylko jeden z nich jest aktywny na raz, co oznacza, że ​​możesz po prostu zignorować pozostałe 5 adresów IP, jeśli ich nie chcesz. Możesz przejść do następnego adresu IP (w kolejności zgodnej z ruchem wskazówek zegara) za pomocą ]i do poprzedniego za pomocą [. (Możesz także wybrać konkretny za pomocą #, ale to na inny czas.)

Jest w nim także kilka nowych poleceń: \i /są jak mirrory |i ~mnożą bieżącą wartość przez -1.

Jak więc wersja bez golfa przekłada się na wersję z golfem? Liniowy kod konfiguracji )}?}=&{i podstawową strukturę pętli można znaleźć tutaj:

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

Teraz ciało pętli przecina krawędzie kilka razy, ale co najważniejsze, rzeczywiste obliczenia są przekazywane do poprzedniego adresu IP (który rozpoczyna się w lewym rogu, przesuwając się na północny wschód):

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

Po odbiciu od gałęzi w kierunku południowo-wschodnim, IP owija się wokół krawędzi do dwóch =w lewym górnym rogu (które razem nie dają op-op), a następnie odbija się od /. ~Odwraca znak aktualnej wartości, co jest ważne dla kolejnych iteracji. IP ponownie owija się wokół tej samej krawędzi i ostatecznie uderza w miejsce, w [którym kontrola zostaje przekazana drugiemu IP.

Ten teraz wykonuje, ~}=)&}=*}który odwraca negację, a następnie po prostu uruchamia ciało pętli bez golfa (minus =). Wreszcie uderza, ]które ręce kontrolują z powrotem do pierwotnego adresu IP. (Zauważ, że następnym razem, gdy wykonamy to w tym adresie IP, zacznie się od miejsca, w którym zostało przerwane, więc najpierw uderzy w róg. Potrzebujemy, aby bieżąca wartość była ujemna, aby adres IP wskoczył z powrotem na północno-zachodnią krawędź zamiast południowo-wschodniej).

Gdy oryginalne IP wznowi kontrolę, odbija się od \, wykonuje pozostałe, =a następnie uderza, >aby przejść do następnej iteracji w pętli.

Teraz naprawdę szalona część: co się dzieje, gdy pętla się kończy?

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

IP przesuwa się z północnego wschodu od <i owija się wokół północno-wschodniej przekątnej. Tak więc kończy się na tej samej ścieżce wykonania co body body ( &}=*}]). Co właściwie jest całkiem fajne, ponieważ dokładnie taki kod chcemy wykonać w tym momencie, przynajmniej jeśli dodamy inny =}(ponieważ }=}jest równoważny {). Ale w jaki sposób nie wchodzi to ponownie w wcześniejszą pętlę? Ponieważ ]zmiany do następnego adresu IP, który jest teraz (dotychczas nieużywanym) adresem IP, który zaczyna się w prawym górnym rogu, przesuwając się na południowy zachód. Stamtąd adres IP jest kontynuowany wzdłuż krawędzi, zawija się do lewego górnego rogu, przesuwa się w dół po przekątnej, odbija się od |i kończy na @podczas wykonywania ostatniego kawałka kodu liniowego:

=}&)('%!@

( )(Oczywiście nie można tego zrobić - musiałem dodać, (ponieważ )już tam był).

Uff ... co za bałagan ...

Pyth, 4 bajty

}QPQ

Odbitki Truelub False.

Siatkówka , 16 bajtów

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

Wypróbuj online!

Zacznijmy od klasycznego: wykrywanie liczb pierwszych za pomocą wyrażenia regularnego . Dane wejściowe należy podawać pojedynczo , przy użyciu dowolnego powtarzalnego znaku drukowalnego. Dla wygody zestaw testowy zawiera konwersję z dziesiętnej na jednoargumentową.

Program Retina składający się z pojedynczej linii traktuje tę linię jako wyrażenie regularne i wypisuje liczbę dopasowań znalezionych na wejściu, która będzie 0dla liczb zespolonych i 1liczb pierwszych.

Lookahead zapewnia, że ​​dane wejściowe nie są złożone: backtracking spróbuje wszystkich możliwych podciągów (co najmniej 2 znaków) (..+), a następnie lookahead spróbuje dopasować resztę danych wejściowych, powtarzając to, co zostało tutaj uchwycone. Jeśli jest to możliwe, oznacza to, że wejście ma dzielnik większy niż 1, ale który jest mniejszy niż sam. W takim przypadku negatywne spojrzenie w przód powoduje niepowodzenie dopasowania. W przypadku liczb pierwszych nie ma takiej możliwości, a mecz trwa.

Jedynym problemem jest to, że ten lookahead również akceptuje 1, więc wykluczamy to, dopasowując co najmniej dwa znaki do ...

CJam, 4 bajty

qimp

CJam ma wbudowany operator do testowania pierwotności.

HTML + CSS, 254 + n _max * 28 bajtów

Możemy sprawdzić pierwotność za pomocą wyrażeń regularnych. Mozilla ma @document, co jest zdefiniowane jako:

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

Aby filtrować elementy za pomocą CSS na podstawie bieżącego adresu URL. To jest pojedyncze przejście, więc musimy zrobić dwa kroki:

1. Uzyskaj wkład od użytkownika. To wejście musi jakoś znaleźć odzwierciedlenie w bieżącym adresie URL.
2. Odpowiedz użytkownikowi w możliwie najmniejszym kodzie.

1. Pierwsze wejście

Najkrótszym sposobem na uzyskanie danych wejściowych i przesłanie ich na adres URL jest GETformularz z polami wyboru. Do wyrażenia regularnego potrzebujemy tylko unikalnego ciągu, aby policzyć wyglądy.

Zacznijmy od tego (61 bajtów):

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

Otrzymaliśmy dwa unikalne <p>znaki wskazujące, czy wprowadzona liczba jest liczbą pierwszą (1), czy nie (0). Definiujemy również formę i jej działanie.

Po których następuje n _{maks. Pól} wyboru o tej samej nazwie (n _maks * 28 bajtów):

<input type=checkbox name=i>

Następnie element przesyłania (34 bajty):

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

2. Wyświetl odpowiedź

Potrzebujemy CSS (159 bajtów), aby wybrać <p>do wyświetlenia (1 lub 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}}

»Wypróbuj w codepen.io (tylko Firefox)

Pomoc, WarDoq! , 1 bajt

P

Wyjścia 1, jeśli wejście jest liczbą pierwszą, 0 w przeciwnym razie.

Sześciokąt , 28 bajtów

Ponieważ Etoplay absolutnie zaniepokoił mnie tym pytaniem , czułem, że muszę wygrać z jego jedyną inną odpowiedzią .

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

Wypróbuj online!

Używam Twierdzenia Wilsona, podobnie jak Martin w swojej odpowiedzi : Biorąc pod uwagę n, wyprowadzam(n-1!)² mod n

Tutaj rozwinął się program:

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

A oto czytelna wersja:

Wyjaśnienie:

Program składa się z trzech głównych etapów: inicjalizacji , czynników i wyników .

Model pamięci Hexagony jest nieskończoną sześciokątną siatką. Używam 5 lokalizacji pamięci, jak pokazano na tym schemacie:

Będę odnosić się do tych lokalizacji (i przechowywanych w nich liczb całkowitych) według ich etykiet na tym schemacie.

Inicjalizacja:

Wskaźnik instrukcji ( IP ) zaczyna się w lewym górnym rogu i idzie na wschód. Wskaźnik pamięci ( MP ) zaczyna się od IN .

Najpierw ?odczytuje liczbę z wejścia i zapisuje ją w IN . IP pozostaje na niebieskim ścieżce, co odzwierciedla \. Sekwencja "&(przesuwa MP z powrotem i w lewo (do A ), kopiuje wartość z IN do A i zmniejsza ją.

Następnie IP wychodzi z jednej strony sześciokąta i ponownie wchodzi na drugą stronę (na zieloną ścieżkę). Wykonuje '+który przesuwa MP do B i kopie, co było w . przekierowuje adres IP na zachód.<

Factorial:

Obliczam silnię w określony sposób, aby kwadratura była łatwa. Przechowuję n-1!w B i C w następujący sposób.

Wskaźnik instrukcji zaczyna się na niebieskiej ścieżce, kierując się na wschód.

='odwraca kierunek MP i przenosi go do tyłu C . Jest to równoważne z {=tym, =że później było to pomocne.

&{kopie wartości z do C , a następnie przenosi MP powrotem do . IP potem następuje zieloną ścieżkę, nic nie robić, przed osiągnięciem czerwoną drogę, uderzając i idzie na ścieżkę pomarańczowego.\

Za pomocą (>dekrementujemy A i przekierowujemy IP East. Tutaj trafi oddział: <. Dla pozytywnego A kontynuujemy pomarańczową ścieżkę. W przeciwnym razie adres IP zostanie skierowany na północny wschód.

'*przesuwa MP do B i przechowuje A * C w B . Tutaj (n-1)*(n-2)znajdowało się początkowe wejście n. IP następnie wchodzi z powrotem do pierwotnej pętli i kontynuuje zmniejszanie i pomnożenie aż A biegu 0. (informatyka n-1!)

NB : W kolejnych pętlach &przechowuje wartość z B w C , ponieważ C ma teraz zapisaną wartość dodatnią. Ma to kluczowe znaczenie dla obliczania silni.

Wynik:

Kiedy A osiągnie 0. Zamiast tego gałąź kieruje adres IP wzdłuż niebieskiej ścieżki.

=*Odwraca MP i przechowuje wartość B * C w A . Następnie IP wychodzi z sześciokąta i ponownie wchodzi na zieloną ścieżkę; wykonywania "%. To przesuwa MP do OUT i oblicza A mod IN , lub (n-1!)² mod n.

Następujące {"działania nie działają, ponieważ wzajemnie się anulują. !drukuje ostateczną moc i *+'(są wykonywane przed zakończeniem: @.

Po wykonaniu (z wejściem 5) pamięć wygląda następująco:

_{Piękne obrazy przepływu sterowania zostały wykonane przy użyciu Timwi za Hexagony Coloror .}

^{Dziękuję Martinowi Enderowi za wygenerowanie wszystkich obrazów, ponieważ nie mogłem tego zrobić na moim komputerze.}

Mornington Crescent , 2448 bajtów

Wróciliśmy do Londynu!

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 był tak miły, że wdrożył kontrolne stacje przepływu Templeoraz Angelw Esoteric IDE, a także dodał dane wejściowe i parsowanie liczb całkowitych do specyfikacji języka.

Ten jest prawdopodobnie lepiej golfowany niż „Witaj, świecie!”, Ponieważ tym razem napisałem skrypt CJam, który pomoże mi znaleźć najkrótszą drogę między dowolnymi dwoma stacjami. Jeśli chcesz go użyć (chociaż nie wiem, dlaczego ktoś chciałby ...), możesz skorzystać z internetowego tłumacza . Wklej ten kod:

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

Tutaj pierwsze dwie linie to stacje, które chcesz sprawdzić. Wklej także zawartość tej pastebin do okna wprowadzania.

Dane wyjściowe pokażą, które linie są dostępne na dwóch stacjach, a następnie listę wszystkich stacji, które łączą obie, posortowane według długości nazw stacji. Pokazuje je wszystkie, ponieważ czasem lepiej jest użyć dłuższej nazwy, albo dlatego, że pozwala ona na krótszą linię, albo dlatego, że stacja jest wyjątkowa (jak Bank lub Świątynia), więc chcesz jej uniknąć. Istnieją pewne przypadki skrajne, w których dwie stacje nie są połączone żadną inną stacją (w szczególności linie Metropolitan i District nigdy się nie krzyżują), w którym to przypadku musisz wymyślić coś innego. ;)

Jeśli chodzi o rzeczywisty kod MC, jest on oparty na podejściu kwadratowo-czynnikowym, jak wiele innych odpowiedzi, ponieważ MC ma mnożenie, dzielenie i modulo. Uznałem też, że wygodna byłaby pojedyncza pętla.

Jednym z problemów jest to, że pętle są pętlami „do while”, a zmniejszanie i zwiększanie jest kosztowne, więc nie mogę łatwo obliczyć (n-1)!(dla n > 0). Zamiast tego wykonuję obliczenia, n!a następnie dzielę według n. Jestem pewien, że istnieje na to lepsze rozwiązanie.

Kiedy zacząłem to pisać, pomyślałem, że przechowywanie -1w Hammersmith byłoby dobrym pomysłem, dzięki czemu mogę zmniejszyć koszty taniej, ale ostatecznie może to kosztować więcej niż zaoszczędziłem. Jeśli znajdę cierpliwość, aby to przerobić, może -1zamiast tego spróbuję po prostu zatrzymać się w Upminster, aby móc użyć Hammersmith do czegoś bardziej przydatnego.

Brachylog (V2), 1 bajt

ṗ

Wypróbuj online!

Brachylog (V1), 2 bajty

#p

Korzysta z wbudowanego predykatu #p - Prime, który ogranicza liczbę wejściową jako liczbę pierwszą.

Brachylog to moja próba stworzenia Prologu w wersji Code Golf, która jest deklaratywnym językiem kodu golfowego, który wykorzystuje backtracking i unifikację.

Alternatywne rozwiązanie bez wbudowanego: 14 bajtów

ybbrb'(e:?r%0)

Oto podział powyższego kodu:

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
)

Haskell, 49 bajtów

Używając następstwa xnora do twierdzenia Wilsona :

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0

Labirynt , 29 bajtów

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

Odczytuje liczbę całkowitą ze STDIN i wyprowadza ((n-1)!)^2 mod n. Twierdzenie Wilsona jest bardzo przydatne w tym wyzwaniu.

Program rozpoczyna się w lewym górnym rogu, zaczynając od 1pomnożenia górnej części stosu przez 10 i dodając 1. Jest to sposób budowania dużych liczb przez Labirynt, ale ponieważ stosy Labiryntu są wypełnione zerami, efekt końcowy jest taki, jakbyśmy właśnie nacisnął 1.

?następnie czyta nze STDIN i :kopiuje go. }przesuwa nsię na stos pomocniczy, który będzie używany na końcu dla modułu. (następnie zmniejszamy ni jesteśmy gotowi, aby rozpocząć obliczanie kwadratowego silni.

Nasz drugi :(duplikat) znajduje się na skrzyżowaniu, a tutaj pojawiają się funkcje sterowania przepływem Labiryntu. Na skrzyżowaniu po wykonaniu instrukcji, jeśli góra stosu jest dodatnia, skręcamy w prawo, dla ujemnego skręcamy w lewo, a dla zera idziemy prosto. Jeśli spróbujesz zawrócić, ale uderzysz w ścianę, Labirynt skręca w przeciwnym kierunku.

Ponieważ n = 1, ponieważ górna część stosu jest nzmniejszana, lub 0idziemy prosto. Następnie trafiliśmy na no-op, 'po którym nastąpił kolejny spadek, (który nas stawia -1. Jest to ujemne, więc skręcamy w lewo, wykonując +plus ( -1 + 0 = -1), {aby nwrócić z stosu pomocniczego do głównego i %modulo ( -1 % 1 = 0). Następnie wyprowadzamy !i kończymy za pomocą @.

Bo n > 1za drugim :skręcamy w prawo. Następnie przesuwamy }nasz skopiowany licznik pętli na stos pomocniczy, duplikujemy :i mnożymy dwa razy **, zanim cofniemy licznik do tyłu {i zmniejszamy (. Jeśli nadal jesteśmy pozytywni, próbujemy skręcić w prawo, ale nie możemy, więc Labirynt skręca w lewo, kontynuując pętlę. W przeciwnym razie górną częścią stosu jest nasz licznik pętli, który został zmniejszony do 0, co +dodajemy do naszych obliczonych ((n-1)!)^2. Wreszcie cofamy nsię z {modulo %, wyjściem !i zakończeniem @.

Powiedziałem, że 'to nie działa, ale może być również użyte do debugowania. Uruchom z -dflagą, aby zobaczyć stan stosu za każdym razem, gdy 'zostanie on przerzucony!

Narzędzia Bash + GNU, 16

• 4 bajty zapisane dzięki @Dennis

• 2 bajty zapisane dzięki @Lekensteyn

factor|awk NF==2

Dane wejściowe to jedna linia pobrana ze STDIN. Dane wyjściowe to pusty ciąg dla falsey i niepusty ciąg dla prawdy. Na przykład:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$

Java, 126 121 bajtów

Chyba potrzebujemy odpowiedzi Java na tablicę wyników ... więc oto prosta pętla podziału próbnego:

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);}}

Jak zwykle w Javie, wymóg „pełnego programu” sprawia, że ​​jest on znacznie większy niż byłby, gdyby był funkcją, głównie ze względu na mainpodpis.

W rozszerzonej formie:

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);
    }
}

Edycja: Naprawiono i ponownie zmieniono w komentarzach Peter. Dzięki!

Brain-Flak , 112 108 bajtów

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

Wypróbuj online!

Jak to działa

Początkowo pierwszy stos będzie zawierał dodatnią liczbę całkowitą n , drugi stos będzie pusty.

Zaczynamy od zmniejszenia n w następujący sposób.

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

n = 1

Jeśli n = 1 wynosi zero, pętla while

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

jest całkowicie pomijany. Na koniec wykonywany jest pozostały kod.

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

Jeśli n - 1 jest niezerowe, wchodzimy do pętli, która n = 1 pomija. To nie jest „prawdziwa” pętla; kod jest wykonywany tylko raz. Osiąga następujące.

{                   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 jest obliczane przy użyciu 42-bajtowego algorytmu modułu z mojej odpowiedzi testu podzielności .

Na koniec interpretujemy wyniki, aby określić pierwotność 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.

R, 37 29 bajtów

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

Wykorzystuje podział próbny. scan()odczytuje liczbę całkowitą ze STDIN i cat()zapisuje do STDOUT.

Generujemy wektor długości nskładający się z liczb całkowitych od 1 do nmodulo n. Sprawdzamy, czy każdy ma wartość 0, negując ( !), która zwraca wartość logiczną, która jest prawdziwa, gdy liczba wynosi 0, a fałsz, gdy jest większa niż 0. Suma wektora logicznego to liczba prawdziwych elementów, a dla liczb pierwszych oczekujemy jedynym niezerowym modułem jest 1, a nzatem oczekujemy, że suma będzie wynosić 2.

Zaoszczędzono 8 bajtów dzięki flodel!

TI-BASIC, 12 bajtów

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

Całkiem proste. randIntNoRep(daje losową permutację wszystkich liczb całkowitych od 1 do Ans.

To trochę wygina reguły; ponieważ listy w TI-BASIC są ograniczone do 999 elementów, które zinterpretowałem

Załóżmy, że dane wejściowe można zapisać w typie danych

co oznacza, że ​​można przyjąć, że wszystkie typy danych uwzględniają dane wejściowe. OP zgadza się z tą interpretacją.

Roztwór 17-bajtowy , który faktycznie działa aż do 10 ^ 12 lub tak:

2=Σ(not(fPart(Ans/A)),A,1,Ans

PARI / GP, 21 bajtów

print(isprime(input))

Działa w przypadku absurdalnie dużych nakładów, ponieważ do tego właśnie służy PARI / GP.

TI-BASIC, 24 bajty

Zauważ, że programy TI-Basic używają systemu tokenów, więc zliczanie znaków nie zwraca rzeczywistej wartości bajtów programu.

Zatwierdź odpowiedź Thomasa Kwa , jest lepsza.

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

Próba:

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

Teraz powraca, 0jeśli nie jest liczbą pierwszą lub 1jeśli tak jest.

Stack Cats , 62 + 4 = 66 bajtów

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

Musi być uruchamiany z -lnflagami wiersza poleceń (stąd +4 bajty). Wydruki 0liczb zespolonych i 1liczb pierwszych.

Wypróbuj online!

Myślę, że to pierwszy nietrywialny program Stack Cats.

Wyjaśnienie

Szybkie wprowadzenie do Stack Cats:

• Stack Cats działa na nieskończonej taśmie stosów, a głowica taśmy wskazuje na bieżący stos. Każdy stos jest początkowo wypełniony nieskończoną liczbą zer. Generalnie zignoruję te zera w moim sformułowaniu, więc kiedy mówię „dolna część stosu”, mam na myśli najniższą niezerową wartość i jeśli mówię „stos jest pusty”, to znaczy, że są na nim tylko zera.
• Przed uruchomieniem programu a -1jest umieszczany na początkowym stosie, a następnie na nim umieszczane jest całe wejście. W tym przypadku, ze względu na -nflagę, dane wejściowe są odczytywane jako liczba całkowita dziesiętna.
• Pod koniec programu bieżący stos jest używany do wyświetlania. Jeśli jest -1na dole, zostanie zignorowany. Ponownie, ze względu na -nflagę, wartości ze stosu są po prostu drukowane jako liczby całkowite dziesiętne oddzielone wierszem.
• Stack Cats to odwracalny język programu: każdy fragment kodu można cofnąć (bez Stack Cats śledzącego jawną historię). Mówiąc dokładniej, aby odwrócić dowolny fragment kodu, po prostu dublujesz go, np . <<(\-_)Staje się (_-/)>>. Ten cel projektowania nakłada dość surowe ograniczenia na to, jakie rodzaje operatorów i konstrukcje przepływu sterowania istnieją w języku i jakie funkcje można obliczyć na temat stanu pamięci globalnej.

• Podsumowując, każdy program Stack Cats musi być samosymetryczny. Możesz zauważyć, że nie dotyczy to powyższego kodu źródłowego. Do tego służy -lflaga: domyślnie odzwierciedla kod po lewej stronie, używając pierwszego znaku na środku. Stąd faktyczny program to:

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

Efektywne programowanie przy użyciu całego kodu jest wysoce nietrywialne i nieintuicyjne i tak naprawdę nie odkryłem jeszcze, jak człowiek może to zrobić. Brutalnie zmusiliśmy taki program do prostszych zadań, ale nie bylibyśmy w stanie zbliżyć się do niego ręcznie. Na szczęście znaleźliśmy podstawowy wzorzec, który pozwala zignorować połowę programu. Chociaż z pewnością nie jest to optymalne, obecnie jest to jedyny znany sposób skutecznego programowania w Stack Cats.

W tej odpowiedzi szablon tego wzorca jest następujący (istnieje pewna zmienność w sposobie jego wykonywania):

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

Po uruchomieniu programu taśma stosu wygląda następująco ( 4powiedzmy na wejściu ):

     4    
... -1 ...
     0
     ^

W [przesuwa wierzchu stosu po lewej stronie (a głowica taśmy wzdłuż) - nazywamy to „pchanie”. I <porusza głową taśmy. Po pierwszych dwóch poleceniach mamy następującą sytuację:

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

Teraz (...)jest to pętla, której można dość łatwo używać jako warunkowego: pętla jest wprowadzana i opuszczana tylko wtedy, gdy góra bieżącego stosu jest dodatnia. Ponieważ obecnie wynosi zero, pomijamy całą pierwszą połowę programu. Teraz centralne polecenie to *. Jest to po prostu XOR 1, tzn. Przełącza najmniej znaczący bit górnej części stosu, w tym przypadku zamieniając 0w 1:

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

Teraz spotykamy lustrzane odbicie (...). Tym razem wierzchołek stosu jest dodatnia, a my zrobić wprowadzić kod. Zanim przejdziemy do tego, co dzieje się w nawiasach, pozwól mi wyjaśnić, jak zakończymy na końcu: chcemy upewnić się, że na końcu tego bloku znów będziemy mieć wartość dodatnią na głowie taśmy (tak aby pętla kończy się po pojedynczym iteracji i służy jedynie jako liniowy warunkowy), aby papier w prawo posiada wyjście i prawy stos , który trzyma -1. W takim przypadku opuszczamy pętlę, >przechodzimy do wartości wyjściowej i ]wypychamy ją na -1tak, aby uzyskać czysty stos dla danych wyjściowych.

To tyle. Teraz w nawiasach możemy zrobić wszystko, co chcemy, aby sprawdzić pierwotność, o ile upewnimy się, że wszystko skonfigurowaliśmy zgodnie z opisem w poprzednim akapicie na końcu (co można łatwo zrobić, przesuwając głowę i przesuwając taśmę). Najpierw próbowałem rozwiązać problem z twierdzeniem Wilsona, ale skończyło się to na ponad 100 bajtach, ponieważ kwadratowe obliczenia czynnikowe są w rzeczywistości dość drogie w Stack Cats (przynajmniej nie znalazłem krótkiej drogi). Więc zamiast tego poszedłem z podziałem próbnym i to rzeczywiście okazało się znacznie prostsze. Spójrzmy na pierwszy bit liniowy:

>:^]

Widziałeś już dwa z tych poleceń. Ponadto :zamienia dwie górne wartości bieżącego stosu, a ^XOR drugą wartość na najwyższą. Powoduje :^to wspólny wzorzec do powielania wartości na pustym stosie (ciągniemy zero na górze wartości, a następnie zamieniamy zero na 0 XOR x = x). Po tym sekcja naszej taśmy wygląda następująco:

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

Zaimplementowany przeze mnie algorytm podziału próby nie działa na dane wejściowe 1, dlatego w takim przypadku powinniśmy pominąć kod. Możemy łatwo mapować 1do 0i wszystko co do wartości dodatnie *, więc oto jak to zrobić:

*(*...)

To znaczy zamieniamy się 1w 0, pomijamy dużą część kodu, jeśli rzeczywiście otrzymujemy 0, ale w środku natychmiast cofamy, *aby odzyskać naszą wartość wejściową. Musimy tylko upewnić się, że kończymy na wartości dodatniej na końcu nawiasów, aby nie zaczęły się zapętlać. Wewnątrz trybu warunkowego przesuwamy jeden stos w prawo za pomocą, >a następnie uruchamiamy główną pętlę podziału próby:

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

Nawiasy klamrowe (w przeciwieństwie do nawiasów) definiują inny rodzaj pętli: jest to pętla „do-while”, co oznacza, że ​​zawsze działa przez co najmniej jedną iterację. Inną różnicą jest warunek zakończenia: po wejściu do pętli Stack Cat zapamiętuje najwyższą wartość bieżącego stosu ( 0w naszym przypadku). Pętla będzie następnie działać, dopóki ta sama wartość nie będzie ponownie widoczna na końcu iteracji. Jest to dla nas wygodne: w każdej iteracji po prostu obliczamy resztę następnego potencjalnego dzielnika i przenosimy na ten stos, na którym rozpoczynamy pętlę. Kiedy znajdziemy dzielnik, reszta jest, 0a pętla zatrzymuje się. Spróbujemy podzielić dzielniki, zaczynając od, n-1a następnie zmniejszamy je do 1. Oznacza to, że a) wiemy, że to się skończy, gdy dotrzemy1najpóźniej ib) możemy ustalić, czy liczba jest liczbą pierwszą, czy nie, sprawdzając ostatni dzielnik, którego próbowaliśmy (jeśli jest 1to liczba pierwsza, w przeciwnym razie nie jest).

Weźmy się za to. Na początku jest krótki odcinek liniowy:

<-!<:^>[:

Wiesz, co robi większość z tych rzeczy. Nowe polecenia to -i !. Koty stosu nie mają operatorów zwiększania ani zmniejszania. Jednak ma -(negacja, tj. Pomnożenie przez -1) i !(bitowe NIE, tj. Pomnożenie przez -1i zmniejszenie). Można je połączyć w przyrost !-lub zmniejszenie -!. Więc zmniejszamy kopię nna wierzchu -1, a następnie tworzymy kolejną kopię nna stosie po lewej stronie, a następnie pobieramy nowy dzielnik próbny i umieszczamy go pod spodem n. Tak więc przy pierwszej iteracji otrzymujemy:

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

W kolejnych iteracjach 3zostanie zastąpiony kolejnym dzielnikiem testowym i tak dalej (podczas gdy dwie kopie nzawsze będą miały tę samą wartość w tym momencie).

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

To jest obliczenie modulo. Ponieważ pętle kończą się na wartościach dodatnich, chodzi o to, aby zacząć od -ni wielokrotnie dodawać ddo niego dzielnik próbny , aż do uzyskania wartości dodatniej. Gdy to zrobimy, odejmujemy wynik od, da to daje nam resztę. Problem polega na tym, że nie możemy po prostu umieścić -nna wierzchu stosu i uruchomić pętli, która dodaje d: jeśli górna część stosu jest ujemna, pętla nie zostanie wprowadzona. Takie są ograniczenia odwracalnego języka programowania.

Aby więc obejść ten problem, zaczynamy nod stosu, ale negujemy go tylko przy pierwszej iteracji. Znowu to brzmi prościej, niż się okazuje ...

(-<)

Kiedy górna część stosu jest dodatnia (tj. Tylko przy pierwszej iteracji), negujemy ją -. Jednak nie możemy tego zrobić, (-)ponieważ nie opuścilibyśmy pętli, dopóki nie zostanie -zastosowana dwukrotnie. Więc przesuwamy jedną komórkę w lewo, <ponieważ wiemy, że jest tam dodatnia wartość (the 1). Okej, więc teraz rzetelnie zanegowaliśmy npierwszą iterację. Ale mamy nowy problem: głowica taśmy znajduje się teraz w innej pozycji podczas pierwszej iteracji niż w każdym innym. Musimy to skonsolidować, zanim przejdziemy dalej. Następny <przesuwa głowicę taśmy w lewo. Sytuacja przy pierwszej iteracji:

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

A przy drugiej iteracji (pamiętaj, że dodaliśmy ddo tego raz -n):

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

Następny warunek ponownie łączy te ścieżki:

(<!-)

Podczas pierwszej iteracji głowica taśmy wskazuje zero, więc jest to całkowicie pomijane. Podczas kolejnych iteracji głowa taśmy wskazuje na jedną, więc wykonujemy to, przesuwamy się w lewo i zwiększamy tam komórkę. Ponieważ wiemy, że komórka zaczyna się od zera, teraz będzie zawsze dodatnia, więc możemy opuścić pętlę. To gwarantuje, że zawsze kończymy dwa stosy z głównego stosu i możemy teraz cofnąć się >>. Następnie robimy na końcu pętli modulo -_. Już wiesz -. _jest odejmowanie wartości ^XOR: jeśli górna część stosu znajduje się, aa wartość pod spodem bzastępuje asię b-a. Ponieważ jednak po raz pierwszy zanegowaliśmy a, -_zastępuje asię b+a, dodając w ten sposóbd do naszej bieżącej sumy.

Po zakończeniu pętli (osiągnęliśmy wartość dodatnią) taśma wygląda następująco:

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

Najbardziej lewą wartością może być dowolna liczba dodatnia. W rzeczywistości jest to liczba iteracji minus jedna. Teraz jest jeszcze jeden krótki liniowy bit:

_<<]>:]<]]

Jak powiedziałem wcześniej, musimy odjąć wynik, daby uzyskać rzeczywistą pozostałość ( 3-2 = 1 = 4 % 3), więc po prostu _raz jeszcze. Następnie musimy wyczyścić stos, który zwiększaliśmy po lewej stronie: kiedy próbujemy następnego dzielnika, musi on ponownie wynosić zero, aby pierwsza iteracja zadziałała. Więc przenosimy się tam i przesuwamy tę dodatnią wartość na drugi stos pomocników za pomocą, <<]a następnie wracamy na nasz stos operacyjny za pomocą innego >. Możemy podciągnąć dsię :i wsunąć go z powrotem na -1z ]a potem przenieść pozostałą na nasz stos z warunkowym <]]. To koniec pętli podziału próbnego: trwa to do momentu, aż otrzymamy resztę zera, w którym to przypadku zawiera stos po lewej stroniennajwiększy dzielnik (inny niż n).

Po zakończeniu pętli tuż *<przed ponownym połączeniem ścieżek z danymi wejściowymi 1. Po *prostu zamienia zero na a 1, które za chwilę będziemy potrzebować, a następnie przechodzimy do dzielnika za pomocą <(abyśmy byli na tym samym stosie, co na wejściu 1).

W tym momencie pomaga porównać trzy różne rodzaje danych wejściowych. Po pierwsze, szczególny przypadek, w n = 1którym nie zrobiliśmy żadnych rzeczy z tego działu próbnego:

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

Następnie, nasz poprzedni przykład n = 4, liczba złożona:

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

I wreszcie n = 3liczba pierwsza:

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

Tak więc dla liczb pierwszych mamy 1na tym stosie, a dla liczb zespolonych albo mamy 0liczbę dodatnią, albo większą niż 2. Zamieniamy tę sytuację w 0lub 1potrzebujemy za pomocą następującego końcowego fragmentu kodu:

]*(:)*=<*

]po prostu przesuwa tę wartość w prawo. Następnie *jest wykorzystywana w celu uproszczenia sytuacji warunkowego znacznie: przełączając najmniej znaczącego bitu, zwracamy 1(prime) do 0, 0(kompozytowe) do wartości dodatniej 1, a wszystkie inne wartości dodatnie będą nadal pozytywne. Teraz musimy tylko odróżnić od 0pozytywnego. Tam używamy innego (:). Jeśli górna część stosu to 0(a wejście było liczbą pierwszą), jest to po prostu pomijane. Ale jeśli górna część stosu jest dodatnia (a dane wejściowe były liczbą złożoną), zamienia to na 1, więc teraz mamy 0dla1dla liczb pierwszych - tylko dwie różne wartości. Oczywiście są one przeciwieństwem tego, co chcemy uzyskać, ale łatwo to naprawić za pomocą innego *.

Teraz wszystko, co pozostało jest przywrócenie wzór stosy oczekiwanych przez nas otaczającego ramy: głowy taśmy na wartości dodatniej, wynik na wierzchu stosu po prawej i jeden -1po prawej stronie stosu że . Po to =<*jest. =zamienia szczyty dwóch sąsiednich stosów, przesuwając w ten -1sposób na prawo od wyniku, np. w celu 4ponownego wprowadzenia :

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

Następnie przesuwamy się w lewo za pomocą <i zamieniamy to zero na jedno z *. I to jest to.

Jeśli chcesz głębiej poznać działanie programu, możesz skorzystać z opcji debugowania. Dodaj -dflagę i wstaw "tam, gdzie chcesz zobaczyć bieżący stan pamięci, np. Tak , lub użyj -Dflagi, aby uzyskać pełny ślad całego programu . Alternatywnie możesz użyć EsotericIDE firmy Timwi, która zawiera interpreter Stack Cats z debuggerem krok po kroku.

Haskell, 54 bajty

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

Nic wielkiego do wyjaśnienia.

Rubinowy, 15 + 8 = 23 bajty

p$_.to_i.prime?

Przykładowy przebieg:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false

JavaScript, 39 36 bajtów

Zaoszczędzono 3 bajty dzięki produktom ETH:

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

Wyświetla true dla liczby pierwszej, false w przeciwnym razie.

Do pętli sprawdza każdy numer ı z n-1 aż I jest dzielnik. Jeśli pierwszym znalezionym dzielnikiem jest 1, to jest to liczba pierwsza.

Poprzednie rozwiązanie (39 bajtów):

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

Jak pozostawiono niepotrzebny test:

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

Wysłałem tylko 39 bajtów, ponieważ najlepsza odpowiedź JavaScript miała już 40 bajtów.

Ślimaki, 122

Dane wejściowe należy podawać jednostkowo. Cyfry mogą być dowolną mieszanką znaków oprócz znaków nowej linii.

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

W tym języku dopasowania wzoru 2D stan programu składa się wyłącznie z bieżącej lokalizacji siatki, zestawu dopasowanych komórek i pozycji w kodzie wzoru. Podróżowanie na dopasowany plac jest również nielegalne. Przechowywanie i pobieranie informacji jest trudne, ale możliwe. Ograniczenie podróżowania do dopasowanej komórki można pokonać przez cofnięcie, teleportację ( t) i asercje ( =, !), które pozostawiają siatkę niezmodyfikowaną po zakończeniu.

Rozkład na czynniki nieparzyste liczby zespolonej rozpoczyna się od zaznaczenia pewnego zestawu wzajemnie niesąsiadujących komórek (niebieski na schemacie). Następnie, z każdej żółtej komórki, program sprawdza, czy po obu stronach sąsiedniej niebieskiej jest taka sama liczba nie niebieskich komórek, przemieszczając się w obie strony. Schemat pokazuje ten wzór dla jednej z czterech żółtych komórek, które należy sprawdzić.

Kod z adnotacjami:

^                         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 . !.
    }
  }
}

C, 67 bajtów

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

Drukuje !1(wartość falsey, zgodnie z definicją Petera Taylora ), 0 jeśli (n-1)!^2 == 0 (mod n)i 1inaczej.

EDYCJA : Po puts("!1"+p%n)krótkiej dyskusji na czacie wydaje się być nieco podstępna, więc ją zastąpiłem. Wynik jest o jeden bajt dłuższy.

EDYCJA : Naprawiono dla dużych nakładów.

Krótsze rozwiązania

56 bajtów : Jak zalecono w komentarzach pawel.boczarski, mógłbym wprowadzić dane jednoargumentowe, czytając liczbę argumentów wiersza poleceń:

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

wywoływanie programu jak

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

51 bajtów : Jeśli zezwolisz na „wyjście” za pomocą kodów powrotu:

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

Python 3, 59 bajtów

Teraz używa input()zamiast argumentów wiersza poleceń. Dzięki @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])

APL, 40 13 bajtów

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

Podział próbna z tego samego algorytmu, jak mój R odpowiedź . Przypisujemy xdo wejścia STDIN ( ⎕) i otrzymujemy resztę dla xpodzielonej przez każdą liczbę całkowitą od 1 do x. Każda reszta jest porównywana z 0, co daje nam wektor zer i jedynek wskazujących, które liczby całkowite dzielą x. Jest to sumowane za pomocą, +/aby uzyskać liczbę dzielników. Jeśli liczba ta wynosi dokładnie 2, oznacza to, że jedynymi dzielnikami są 1 xi dlatego xjest liczbą pierwszą.

Python 2, 44

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

Podobnie jak odpowiedź Pythona w Sp3000 , ale unika się zapisywania danych wejściowych poprzez zliczanie zmiennej nod 1wartości wejściowej.

Metaprogramowanie szablonów C ++. 166 131 119 bajtów.

Kod kompiluje się, jeśli stała jest liczbą pierwszą, i nie kompiluje się, jeśli jest liczbą złożoną lub 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];

(wszystkie nowe wiersze, z wyjątkiem ostatniego, są eliminowane w „prawdziwej” wersji).

Myślę, że „brak kompilacji” to zwracana wartość falsey dla języka metaprogramowania. Zauważ, że nie łączy się (więc jeśli nakarmisz go liczbą pierwszą, dostaniesz błędy łączenia) jako pełny program w C ++.

Wartością do przetestowania jest liczba całkowita w ostatnim „wierszu”.

przykład na żywo .