Percaya atau tidak, kami belum memiliki kode tantangan golf untuk tes primality sederhana . Meskipun ini mungkin bukan tantangan yang paling menarik, terutama untuk bahasa "biasa", ini bisa menjadi masalah biasa dalam banyak bahasa.

Fitur kode Rosetta berisi daftar berdasarkan pendekatan idiomatik untuk pengujian primality, satu menggunakan uji Miller-Rabin secara khusus dan lainnya menggunakan divisi uji coba . Namun, "paling idiomatik" sering tidak bersamaan dengan "terpendek." Dalam upaya untuk menjadikan Programming Puzzles dan Code Golf sebagai situs utama untuk golf kode, tantangan ini berupaya menyusun katalog pendekatan terpendek dalam setiap bahasa, mirip dengan "Halo, Dunia!" dan Golf Anda quine untuk kebaikan! .

Selain itu, kemampuan menerapkan tes primality adalah bagian dari definisi bahasa pemrograman kami , jadi tantangan ini juga akan berfungsi sebagai direktori bahasa pemrograman yang terbukti.

Tugas

Tulis program lengkap yang, dengan bilangan bulat positif n sebagai input, menentukan apakah n adalah prima dan mencetak nilai yang benar atau salah .

Untuk tujuan tantangan ini, bilangan bulat adalah prima jika memiliki tepat dua pembagi positif. Perhatikan bahwa ini tidak termasuk 1 , yang merupakan satu-satunya pembagi yang benar-benar positif.

Algoritme Anda harus deterministik (yaitu, menghasilkan output yang benar dengan probabilitas 1) dan harus, secara teori, bekerja untuk bilangan bulat besar yang sewenang-wenang. Dalam praktiknya, Anda dapat mengasumsikan bahwa input dapat disimpan dalam tipe data Anda, selama program bekerja untuk bilangan bulat dari 1 hingga 255.

Memasukkan

• Jika bahasa Anda dapat membaca dari STDIN, menerima argumen baris perintah atau bentuk alternatif lain dari input pengguna, Anda dapat membaca integer sebagai representasi desimal, representasi unary (menggunakan karakter pilihan Anda), byte array (besar atau little endian) atau byte tunggal (jika ini adalah tipe data terbesar bahasa Anda).

• Jika (dan hanya jika) bahasa Anda tidak dapat menerima segala jenis input pengguna, Anda dapat mengubah kode input dalam program Anda.

  Dalam hal ini, integer hardcoded harus mudah ditukar. Secara khusus, ini mungkin hanya muncul di satu tempat di seluruh program.

  Untuk tujuan penilaian, kirimkan program yang sesuai dengan input 1 .

Keluaran

Keluaran harus ditulis ke STDOUT atau alternatif terdekat.

Jika memungkinkan, output harus semata-mata terdiri dari nilai truey atau falsy (atau representasi stringnya), secara opsional diikuti oleh satu baris baru.

Satu-satunya pengecualian untuk aturan ini adalah output konstan dari juru bahasa Anda yang tidak dapat ditekan, seperti salam, kode warna ANSI atau lekukan.

Aturan tambahan

• Ini bukan tentang menemukan bahasa dengan pendekatan terpendek untuk pengujian prima, ini tentang menemukan pendekatan terpendek dalam setiap bahasa. Karenanya, tidak ada jawaban yang akan ditandai sebagai diterima.

• Kiriman dalam sebagian besar bahasa akan dinilai dalam byte dalam pengkodean yang sudah ada sebelumnya, biasanya (tetapi tidak harus) UTF-8.

  Bahasa Piet , misalnya, akan diberi skor dalam kode, yang merupakan pilihan alami untuk bahasa ini.

  Beberapa bahasa, seperti Folder , agak sulit untuk dinilai. Jika ragu, silakan tanyakan di Meta .

• Tidak seperti aturan kami yang biasa, jangan ragu untuk menggunakan bahasa (atau versi bahasa) meskipun itu lebih baru daripada tantangan ini. Jika ada yang ingin menyalahgunakan ini dengan membuat bahasa tempat program kosong melakukan tes primality, selamat untuk membuka jalan bagi jawaban yang sangat membosankan.

  Perhatikan bahwa harus ada penerjemah agar pengajuan dapat diuji. Diperbolehkan (dan bahkan dianjurkan) untuk menulis sendiri penerjemah ini untuk bahasa yang sebelumnya tidak diterapkan.

• Jika bahasa pilihan Anda adalah varian sepele dari bahasa lain (yang berpotensi lebih populer) yang sudah memiliki jawaban (pikirkan dialek BASIC atau SQL, cangkang Unix atau turunan Brainfuck sepele seperti Headecks atau Unary), pertimbangkan untuk menambahkan catatan ke jawaban yang ada bahwa solusi yang sama atau sangat mirip juga merupakan yang terpendek dalam bahasa lain.

• Built-in fungsi untuk pengujian primality yang diperbolehkan. Tantangan ini dimaksudkan untuk membuat katalog solusi terpendek yang mungkin ada dalam setiap bahasa, jadi jika lebih pendek untuk menggunakan built-in dalam bahasa Anda, lakukanlah.

• Kecuali jika telah ditolak sebelumnya, semua aturan standar kode-golf berlaku, termasuk http://meta.codegolf.stackexchange.com/q/1061 .

Sebagai catatan tambahan, tolong jangan turunkan jawaban yang membosankan (tetapi valid) dalam bahasa yang tidak banyak memiliki golf; ini masih berguna untuk pertanyaan ini karena mencoba mengkompilasi katalog selengkap mungkin. Namun, lakukan sebagian besar pilihan jawaban dalam bahasa di mana penulis benar-benar harus berusaha kode golf.

Katalog

Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Misalnya:

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

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

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

Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:

## [><>](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>

Halo Dunia! , 13

hello, world!

Hexagony , 29 byte

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

Versi kode ini yang dapat dibaca adalah:

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

Penjelasan: Ini menguji apakah ada angka dari 2 hingga n-1 yang membagi n.

Inisialisasi:

Tulis n di satu sel memori dan n-1 di yang lain:

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

Kasus Khusus n = 1:

Cetak 0 dan akhiri

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

Putaran

Hitung n% a dan kurangi a. Hentikan jika a = 1 atau n% a = 0.

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

Kasus a = 1:

Tambah 0 ke 1, cetak dan hentikan. (Penunjuk instruksi berjalan ke arah NE dan loop dari sudut timur ke sudut barat daya. Dan $ memastikan itu mengabaikan perintah berikutnya)

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

Huruf a% n = 0:

Cetak 0 dan akhiri (Petunjuk penunjuk sedang menjalankan SW dan loop ke atas ke @

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

Hexagony , 218 92 58 58 55 byte

Perhatikan: Jawaban ini telah dipukuli dengan kuat dengan solusi sisi-panjang 4 oleh Etoplay.

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

Program Hexagony yang non-sepele (non-linear) yang pertama! Ini didasarkan pada pendekatan kuadrat-faktorial yang sama dengan jawaban Labyrinth Sp3000 . Setelah memulai dengan segi enam ukuran 10, saya berhasil memampatkannya ke ukuran 5. Namun, saya dapat menggunakan kembali beberapa kode duplikat dan masih ada banyak no-ops dalam kode, jadi ukuran 4 mungkin saja menjadi mungkin.

Penjelasan

Untuk memahami kode, pertama-tama kita harus membuka lipatannya. Hexagony menempatkan kode sumber apa pun ke angka heksagonal terpusat berikutnya dengan no-ops ( .), yang mana 61. Kemudian mengatur ulang kode menjadi segi enam reguler dengan ukuran yang sesuai:

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

Ini cukup banyak golf dengan persimpangan dan tumpang tindih jalur eksekusi dan beberapa instruksi petunjuk (IP). Untuk menjelaskan cara kerjanya, pertama-tama mari kita lihat versi yang tidak dikenali di mana aliran kontrol tidak melewati batas, hanya satu IP yang digunakan dan jalur eksekusi sesederhana mungkin:

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

^{Catatan sisi: kode di atas dimulai dengan mengeksekusi baris pertama, yang penuh dengan no-ops. Kemudian, ketika IP menyentuh tepi timur laut, ia membungkus ke sudut paling kiri ( )), di mana kode aktual dimulai.}

Sebelum kita mulai, sepatah kata tentang tata letak memori Hexagony. Ini agak seperti rekaman Brainfuck tentang steroid. Sebenarnya, ini bukan pita, tapi itu adalah grid heksagonal itu sendiri (yang tak terbatas), di mana setiap sisi memiliki nilai integer, yang awalnya 0 (dan sebagai lawan dari Brainfuck standar, nilai-nilai tersebut bertanda bilangan bulat presisi presisi). Untuk program ini, kami akan menggunakan empat sisi:

Kami akan menghitung faktorial di tepi A , menghitung mundur masukan kami di tepi C dan menyimpan salinan lain dari input (untuk Modulo) di tepi D . B digunakan sebagai tepi sementara untuk perhitungan.

Memory pointer (MP) dimulai pada tepi A dan menunjuk ke utara (ini penting untuk menggerakkan MP sekitar). Sekarang di sini adalah bit pertama dari kode:

)}?}=&{

)menambah tepi A menjadi 1dasar faktorial. }membuat MP berbelok ke kanan, yaitu pindah ke tepi C (menunjuk utara-timur). Di sini kita membaca input sebagai integer ?. Kemudian kita belok kanan lagi ke ujung D dengan }. =membalikkan MP, seperti yang menunjuk pada simpul bersama dengan C . &menyalin nilai dari C (input) ke D - nilai tersebut disalin dari kiri karena nilai saat ini adalah non-positif (nol). Akhirnya, kami membuat MP berbelok ke kiri ke C dengan {.

Berikutnya, <secara teknis adalah cabang, tetapi kita tahu bahwa nilai saat ini adalah positif, sehingga IP akan selalu berbelok ke kanan menuju >. Sebuah cabang memukul dari tindakan sisi sebagai cermin, sehingga IP bergerak horizontal lagi, menuju (, yang decrements nilai dalam C .

Cabang berikutnya, <adalah benar-benar cabang sekarang. Ini adalah cara kami beralih dari n-1bawah ke 1. Sementara nilai saat ini dalam C positif, IP mengambil belokan kanan (untuk menjalankan loop). Setelah kami mencapai nol, itu akan berbelok ke kiri.

Mari kita lihat loop "tubuh". The |adalah cermin sederhana, >dan <juga digunakan sebagai cermin lagi. Itu berarti tubuh loop yang sebenarnya bermuara ke

}=)&}=*}=

}memindahkan MP ke tepi B , =membalikkan arahnya untuk menghadapi titik puncak ABC . )menambah nilai: ini hanya relevan untuk iterasi pertama, di mana nilai B masih nol: kami ingin memastikan bahwa itu positif, sehingga instruksi berikutnya &menyalin tetangga yang tepat , yaitu A , yaitu nilai saat ini dari faktorial perhitungan, menjadi B .

}kemudian memindahkan MP ke A , =membalikkannya lagi untuk menghadapi titik umum. *mengalikan kedua tetangga, yaitu tepi B dan C dan menyimpan hasilnya di A . Akhirnya, kami memiliki yang lain }=untuk kembali ke C , masih menghadap ABC titik .

Saya harap Anda dapat melihat bagaimana ini menghitung faktorial dari n-1dalam A .

Jadi sekarang kita telah melakukan itu, penghitung lingkaran dalam C adalah nol. Kami ingin kuadrat faktorial dan kemudian mengambil modulo dengan input. Itulah yang dilakukan kode ini:

&}=*{&'%!@

Sejak C adalah nol, &salinan tetangga kiri, yaitu faktorial di A . }=*bergerak ke B dan menyimpan produk dari dua salinan dari faktorial (yaitu alun-alun) di B . {kembali ke C , tetapi tidak membalikkan MP. Kita tahu bahwa nilai saat sekarang positif, sehingga &salinan masukan dari D ke C . 'MP mundur ke kanan, yaitu ke A . Ingat, alun-alun dari faktorial adalah di B dan input di C . Jadi %hitung (n-1)!^2 % n, persis apa yang kita cari.!mencetak hasilnya sebagai integer (0 atau 1) dan @mengakhiri program.

Oke, tapi itu versi yang tidak disunat. Bagaimana dengan versi golf? Anda perlu tahu dua hal lagi tentang Hexagony:

1. Tepi membungkus. Jika IP menyentuh tepi segi enam, ia melompat ke tepi yang berlawanan. Ini ambigu ketika IP menyentuh sudut lurus, jadi memukul sudut juga bertindak sebagai cabang: jika nilai saat ini positif, IP melompat ke tepi kisi ke kanan, sebaliknya ke yang di kiri.
2. Sebenarnya ada 6 IP. Masing-masing dimulai di sudut yang berbeda, bergerak di sepanjang tepi searah jarum jam. Hanya satu dari mereka yang aktif pada satu waktu, yang berarti Anda bisa mengabaikan 5 IP lainnya jika Anda tidak menginginkannya. Anda dapat beralih ke IP berikutnya (dalam urutan searah jarum jam) dengan ]dan ke yang sebelumnya dengan [. (Anda juga dapat memilih yang spesifik dengan #, tetapi itu untuk waktu lain.)

Ada juga beberapa perintah baru di dalamnya: \dan /seperti mirror |, dan ~mengalikan nilai saat ini dengan -1.

Jadi, bagaimana versi yang tidak disunting diterjemahkan menjadi versi golf? Kode pengaturan linier )}?}=&{dan struktur loop dasar dapat ditemukan di sini:

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

Sekarang badan loop melintasi tepi beberapa kali, tetapi yang paling penting, perhitungan aktual diserahkan ke IP sebelumnya (yang dimulai di sudut kiri, bergerak ke timur laut):

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

Setelah memantul cabang ke arah tenggara, IP membungkus tepi ke dua =di sudut kiri atas (yang, bersama-sama, adalah no-op), kemudian memantul dari /. The ~membalikkan tanda dari nilai saat ini, yang penting untuk iterasi berikutnya. IP membungkus tepi yang sama lagi dan akhirnya menyentuh di [mana kontrol diserahkan ke IP lainnya.

Yang ini sekarang dijalankan ~}=)&}=*}yang menghilangkan negasi dan kemudian hanya menjalankan tubuh loop tanpa tanda (minus the =). Akhirnya menyentuh ]tangan mana yang mengontrol kembali ke IP asli. (Perhatikan bahwa lain kali, kami mengeksekusi IP ini, ia akan mulai dari tempat IP itu ditinggalkan, jadi itu akan lebih dulu menyentuh sudut. Kami perlu nilai saat ini menjadi negatif agar IP dapat melompat kembali ke tepi barat laut) bukannya yang di tenggara.)

Setelah IP asli melanjutkan kontrol, itu memantul \, mengeksekusi sisanya =dan kemudian hits >untuk dimasukkan ke dalam iterasi loop berikutnya.

Sekarang bagian yang benar-benar gila: apa yang terjadi ketika loop berakhir?

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

IP bergerak timur laut membentuk <dan membungkus diagonal timur laut. Jadi berakhir di jalur eksekusi yang sama dengan loop body ( &}=*}]). Yang sebenarnya cukup keren, karena itulah kode yang ingin kita jalankan pada titik ini, setidaknya jika kita menambahkan yang lain =}(karena }=}setara dengan {). Tetapi bagaimana ini tidak benar-benar masuk ke loop sebelumnya lagi? Karena ]perubahan pada IP berikutnya yang sekarang menjadi (sejauh ini tidak digunakan) IP yang dimulai di sudut kanan atas, bergerak ke barat daya. Dari sana, IP terus sepanjang tepi, membungkus ke sudut kiri atas, bergerak ke bawah diagonal, memantul |dan berakhir pada @saat menjalankan bit terakhir dari kode linier:

=}&)('%!@

(Ini )(adalah no-op tentu saja - saya harus menambahkan (karena )sudah ada di sana.)

Fiuh ... sangat berantakan ...

Pyth, 4 byte

}QPQ

Cetakan Trueatau False.

Retina , 16 byte

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

Cobalah online!

Mari kita mulai dengan klasik: mendeteksi bilangan prima dengan regex . Input harus diberikan secara unary , menggunakan karakter yang dapat dicetak berulang. Test suite mencakup konversi dari desimal ke unary untuk kenyamanan.

Program Retina yang terdiri dari satu baris memperlakukan garis itu sebagai regex dan mencetak jumlah kecocokan yang ditemukan dalam input, yang akan 0untuk bilangan komposit dan 1untuk bilangan prima.

Lookahead memastikan bahwa input tidak komposit: backtracking akan mencoba setiap kemungkinan substring (minimal 2 karakter) untuk (..+), lookahead kemudian mencoba untuk mencocokkan sisa input dengan mengulangi apa yang ditangkap di sini. Jika ini memungkinkan, itu berarti input memiliki pembagi yang lebih besar dari 1, tetapi yang kurang dari itu sendiri. Jika itu masalahnya, lookahead negatif menyebabkan pertandingan gagal. Untuk bilangan prima tidak ada kemungkinan seperti itu, dan pertandingan berlanjut.

Satu-satunya masalah adalah bahwa lookahead ini juga menerima 1, jadi kami mengesampingkannya dengan mencocokkan setidaknya dua karakter dengan ...

CJam, 4 byte

qimp

CJam memiliki operator bawaan untuk pengujian primality.

HTML + CSS, 254 + n _maks * 28 byte

Kita dapat memeriksa primality menggunakan ekspresi reguler. Mozilla memiliki @document, yang didefinisikan sebagai:

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

Untuk memfilter elemen melalui CSS berdasarkan URL saat ini. Ini adalah satu langkah, jadi kita harus melakukan dua langkah:

1. Dapatkan input dari pengguna. Input ini entah bagaimana harus tercermin dalam URL saat ini.
2. Balas ke pengguna dalam kode sesedikit mungkin.

1. Mendapatkan Input

Cara terpendek yang dapat saya pikirkan untuk mendapatkan input dan mentransfernya ke URL adalah GETformulir dengan kotak centang. Untuk regex, kita hanya perlu beberapa string unik untuk menghitung penampilan.

Jadi kita mulai dengan ini (61 byte):

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

Kami mendapat dua <p>s unik untuk menunjukkan apakah angka yang dimasukkan adalah prima (1) atau tidak (0). Kami juga mendefinisikan bentuk dan tindakannya.

Diikuti oleh n _max checkbox dengan nama yang sama (n _max * 28 bytes):

<input type=checkbox name=i>

Diikuti oleh elemen kirim (34 byte):

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

2. Tampilkan Jawaban

Kami membutuhkan CSS (159 byte) untuk memilih <p>tampilan (1 atau 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}}

»Cobalah di codepen.io (hanya firefox)

Tolong, WarDoq! , 1 byte

P

Output 1 jika inputnya prima, 0 sebaliknya.

Hexagony , 28 byte

Karena Etoplay benar-benar mengalahkan saya dalam pertanyaan ini , saya merasa bahwa saya harus mengalahkan satu-satunya jawaban lainnya .

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

Cobalah online!

Saya menggunakan Teorema Wilson, seperti yang Martin lakukan dalam jawabannya : Diberikan n, saya hasilkan(n-1!)² mod n

Ini dia programnya dibuka:

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

Dan ini adalah versi yang dapat dibaca :

Penjelasan:

Program ini memiliki tiga langkah utama: Inisialisasi , Faktorial dan Output .

Model memori Hexagony adalah kisi heksagonal tak terbatas. Saya menggunakan 5 lokasi memori, seperti yang ditunjukkan dalam diagram ini:

Saya akan merujuk ke lokasi-lokasi ini (dan bilangan bulat disimpan di dalamnya) oleh label mereka pada diagram itu.

Inisialisasi:

Pointer instruksi ( IP ) dimulai di sudut kiri atas, menuju ke Timur. Penunjuk memori ( MP ) dimulai pada IN .

Pertama, ?baca nomor dari input dan simpan di IN . The IP tetap pada jalur biru, tercermin \. Urutan "&(menggerakkan MP kembali dan ke kiri (ke A ), menyalin nilai dari IN ke A dan menurunkannya.

The IP kemudian keluar satu sisi segi enam dan re-memasuki sisi lain (ke jalan yang hijau). Dijalankan '+yang bergerak MP untuk B dan salinan apa yang ada di A . <mengalihkan IP ke Barat.

Faktorial:

Saya menghitung faktorial dengan cara tertentu, sehingga mengkuadratkannya mudah. Saya menyimpan n-1!di B dan C sebagai berikut.

Penunjuk instruksi dimulai pada jalur biru, menuju ke Timur.

='membalikkan arah MP dan bergerak ke belakang untuk C . Ini setara dengan {=tetapi memiliki =tempat itu sangat membantu nanti.

&{salinan nilai dari A ke C , kemudian bergerak MP kembali ke A . The IP kemudian mengikuti jalur hijau, melakukan apa-apa, sebelum mencapai jalur merah, memukul \dan pergi ke jalan oranye.

Dengan (>, kami mengurangi A dan mengarahkan IP East. Berikut hits cabang: <. Untuk positif A , kami melanjutkan sepanjang jalur oranye. Kalau tidak, IP akan diarahkan ke Timur Laut.

'*bergerak MP untuk B dan menyimpan A * C di B . Di (n-1)*(n-2)sinilah input awal berada n. The IP kemudian memasuki kembali ke loop awal dan terus decrementing dan mengalikan sampai A mencapai 0. (komputasi n-1!)

NB : Pada loop berikut, &menyimpan nilai dari B dalam C , karena C memiliki nilai positif yang tersimpan di dalamnya sekarang. Ini penting untuk menghitung faktorial.

Keluaran:

Ketika A mencapai 0. Cabang mengarahkan IP di sepanjang jalur biru sebagai gantinya.

=*membalikkan MP dan menyimpan nilai B * C di A . Kemudian IP keluar hexagon dan masuk kembali di jalur hijau; mengeksekusi "%. Ini menggerakkan MP ke OUT dan menghitung A mod IN , atau (n-1!)² mod n.

Berikut ini {"bertindak sebagai no-op, karena mereka membatalkan satu sama lain. !mencetak hasil akhir dan *+'(dieksekusi sebelum penghentian: @.

Setelah eksekusi, (dengan input 5) memori terlihat seperti ini:

_{Gambar-gambar indah dari aliran kontrol dibuat menggunakan Hexagony Coloror Timwi .}

^{Terima kasih kepada Martin Ender karena membuat semua gambar, karena saya tidak bisa melakukannya di PC saya.}

Mornington Crescent , 2448 bytes

Kami kembali di London!

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 sangat baik hati untuk mengimplementasikan stasiun aliran kontrol Templedan Angeldalam IDE Esoterik serta menambahkan input dan pengurai integer ke spesifikasi bahasa.

Yang ini mungkin lebih baik bermain golf daripada "Hello, World!", Karena kali ini saya menulis skrip CJam untuk membantu saya menemukan jalur terpendek antara dua stasiun. Jika Anda ingin menggunakannya (walaupun saya tidak tahu mengapa ada orang yang mau ...), Anda dapat menggunakan juru bahasa online . Tempel kode ini:

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

Di sini dua baris pertama adalah stasiun yang ingin Anda periksa. Juga, rekatkan isi pastebin ini ke jendela input.

Output akan menunjukkan kepada Anda jalur mana yang tersedia di dua stasiun, dan kemudian daftar semua stasiun yang menghubungkan keduanya, diurutkan berdasarkan panjang nama stasiun. Ini menunjukkan semuanya, karena kadang-kadang lebih baik menggunakan nama yang lebih panjang, baik karena memungkinkan garis yang lebih pendek, atau karena stasiun itu istimewa (seperti Bank atau Kuil) sehingga Anda ingin menghindarinya. Ada beberapa kasus tepi di mana dua stasiun tidak terhubung oleh stasiun tunggal lainnya (terutama, garis Metropolitan dan Distrik tidak pernah menyeberang), dalam hal ini Anda harus mencari tahu hal lain. ;)

Sedangkan untuk kode MC yang sebenarnya, ini didasarkan pada pendekatan kuadrat-faktorial karena banyak jawaban lain karena MC memiliki perkalian, pembagian, dan modulo. Juga, saya pikir satu loop akan nyaman.

Satu masalah adalah bahwa loop adalah loop do-while, dan decrementing dan incrementing itu mahal, jadi saya tidak bisa dengan mudah menghitung (n-1)!(untuk n > 0). Sebagai gantinya, saya menghitung n!dan kemudian membagi npada akhirnya. Saya yakin ada solusi yang lebih baik untuk ini.

Ketika saya mulai menulis ini, saya berpikir bahwa menyimpan -1di Hammersmith akan menjadi ide yang baik sehingga saya dapat mengurangi lebih murah, tetapi pada akhirnya ini mungkin lebih mahal daripada menghemat. Jika saya menemukan kesabaran untuk mengulangi hal ini, saya mungkin mencoba menjaga -1di Upminster saja sehingga saya dapat menggunakan Hammersmith untuk sesuatu yang lebih berguna.

Brachylog (V2), 1 byte

ṗ

Cobalah online!

Brachylog (V1), 2 byte

#p

Ini menggunakan predikat bawaan #p - Prime, yang membatasi inputnya menjadi bilangan prima.

Brachylog adalah upaya saya untuk membuat Prolog versi Golf Code, yaitu bahasa golf kode deklaratif yang menggunakan backtracking dan unifikasi.

Solusi alternatif tanpa built-in: 14 byte

ybbrb'(e:?r%0)

Berikut ini adalah rincian kode di atas:

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 byte

Menggunakan xnor's wajar untuk teorema Wilson :

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

Labirin , 29 byte

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

Membaca bilangan bulat dari STDIN dan output ((n-1)!)^2 mod n. Teorema Wilson sangat berguna untuk tantangan ini.

Program dimulai di sudut kiri atas, dimulai dengan 1yang mengalikan bagian atas tumpukan dengan 10 dan menambahkan 1. Ini adalah cara Labyrinth membangun jumlah besar, tetapi karena tumpukan Labyrinth dipenuhi dengan nol, efek akhirnya adalah seolah-olah kita hanya mendorong 1.

?kemudian membaca ndari STDIN dan :menggandakannya. }bergeser nke stack bantu, untuk digunakan di akhir modulo. (kemudian pengurangan n, dan kami siap untuk mulai menghitung faktorial kuadrat.

Kedua :(duplikat) kami berada di persimpangan, dan di sini fitur kontrol aliran Labyrinth ikut berperan. Di persimpangan setelah instruksi dijalankan, jika bagian atas tumpukan positif kita berbelok ke kanan, untuk negatif kita belok kiri dan untuk nol kita lurus ke depan. Jika Anda mencoba untuk berbalik tetapi menabrak dinding, Labyrinth membuat Anda berbelok ke arah sebaliknya.

Karena n = 1, karena bagian atas tumpukan ndikurangi, atau 0, kita langsung saja. Kami kemudian mencapai no-op 'diikuti oleh penurunan lain (yang menempatkan kami di -1. Ini negatif, jadi kami belok kiri, mengeksekusi +plus ( -1 + 0 = -1), {untuk beralih nkembali dari stack bantu ke main dan %modulo ( -1 % 1 = 0). Lalu kami output dengan !dan berakhir dengan @.

Sebab n > 1, pada detik :kita belok kanan. Kami kemudian menggeser }penghitung perulangan yang disalin ke tumpukan tambahan, menggandakan :dan mengalikan dua kali **, sebelum menggeser penghitung mundur {dan mengurangi (. Jika kita masih positif kita mencoba untuk berbelok ke kanan tetapi tidak bisa, jadi Labyrinth membuat kita berbelok ke kiri, melanjutkan putaran. Kalau tidak, bagian atas tumpukan adalah penghitung lingkaran kami yang telah dikurangi menjadi 0, yang kami +tambahkan ke perhitungan kami ((n-1)!)^2. Akhirnya, kami beralih nkembali dengan {modulo %, output !dan terminasi @.

Saya mengatakan bahwa itu 'adalah no-op, tetapi juga dapat digunakan untuk debugging. Jalankan dengan -dbendera untuk melihat status tumpukan setiap kali 'dilewati!

Utilitas Bash + GNU, 16

• 4 byte disimpan berkat @Dennis

• 2 byte disimpan berkat @Lekensteyn

factor|awk NF==2

Input adalah satu baris yang diambil dari STDIN. Output adalah string kosong untuk falsey dan string non-kosong untuk truey. Misalnya:

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

Java, 126 121 byte

Saya kira kita membutuhkan jawaban Java untuk papan skor ... jadi inilah loop pembagian percobaan sederhana:

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

Seperti biasa untuk Java, persyaratan "program penuh" membuat ini jauh lebih besar daripada jika itu adalah fungsi, sebagian besar karena maintanda tangan.

Dalam bentuk yang diperluas:

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

Sunting: Diperbaiki dan disatukan kembali oleh Peter dalam komentar. Terima kasih!

Brain-Flak , 112 108 byte

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

Cobalah online!

Bagaimana itu bekerja

Awalnya, tumpukan pertama akan berisi bilangan bulat positif n , tumpukan kedua akan kosong.

Kita mulai dengan mengurangi n sebagai berikut.

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

n = 1

Jika n = 1 adalah nol, loop while

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

dilewati seluruhnya. Akhirnya, kode yang tersisa dieksekusi.

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

Jika n - 1 adalah bukan nol, kita masukkan loop yang n = 1 dilewati. Ini bukan loop "nyata"; kode hanya dieksekusi sekali. Ini mencapai yang berikut.

{                   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 dihitung menggunakan algoritma modulus 42-byte dari jawaban tes keterbagian saya .

Akhirnya, kami menginterpretasikan hasil untuk menentukan keutamaan 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 byte

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

Menggunakan divisi percobaan. scan()membaca bilangan bulat dari STDIN dan cat()menulis ke STDOUT.

Kami menghasilkan vektor panjang yang nterdiri dari bilangan bulat 1 ke nmodulo n. Kami menguji apakah masing-masing adalah 0 dengan meniadakan ( !), yang mengembalikan nilai logis yang benar ketika angka 0 dan salah ketika lebih besar dari 0. Jumlah vektor logis adalah jumlah elemen benar, dan untuk bilangan prima kita harapkan satu-satunya moduli bukan nol menjadi 1 dan n, jadi kami berharap jumlahnya menjadi 2

Disimpan 8 byte berkat flodel!

TI-BASIC, 12 byte

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

Cukup mudah. randIntNoRep(memberikan permutasi acak semua bilangan bulat dari 1 hingga Ans.

Ini sedikit membengkokkan aturan; karena daftar dalam TI-BASIC terbatas pada 999 elemen yang saya tafsirkan

asumsikan bahwa input dapat disimpan dalam tipe data Anda

sebagai makna bahwa semua tipe data dapat diasumsikan untuk mengakomodasi input. OP setuju dengan interpretasi ini.

Solusi 17 byte yang benar-benar berfungsi hingga 10 ^ 12 atau lebih:

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

PARI / GP, 21 byte

print(isprime(input))

Berfungsi untuk input yang sangat besar, karena hal seperti ini dibuat untuk PARI / GP.

TI-BASIC, 24 byte

Perhatikan bahwa program TI-Basic menggunakan sistem token, sehingga penghitungan karakter tidak mengembalikan nilai byte sebenarnya dari program.

Suara positif jawaban Thomas Kwa , itu lebih unggul.

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

Sampel:

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

Sekarang kembali 0jika bukan bilangan prima, atau 1jika bilangan prima .

Stack Cats , 62 + 4 = 66 byte

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

Perlu dijalankan dengan -lnflag-command-line (karenanya +4 bytes). Mencetak 0untuk angka komposit dan 1untuk bilangan prima.

Cobalah online!

Saya pikir ini adalah program Stack Cats non-sepele pertama.

Penjelasan

Pengantar Stack Cats cepat:

• Stack Cats beroperasi pada pita tumpukan yang tak terbatas, dengan kepala pita mengarah ke tumpukan saat ini. Setiap tumpukan awalnya diisi dengan jumlah nol yang tak terbatas. Saya biasanya akan mengabaikan nol ini dalam kata-kata saya, jadi ketika saya mengatakan "bagian bawah tumpukan" yang saya maksud adalah nilai non-nol terendah dan jika saya mengatakan "tumpukan kosong" Maksud saya hanya ada nol di atasnya.
• Sebelum program dimulai, a -1didorong ke tumpukan awal, dan kemudian seluruh input didorong di atas itu. Dalam hal ini, karena -nflag, input dibaca sebagai integer desimal.
• Di akhir program, tumpukan saat ini digunakan untuk output. Jika ada -1di bagian bawah, itu akan diabaikan. Sekali lagi, karena adanya -nflag, nilai-nilai dari stack hanya dicetak sebagai bilangan bulat desimal yang dipisahkan oleh linefeed.
• Stack Cats adalah bahasa program yang dapat dibalik: setiap bagian dari kode dapat dibatalkan (tanpa Stack Cats mencatat riwayat yang eksplisit). Lebih khusus lagi, untuk membalikkan setiap kode, Anda cukup mem-mirror-nya, misalnya <<(\-_)menjadi (_-/)>>. Tujuan desain ini menempatkan pembatasan yang cukup parah pada operator dan konstruksi aliran seperti apa yang ada dalam bahasa tersebut, dan fungsi apa yang dapat Anda hitung pada status memori global.

• Untuk melengkapi semua ini, setiap program Stack Cats harus simetris sendiri. Anda mungkin memperhatikan bahwa ini bukan kasus untuk kode sumber di atas. Inilah -lgunanya flag: itu secara implisit mencerminkan kode ke kiri, menggunakan karakter pertama untuk pusat. Maka program yang sebenarnya adalah:

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

Pemrograman secara efektif dengan seluruh kode sangat non-sepele dan tidak intuitif dan belum benar-benar mengetahui bagaimana manusia dapat melakukannya. Kami telah dengan kasar memaksa program semacam itu untuk tugas-tugas yang lebih sederhana, tetapi tidak akan bisa mendekati itu dengan tangan. Untungnya, kami telah menemukan pola dasar yang memungkinkan Anda mengabaikan setengah dari program. Meskipun ini pasti suboptimal, saat ini satu-satunya cara yang dikenal untuk memprogram secara efektif di Stack Cats.

Jadi dalam jawaban ini, templat pola kata adalah ini (ada beberapa variabilitas dalam cara dijalankannya):

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

Ketika program dimulai, stack tape terlihat seperti ini (untuk input 4, katakanlah):

     4    
... -1 ...
     0
     ^

The [bergerak atas tumpukan ke kiri (dan kepala rekaman bersama) - kita sebut ini "mendorong". Dan <memindahkan kepala kaset itu sendiri. Jadi setelah dua perintah pertama, kita punya situasi ini:

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

Sekarang (...)adalah loop yang dapat digunakan dengan mudah sebagai kondisional: loop dimasukkan dan dibiarkan hanya ketika bagian atas tumpukan saat ini positif. Karena saat ini nol, kami melewatkan seluruh paruh pertama program. Sekarang perintah pusat adalah *. Ini sederhana XOR 1, yaitu mengubah sedikit paling tidak signifikan dari bagian atas tumpukan, dan dalam hal ini mengubah 0menjadi 1:

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

Sekarang kita menemukan gambar cermin dari (...). Kali ini atas tumpukan positif dan kami melakukan memasukkan kode. Sebelum kita melihat apa yang terjadi di dalam tanda kurung, izinkan saya menjelaskan bagaimana kita akan menyelesaikannya di akhir: kita ingin memastikan bahwa pada akhir blok ini, kita memiliki tape head pada nilai positif lagi (sehingga lingkaran berakhir setelah iterasi tunggal dan digunakan hanya sebagai bersyarat linear), bahwa tumpukan ke kanan memegang output dan tumpukan kanan yang memegang -1. Jika itu masalahnya, kita biarkan loop, >bergerak ke nilai output dan ]mendorongnya ke -1sehingga kita memiliki tumpukan bersih untuk output.

Itu itu. Sekarang di dalam tanda kurung kita dapat melakukan apa pun yang kita inginkan untuk memeriksa keaslian selama kita memastikan bahwa kita mengatur hal-hal seperti yang dijelaskan dalam paragraf sebelumnya di akhir (yang dapat dengan mudah dilakukan dengan beberapa mendorong dan kepala pita bergerak). Saya pertama kali mencoba menyelesaikan masalah dengan teorema Wilson tetapi berakhir lebih dari 100 byte, karena perhitungan faktorial kuadrat sebenarnya cukup mahal di Stack Cats (setidaknya saya belum menemukan jalan pintas). Jadi saya pergi dengan pembagian percobaan dan ternyata memang lebih sederhana. Mari kita lihat bit linear pertama:

>:^]

Anda sudah melihat dua perintah itu. Selain itu, :menukar dua nilai teratas dari tumpukan saat ini dan ^XORs nilai kedua menjadi nilai teratas. Ini membuat :^pola umum untuk menduplikasi nilai pada tumpukan kosong (kami menarik nol di atas nilai dan kemudian mengubah nol menjadi 0 XOR x = x). Jadi setelah ini, bagian rekaman kami terlihat seperti ini:

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

Algoritma pembagian percobaan yang saya terapkan tidak berfungsi untuk input 1, jadi kita harus melewatkan kode dalam kasus itu. Kita dapat dengan mudah memetakan 1ke 0dan segala sesuatu yang lain untuk nilai-nilai positif dengan *, jadi di sini adalah bagaimana kita melakukannya:

*(*...)

Itulah kita berubah 1menjadi 0, lewati sebagian besar kode jika kita memang benar 0, tetapi di dalam kita segera membatalkan *sehingga kita mendapatkan kembali nilai input kita. Kita hanya perlu memastikan lagi bahwa kita mengakhiri nilai positif pada akhir tanda kurung agar tidak mulai berulang. Di dalam bersyarat, kita bergerak satu tumpukan yang tepat dengan >dan kemudian mulai loop divisi sidang utama:

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

Kawat gigi (sebagai lawan dari tanda kurung) mendefinisikan jenis loop yang berbeda: itu adalah loop do-while, yang berarti selalu dijalankan untuk setidaknya satu iterasi. Perbedaan lainnya adalah kondisi terminasi: ketika memasuki loop Stack Cat mengingat nilai teratas dari stack saat ini ( 0dalam kasus kami). Pengulangan akan berjalan hingga nilai yang sama ini terlihat lagi di akhir iterasi. Ini nyaman bagi kami: dalam setiap iterasi kami cukup menghitung sisa pembagi potensial berikutnya dan memindahkannya ke tumpukan ini kita mulai loop pada. Ketika kami menemukan pembagi, sisanya adalah 0dan loop berhenti. Kami akan mencoba pembagi mulai dari n-1dan kemudian turunkan ke 1. Itu berarti a) kita tahu ini akan berakhir ketika kita mencapai1paling lambat dan b) kita kemudian dapat menentukan apakah angka itu prima atau tidak dengan memeriksa pembagi terakhir yang kita coba (jika itu 1, itu prima, kalau tidak, itu bukan).

Mari kita mulai. Ada bagian linear pendek di awal:

<-!<:^>[:

Anda tahu apa yang sebagian besar hal itu lakukan sekarang. Perintah baru adalah -dan !. Stack Cats tidak memiliki operator increment atau decrement. Namun ia memiliki -(negasi, yaitu kalikan dengan -1) dan !(bitwise BUKAN, yaitu kalikan dengan -1dan penurunan). Ini dapat digabungkan menjadi kenaikan !-, atau penurunan -!. Jadi kami mengurangi salinan ndi atas -1, lalu membuat salinan lain ndi tumpukan ke kiri, lalu mengambil pembagi uji coba baru dan meletakkannya di bawah n. Jadi pada iterasi pertama, kita mendapatkan ini:

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

Pada iterasi lebih lanjut, 3akan diganti dengan pembagi tes berikutnya dan seterusnya (sedangkan dua salinan nakan selalu bernilai sama pada saat ini).

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

Ini adalah perhitungan modulo. Karena loop berakhir pada nilai-nilai positif, idenya adalah mulai dari -ndan berulang kali menambahkan pembagi uji coba dhingga kami mendapatkan nilai positif. Setelah kami melakukannya, kami kurangi hasilnya ddan ini memberi kita sisanya. Agak rumit di sini adalah bahwa kita tidak bisa hanya meletakkan -ndi atas tumpukan dan memulai loop yang menambahkan d: jika bagian atas tumpukan negatif, loop tidak akan dimasukkan. Tersebut adalah keterbatasan bahasa pemrograman reversibel.

Jadi untuk menghindari masalah ini, kita mulai dengan ndi atas tumpukan, tetapi meniadakannya hanya pada iterasi pertama. Sekali lagi, itu terdengar lebih sederhana daripada ternyata ...

(-<)

Ketika bagian atas tumpukan positif (yaitu hanya pada iterasi pertama), kami meniadakannya -. Namun, kita tidak bisa hanya melakukannya (-)karena kita tidak akan meninggalkan loop sampai -diterapkan dua kali. Jadi kami memindahkan satu sel ke kiri <karena kami tahu ada nilai positif di sana 1. Oke, jadi sekarang kita sudah bisa diandalkan meniadakan niterasi pertama. Tetapi kami memiliki masalah baru: kepala kaset sekarang dalam posisi yang berbeda pada iterasi pertama daripada yang lainnya. Kita perlu mengkonsolidasikan ini sebelum kita melanjutkan. Selanjutnya <memindahkan kepala kaset ke kiri. Situasi pada iterasi pertama:

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

Dan pada iterasi kedua (ingat kita telah menambahkan dsekali ke -nsekarang):

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

Persyaratan berikutnya menggabungkan jalur ini lagi:

(<!-)

Pada iterasi pertama head tape menunjuk pada nol, jadi ini dilewati seluruhnya. Pada iterasi lebih lanjut, kepala kaset menunjuk pada satu, jadi kami melakukan ini, pindah ke kiri dan sel meningkat di sana. Karena kita tahu sel dimulai dari nol, sekarang akan selalu positif sehingga kita dapat meninggalkan loop. Ini memastikan kita selalu berakhir dengan dua tumpukan yang tersisa dari tumpukan utama dan sekarang dapat kembali >>. Kemudian pada akhir modulo loop kita lakukan -_. Anda sudah tahu -. _adalah untuk mengurangi apa ^yang harus XOR: jika bagian atas tumpukan adan nilai di bawahnya bdiganti adengan b-a. Sejak kami pertama kali dinegasikan a, -_diganti adengan b+a, dengan demikian menambahkand ke total berjalan kami.

Setelah nilai loop berakhir (kami telah mencapai nilai positif), rekaman itu terlihat seperti ini:

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

Nilai paling kiri bisa berupa angka positif. Bahkan, itu jumlah iterasi minus satu. Ada bit linear pendek lain sekarang:

_<<]>:]<]]

Seperti yang saya katakan sebelumnya, kita perlu mengurangi hasil dari duntuk mendapatkan sisa aktual ( 3-2 = 1 = 4 % 3), jadi kita lakukan _sekali lagi. Selanjutnya, kita perlu membersihkan tumpukan yang telah kita tambahkan di sebelah kiri: ketika kita mencoba pembagi berikutnya, itu harus nol lagi, agar iterasi pertama berfungsi. Jadi kami pindah ke sana dan mendorong nilai positif itu ke tumpukan pembantu lain <<]dan kemudian pindah ke tumpukan operasional kami dengan yang lain >. Kami menarik ddengan :dan mendorongnya kembali ke -1dengan ]dan kemudian kami memindahkan sisanya ke tumpukan bersyarat kami dengan <]]. Itulah akhir dari loop pembagian percobaan: ini berlanjut sampai kita mendapatkan sisa nol, dalam hal ini tumpukan di sebelah kiri berisinPembagi terbesar (selain n).

Setelah loop berakhir, ada beberapa saat *<sebelum kita bergabung dengan input 1lagi. The *hanya mengubah nol menjadi 1, yang kita perlukan sedikit, dan kemudian kami pindah ke pembagi dengan <(sehingga kita berada di tumpukan yang sama seperti untuk input 1).

Pada titik ini membantu untuk membandingkan tiga jenis input yang berbeda. Pertama, kasus khusus di n = 1mana kami belum melakukan hal-hal pembagian sidang itu:

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

Kemudian, contoh kita sebelumnya n = 4, angka gabungan:

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

Dan akhirnya,, n = 3bilangan prima:

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

Jadi untuk bilangan prima, kita memiliki 1pada tumpukan ini, dan untuk bilangan komposit kita memiliki 0bilangan positif atau lebih besar dari 2. Kami mengubah situasi ini menjadi 0atau 1kita perlu dengan potongan kode berikut:

]*(:)*=<*

]hanya mendorong nilai ini ke kanan. Kemudian *digunakan untuk menyederhanakan situasi kondisional: dengan mengubah bit paling tidak signifikan, kita mengubah 1(prime) menjadi 0,0 (komposit) menjadi nilai positif 1, dan semua nilai positif lainnya masih akan tetap positif. Sekarang kita hanya perlu membedakan 0dan positif. Di situlah kita menggunakan yang lain (:). Jika bagian atas tumpukan adalah 0(dan inputnya adalah yang utama), ini hanya dilewati. Tetapi jika bagian atas tumpukan positif (dan inputnya adalah angka komposit) ini menukar dengan 1, sehingga kita sekarang memiliki 0untuk komposit dan1untuk bilangan prima - hanya dua nilai yang berbeda. Tentu saja, itu kebalikan dari apa yang ingin kita hasilkan, tetapi itu mudah diperbaiki dengan yang lain *.

Sekarang yang tersisa adalah mengembalikan pola tumpukan yang diharapkan oleh kerangka kerja kita di sekitarnya: selotip pada nilai positif, hasil di atas tumpukan di sebelah kanan, dan satu -1di tumpukan di sebelah kanan itu . Ini untuk apa =<*. =menukar bagian atas dua tumpukan yang berdekatan, dengan demikian memindahkan-1 ke kanan hasil, misalnya untuk input 4lagi:

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

Kemudian kita hanya bergerak ke kiri < dan mengubah nol itu menjadi satu dengan *. Dan itu saja.

Jika Anda ingin menggali lebih dalam tentang cara kerja program, Anda dapat menggunakan opsi debug. Tambahkan -dbendera dan sisipkan ke "mana pun Anda ingin melihat status memori saat ini, misalnya seperti ini , atau gunakan -Dbendera untuk mendapatkan jejak lengkap dari seluruh program . Atau, Anda dapat menggunakan EsotericIDE Timwi yang mencakup juru bahasa Stack Cats dengan debugger langkah-demi-langkah.

Haskell, 54 byte

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

Tidak banyak yang bisa dijelaskan.

Ruby, 15 + 8 = 23 byte

p$_.to_i.prime?

Contoh dijalankan:

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

JavaScript, 39 36 byte

Disimpan 3 byte berkat produk ETH:

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

Menampilkan true untuk prime, false sebaliknya.

The untuk lingkaran tes setiap nomor i dari n-1 sampai i adalah pembagi. Jika pembagi pertama yang ditemukan adalah 1 maka itu adalah bilangan prima.

Solusi sebelumnya (39 byte):

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

Bagaimana dibiarkan tes yang tidak dibutuhkan:

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

Saya hanya memposting solusi 39 byte karena jawaban JavaScript terbaik sudah 40 byte.

Siput, 122

Masukan harus diberikan secara unary. Digit dapat berupa campuran karakter apa pun kecuali baris baru.

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

Dalam bahasa pencocokan pola 2D ini, status program hanya terdiri dari lokasi kisi saat ini, set sel yang telah dicocokkan, dan posisi dalam kode pola. Juga ilegal bepergian ke alun-alun yang cocok. Ini rumit, tetapi mungkin untuk menyimpan dan mengambil informasi. Pembatasan terhadap perjalanan ke sel yang cocok dapat diatasi dengan mundur, teleportasi ( t) dan pernyataan ( =, !) yang membuat grid tidak dimodifikasi setelah selesai.

Faktorisasi untuk bilangan komposit ganjil dimulai dengan menandai beberapa set sel yang saling tidak bersebelahan (berwarna biru dalam diagram). Kemudian, dari setiap sel kuning, program memverifikasi bahwa ada jumlah yang sama dari sel-sel non-biru di kedua sisi biru yang berdekatan dengan bolak-balik antara dua sisi. Diagram menunjukkan pola ini untuk salah satu dari empat sel kuning yang harus diperiksa.

Kode beranotasi:

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

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

Mencetak !1(nilai falsey, menurut definisi Peter Taylor ) 0 jika (n-1)!^2 == 0 (mod n), dan 1sebaliknya.

EDIT : Setelah beberapa diskusi dalam obrolan, puts("!1"+p%n)tampaknya dianggap sedikit curang, jadi saya menggantinya Hasilnya satu byte lebih panjang.

SUNTING : Tetap untuk input besar.

Solusi yang lebih pendek

56 byte : Seperti yang direkomendasikan dalam komentar oleh pawel.boczarski, saya dapat mengambil input di unary dengan membaca sejumlah argumen baris perintah:

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

memanggil program seperti

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

51 bytes : Jika Anda mengizinkan "output" dengan menggunakan kode pengembalian:

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

Python 3, 59 byte

Sekarang gunakan input()alih-alih argumen baris perintah. Terima kasih kepada @Beta Decay

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

APL, 40 13 byte

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

Divisi percobaan dengan algoritma yang sama seperti jawaban R saya . Kami menetapkan xinput dari STDIN ( ⎕) dan mendapatkan sisanya untuk xdibagi oleh setiap integer dari 1 hingga x. Setiap sisa dibandingkan dengan 0, yang memberi kita vektor satu dan nol yang menunjukkan bilangan bulat mana x. Ini dijumlahkan menggunakan +/untuk mendapatkan jumlah pembagi. Jika angka ini tepat 2, ini berarti satu-satunya pembagi adalah 1 dan x, dan karenanya xprima.

Python 2, 44

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

Seperti jawaban Python Sp3000 , tetapi menghindari menyimpan input dengan menghitung variabel nnaik dari 1ke nilai input.

Metaprogramming template C ++. 166 131 119 byte.

Kode mengkompilasi jika konstanta adalah prima, dan tidak mengkompilasi jika komposit atau 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];

(semua baris baru, kecuali yang terakhir, dihilangkan dalam versi "asli").

Saya pikir "kegagalan untuk mengkompilasi" adalah nilai pengembalian falsey untuk bahasa pemrograman. Perhatikan bahwa itu tidak menautkan (jadi jika Anda memberinya prime, Anda akan mendapatkan kesalahan penautan) sebagai program C ++ lengkap.

Nilai untuk menguji adalah bilangan bulat pada "baris" terakhir.

contoh hidup .