[Question]
  [
Believe it or not, we do not yet have a code golf challenge for a simple [primality test](https://en.wikipedia.org/wiki/Primality_test). While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.
Rosetta code features lists by language of idiomatic approaches to primality testing, one using the [Miller-Rabin test](http://rosettacode.org/wiki/Miller-Rabin_primality_test) specifically and another using [trial division](http://rosettacode.org/wiki/Primality_by_trial_division). However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to ["Hello, World!"](https://codegolf.stackexchange.com/q/55422/20469) and [Golf you a quine for great good!](https://codegolf.stackexchange.com/q/69/20469).
Furthermore, the capability of implementing a primality test is part of [our definition of programming language](http://meta.codegolf.stackexchange.com/a/2073), so this challenge will also serve as a directory of proven programming languages.
### Task
Write a **full program** that, given a strictly positive integer **n** as input, determines whether **n** is prime and prints a [truthy or falsy value](http://meta.codegolf.stackexchange.com/a/2194) accordingly.
For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes **1**, who is its only strictly positive divisor.
Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.
### Input
* If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).
* If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.
In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.
For scoring purposes, submit the program that corresponds to the input **1**.
### Output
Output has to be written to STDOUT or closest alternative.
If possible, output should consist solely of a [truthy or falsy value](http://meta.codegolf.stackexchange.com/a/2194) (or a string representation thereof), optionally followed by a single newline.
The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.
### Additional rules
* This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.
* Submissions in most languages will be scored in *bytes* in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.
The language [Piet](http://www.dangermouse.net/esoteric/piet.html), for example, will be scored in codels, which is the natural choice for this language.
Some languages, like [Folders](http://esolangs.org/wiki/Folders), are a bit tricky to score. If in doubt, please ask on [Meta](http://meta.codegolf.stackexchange.com/).
* Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.
Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.
* If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.
* Built-in functions for testing primality **are** allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.
* Unless they have been overruled earlier, all standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply, including the <http://meta.codegolf.stackexchange.com/q/1061>.
As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.
### Catalog
The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
```
## Language Name, N bytes
```
where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:
```
## Ruby, <s>104</s> <s>101</s> 96 bytes
```
If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:
```
## Perl, 43 + 2 (-p flag) = 45 bytes
```
You can also make the language name a link which will then show up in the snippet:
```
## [><>](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>
```
  
[Answer]
# [hello, world!](https://github.com/histocrat/hello_world), 13
```
hello, world!
```
[Answer]
# [Hexagony](https://github.com/mbuettner/hexagony), 29 bytes
```
.?'.).@@/'/.!.>+=(<.!)}($>(<%
```
The readable version of this code is:
```
   . ? ' .
  ) . @ @ /
 ' / . ! . >
+ = ( < . ! )
 } ( $ > ( <
  % . . . .
   . . . .
```
Explanation: It test if there is a number from 2 to n-1 who divides n.
## Initialization:
Write n in one memory cell and n-1 in an other:
```
   . ? ' .
  . . . . .
 . . . . . .
+ = ( . . . .
 . . . . . .
  . . . . .
   . . . .
```
## Special Case n=1:
Print a 0 and terminate
```
   . . . .
  . . . @ .
 . . . ! . .
. . . < . . .
 . . . . . .
  . . . . .
   . . . .
```
## The loop
Calculate n%a and decrease a. Terminate if a=1 or n%a=0.
```
   . . . .
  ) . . . /
 ' / . . . >
. . . . . . .
 } ( $ > ( <
  % . . . .
   . . . .
```
## Case a=1:
Increase a 0 to an 1, print it and terminate. (The instruction pointer runs in NE direction and loops from the eastern corner to the south western corner. And the $ makes sure it ignores the next command)
```
   . . . .
  . . . @ .
 . . . ! . .
. . . < . . )
 . . $ . . <
  . . . . .
   . . . .
```
## Case a%n=0:
Print the 0 and terminate (The instruction pointer is running SW and loops to the top to the @
```
   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
```
[Answer]
# [Hexagony](https://github.com/mbuettner/hexagony), ~~218~~ ~~92~~ ~~58~~ 55 bytes
**Notice:** This answer has been solidly beaten [with a side-length 4 solution](https://codegolf.stackexchange.com/a/58347/8478) by Etoplay.
```
)}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[
```
The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as [Sp3000's Labyrinth answer](https://codegolf.stackexchange.com/a/57672/8478). After starting out with a hexagon of size 10, I managed to compress it down to size 5. However, I was able to reuse some duplicate code and there are still quite a bunch of no-ops in the code, so size 4 might *just* be possible.
## Explanation
To make sense of the code, we first need to unfold it. Hexagony pads any source code to the next centred hexagonal number with no-ops (`.`), which is `61`. It then rearranges the code into a regular hexagon of the corresponding size:
```
     ) } ? } .
    = ( . . ] =
   } = ' . } . }
  ~ . / % * . . &
 . = & { . < . . .
  . . . = | > ( <
   . . } ! = . .
    . & @ \ [ .
     . . . . .
```
This is quite heavily golfed with crossing and overlapping execution paths and multiple instruction pointers (IPs). To explain how it works, let's first look at an ungolfed version where control flow doesn't go through the edges, only one IP is used and the execution paths are as simple as possible:
```
             . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
          . . . . . . . . . . @ . . . . .
         . . . . . . . . . . ! . . . . . .
        . . . . . . . . . . % . . . . . . .
       . . . . . . . . . . ' . . . . . . . .
      . . . . . . . . . . & . . . . . . . . .
     . . . . . . . . . . { . . . . . . . . . .
    . . . . . . . . . . * . . . . . . . . . . .
   . . . . . . . . . . = . . . . . . . . . . . .
  . . . . . . . . . . } . . . . . . . . . . . . .
 ) } ? } = & { < . . & . . . . . . . . . . . . . .
  . . . . . . . > ( < . . . . . . . . . . . . . .
   . . . . . . = . . } . . . . . . . . . . . . .
    . . . . . } . . . = . . . . . . . . . . . .
     . . . . | . . . . | . . . . . . . . . . .
      . . . . * . . . ) . . . . . . . . . . .
       . . . . = . . & . . . . . . . . . . .
        . . . . > } < . . . . . . . . . . .
         . . . . . . . . . . . . . . . . .
          . . . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
             . . . . . . . . . . . . .
```
Side note: the above code starts with executing the first line, which is full of no-ops. Then, when the IP hits the north east edge, it wraps to the left-most corner (the `)`), where the actual code begins.
Before we start, a word about Hexagony's memory layout. It's a bit like Brainfuck's tape on steroids. In fact, it's not a tape, but it's a hexagonal grid itself (an infinite one), where each *edge* has an integer value, which is initially 0 (and as opposed to standard Brainfuck, the values are signed arbitrary-precision integers). For this program, we'll be using four edges:
[![enter image description here](https://i.stack.imgur.com/bh4T0.png)](https://i.stack.imgur.com/bh4T0.png)
We'll compute the factorial on edge **A**, count down our input on edge **C** and store another copy of the input (for the modulo) on edge **D**. **B** is used as a temporary edge for computations.
The memory pointer (MP) starts out on edge **A** and points north (this is important for moving the MP around). Now here is the first bit of the code:
```
)}?}=&{
```
`)` increments edge **A** to `1` as the basis of the factorial. `}` makes the MP take a right-turn, i.e. move to edge **C** (pointing north-east). Here we read the input as an integer with `?`. Then we take another right-turn to edge **D** with `}`. `=` reverses the MP, such that it points at the vertex shared with **C**. `&` copies the value from **C** (the input) into **D** - the value is copied from the left because the current value is non-positive (zero). Finally, we make the MP take a left-turn back to **C** with `{`.
Next, `<` is technically a branch, but we know that the current value is positive, so the IP will always turn right towards the `>`. A branch hit from the side acts as a mirror, such that the IP moves horizontally again, towards the `(`, which decrements the value in **C**.
The next branch, `<` is *actually* a branch now. This is how we loop from `n-1` down to `1`. While the current value in **C** is positive, the IP takes a right-turn (to execute the loop). Once we hit zero, it will turn left instead.
Let's look at the loop "body". The `|` are simple mirrors, the `>` and `<` are also used as mirrors again. That means the actual loop body boils down to
```
}=)&}=*}=
```
`}` moves the MP to edge **B**, `=` reverses its direction to face the vertex **ABC**. `)` increments the value: this is only relevant for the first iteration, where the value of **B** is still zero: we want to ensure that it's positive, such that the next instruction `&` copies the *right* neighbour, i.e. **A**, i.e. the current value of the factorial computation, into **B**.
`}` then moves the MP to **A**, `=` reverses it again to face the common vertex. `*` multiplies both neighbours, i.e. edges **B** and **C** and stores the result in **A**. Finally, we have another `}=` to return to **C**, still facing the vertex **ABC**.
I hope you can see how this computes the factorial of `n-1` in **A**.
So now we've done that, the loop counter in **C** is zero. We want to square the factorial and then take the modulo with the input. That's what this code does:
```
&}=*{&'%!@
```
Since **C** is zero, `&` copies the left neighbour, i.e. the factorial in **A**. `}=*` moves to **B** and stores the product of the two copies of the factorial (i.e. the square) in **B**. `{` moves back to **C**, but doesn't reverse the MP. We know that the current value is now positive, so `&` copies input from **D** into **C**. `'` the MP *backwards* to the right, i.e. onto **A**. Remember, the square of the factorial is in **B** and the input is in **C**. So `%` computes `(n-1)!^2 % n`, exactly what we're looking for. `!` prints the result as an integer (0 or 1) and `@` terminates the program.
---
Okay, but that was the ungolfed version. What about the golfed version? You need to know two more things about Hexagony:
1. The edges wrap around. If the IP hits an edge of the hexagon, it jumps to the opposite edge. This is ambiguous when the IP hits a corner straight on, so hitting a corner also acts as a branch: if the current value is positive, the IP jumps to the grid edge to its right, otherwise to the one to its left.
2. There are actually *6* IPs. Each of them starts in a different corner, moving along the edge in the clockwise direction. Only one of them is active at a time, which means you can just ignore the other 5 IPs if you don't want them. You can switch to the next IP (in clockwise order) with `]` and to the previous one with `[`. (You can also choose a specific one with `#`, but that's for another time.)
There are also a few new commands in it: `\` and `/` are mirrors like `|`, and `~` multiplies the current value by `-1`.
So how does the ungolfed version translate to the golfed one? The linear set up code `)}?}=&{` and the basic loop structure can be found here:
```
        ) } ? } .  ->
       . . . . . .
      . . . . . . .
     . . . . . . . .
->  . = & { . < . . .
     . . . . . > ( <
      . . . . . . .
       . . . . . .
        . . . . .
```
Now the loop body crosses the edges a few times, but most importantly, the actual computation is handed off to the previous IP (which starts at the left corner, moving north east):
```
        ) . . . .
       = . . . ] .
      } = . . } . .
     ~ . / . * . . .
    . . . . . . . . .
     . . . = . > ( <
      . . } . = . .
       . & . \ [ .
        . . . . .
```
After bouncing off the branch towards south east, the IP wraps around the edge to the two `=` in the top left corner (which, together, are a no-op), then bounces off the `/`. The `~` inverts the sign of the current value, which is important for subsequent iterations. The IP wraps around the same edge again and finally hits `[` where control is handed over to the other IP.
This one now executes `~}=)&}=*}` which undoes the negation and then just runs the ungolfed loop body (minus the `=`). Finally it hits `]` which hands control back to the original IP. (Note that next time, we execute it this IP, it will start from where it left off, so it will first hit the corner. We need the current value to be negative in order for the IP to jump back to the north west edge instead of the south east one.)
Once the original IP resumes control, it bounces off the `\`, executes the remaining `=` and then hits `>` to feed into the next loop iteration.
Now the really crazy part: what happens when the loop terminates?
```
        ) . . . .
       . ( . . ] =
      . . ' . } . }
     . . . % * . . &
    . . . . . . . . .
     . . . = | . . <
      . . } ! . . .
       . & @ . . .
        . . . . .
```
The IP moves north east form the `<` and wraps around to the north east diagonal. So it ends up on the same execution path as the loop body (`&}=*}]`). Which is actually pretty cool, because that is exactly the code we want to execute at this point, at least if we add another `=}` (because `}=}` is equivalent to `{`). But how does this not actually enter the earlier loop again? Because `]` changes to the next IP which is now the (so far unused) IP which starts in the top right corner, moving south west. From there, the IP continues along the edge, wraps to the top left corner, moves down the diagonal, bounces off the `|` and terminates at `@` while executing the final bit of linear code:
```
=}&)('%!@
```
(The `)(` is a no-op of course - I had to add the `(` because the `)` was already there.)
Phew... what a mess...
[Answer]
# Pyth, 4 bytes
```
}QPQ
```
Prints `True` or `False`.
[Answer]
## [Retina](https://github.com/m-ender/retina/wiki/The-Language), 16 bytes
```
^(?!(..+)\1+$)..
```
[Try it online!](https://tio.run/##K0otycxLNPyvqpGgp82l9T9Ow15RQ09PWzPGUFtFU0/v/39DLiMuYy4TLlMuMy5zLgsuSy5DAy5DQwA "Retina – Try It Online")
Let's start with a classic: [detecting primes with a regex](https://stackoverflow.com/q/2795065/1633117). Input should be given in *unary*, using any repeated printable character. The test suite includes a conversion from decimal to unary for convenience.
A Retina program consisting of a single line treats that line as a regex and prints the number of matches found in the input, which will be `0` for composite numbers and `1` for primes.
The lookahead ensures that the input is not composite: backtracking will try every possible substring (of at least 2 characters) for `(..+)`, the lookahead then attempts to match the rest of the input by repeating what was captured here. If this is possible, that means the input has a divisor greater than 1, but which is less than itself. If that is the case the *negative* lookahead causes the match to fail. For primes there is no such possibility, and the match continues.
The only issue is that this lookahead also accepts `1`, so we rule that out by matching at least two characters with `..`.
[Answer]
# HTML+CSS, 254+nmax\*28 bytes
We can check primality using regular expressions. Mozilla has `@document`, which is defined as:
```
@document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# {
  <group-rule-body>
}
```
To filter elements via CSS based on the current URL. This is a single pass, so we have to do two steps:
1. Get input from the user. This input must somehow be reflected in the current URL.
2. Reply to the user in as little code as possible.
**1. Getting Input**
The shortest way I can figure to get input and transfer that to the URL is a `GET` form with checkboxes. For the regex, we just need some unique string to count appearances.
So we start with this (61 bytes):
```
<div id=q><p id=r>1<p id=s>0</div><form method=GET action=#q>
```
We got two unique `<p>`s to indicate whether the entered number is a prime (1) or not (0). We also define the form and it's action.
Followed by nmax checkboxes with the same name (nmax\*28 bytes):
```
<input type=checkbox name=i>
```
Followed by the submit element (34 bytes):
```
<input name=d value=d type=submit>
```
**2. Display Answer**
We need the CSS (159 bytes) to select the `<p>` to display (1 or 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}}
```
---
## [» Try it at codepen.io (firefox only)](https://codepen.io/turbodev/pen/YWJoJr)
![](https://i.stack.imgur.com/pRKzA.png)
[Answer]
# [Hexagony](https://github.com/m-ender/hexagony), 28 bytes
Since [Etoplay](https://codegolf.stackexchange.com/users/45161/etoplay) absolutely trounced me on [this question](https://codegolf.stackexchange.com/a/143928/71256), I felt that I had to outgolf his only other [answer](https://codegolf.stackexchange.com/a/58347/71256).
```
?\.">"!*+{&'=<\%(><.*.'(@>'/
```
[Try it online!](https://tio.run/##y0itSEzPz6v8/98@Rk/JTklRS7taTd3WJkZVw85GT0tPXcPBTl3//39DA0MA "Hexagony – Try It Online")
I use Wilson's Theorem, like Martin did in his [answer](https://codegolf.stackexchange.com/a/57706/71256): Given `n`, I output `(n-1!)² mod n`
Here it the program unfolded:
```
   ? \ . "
  > " ! * +
 { & ' = < \
% ( > < . * .
 ' ( @ > ' /
  . . . . .
   . . . .
```
And here is the *readable* version:
[![Very readable](https://i.stack.imgur.com/atuRJ.png)](https://i.stack.imgur.com/atuRJ.png)
### Explanation:
The program has three main steps: **Initialisation**, **Factorial** and **Output**.
Hexagony's memory model is an infinite hexagonal grid. I am using 5 memory locations, as shown in this diagram:
[![Memory](https://i.stack.imgur.com/sDrUa.png)](https://i.stack.imgur.com/sDrUa.png)
I will be referring to these locations (and the Integers stored in them) by their labels on that diagram.
### Initialisation:
[![Initialisation](https://i.stack.imgur.com/Lm5h7.png)](https://i.stack.imgur.com/Lm5h7.png)
The instruction pointer (**IP**) starts at the top left corner, going East. The memory pointer (**MP**) starts at **IN**.
First, `?` reads the number from input and stores it in **IN**. The **IP** stays on the blue path, reflected by `\`. The sequence `"&(` moves the **MP** back and to the left (to **A**), copies the value from **IN** to **A** and decrements it.
The **IP** then exits one side of the hexagon and re-enters the other side (onto the green path). It executes `'+` which moves the **MP** to **B** and copies what was in **A**. `<` redirects the **IP** to West.
### Factorial:
I compute the factorial in a specific way, so that squaring it is easy. I store `n-1!` in both **B** and **C** as follows.
[![Factorial](https://i.stack.imgur.com/Z6Eun.png)](https://i.stack.imgur.com/Z6Eun.png)
The instruction pointer starts on the blue path, heading East.
`='` reverses the direction of the **MP** and moves it backwards to **C**. This is equivalent to `{=` but having the `=` where it is was helpful later.
`&{` copies the value from **A** to **C**, then moves the **MP** back to **A**. The **IP** then follows the green path, doing nothing, before reaching the red path, hitting `\` and going onto the orange path.
With `(>`, we decrement **A** and redirect the **IP** East. Here it hits a branch: `<`. For positive **A**, we continue along the orange path. Otherwise the **IP** gets directed North-East.
`'*` moves the **MP** to **B** and stores **A** \* **C** in **B**. This is `(n-1)*(n-2)` where the initial input was `n`. The **IP** then enters back into the initial loop and continues decrementing and multiplying until **A** reaches `0`. (computing `n-1!`)
**N.B**: On following loops, `&` stores the value from **B** in **C**, as **C** has a positive value stored in it now. This is crucial to computing factorial.
### Output:
[![Output](https://i.stack.imgur.com/frdsq.png)](https://i.stack.imgur.com/frdsq.png)
When **A** reaches `0`. The branch directs the **IP** along the blue path instead.
`=*` reverses the **MP** and stores the value of **B** \* **C** in **A**. Then the **IP** exits the hexagon and re-enters on the green path; executing `"%`. This moves the **MP** to **OUT** and calculates **A** mod **IN**, or `(n-1!)² mod n`.
The following `{"` acts as a no-op, as they cancel each-other out. `!` prints the final output and `*+'(` are executed before termination: `@`.
After execution, (with an input of `5`) the memory looks like this:
[![Memory2](https://i.stack.imgur.com/VLqWL.png)](https://i.stack.imgur.com/VLqWL.png)
The beautiful images of the control flow were made using [Timwi's](https://codegolf.stackexchange.com/users/668/timwi) [Hexagony Coloror](https://github.com/Timwi/HexagonyColorer).
Thank you to [Martin Ender](https://codegolf.stackexchange.com/users/8478/martin-ender) for generating all of the images, as I couldn't do it on my PC.
[Answer]
## CJam, 4 bytes
```
qimp
```
CJam has a built-in operator for primality testing.
[Answer]
# [Help, WarDoq!](http://esolangs.org/wiki/Help,_WarDoq!), 1 byte
```
P
```
Outputs 1 if the input is prime, 0 otherwise.
[Answer]
# [Mornington Crescent](https://esolangs.org/wiki/Mornington_Crescent), 2448 bytes
[We're back](https://codegolf.stackexchange.com/a/57064/8478) in 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 was so kind to implement the control flow stations `Temple` and `Angel` in [Esoteric IDE](https://github.com/Timwi/EsotericIDE/) as well as add input and integer parsing to the language specification.
This one is probably better golfed than the "Hello, World!", because this time I wrote a CJam script to help me find the shortest path between any two stations. If you want to use it (although I don't know why anyone would want to...), you can use [the online interpreter](http://cjam.aditsu.net/). Paste this code:
```
"Mornington Crescent"
"Cannon Street"
]qN/{'[/0=,}$:Q;{Q{1$#!}=\;_oNo'[/1>{']/0="[]"\*}%}%:R;NoQ{R\f{f{\#)}:+}:*},N*
```
Here the first two lines are the stations you want to check. Also, paste the contents of [this pastebin](http://pastebin.com/raw.php?i=CMbQxrpS) into the input window.
The output will show you which lines are available at the two stations, and then a list of all stations which connect the two, sorted by the length of the station names. It shows all of them, because sometimes it's better to use a longer name, either because it allows a shorter line, or because the station is special (like Bank or Temple) so that you want to avoid it. There are some edge cases where two stations aren't connected by any single other station (notably, the Metropolitan and District lines never cross), in which case you'll have to figure out something else. ;)
As for the actual MC code, it's based on the squared-factorial approach as many other answers because MC has multiplication, division and modulo. Also, I figured that a single loop would be convenient.
One issue is that the loops are do-while loops, and decrementing and incrementing is expensive, so I can't easily compute `(n-1)!` (for `n > 0`). Instead, I'm computing `n!` and then divide by `n` at the end. I'm sure there is a better solution for this.
When I started writing this, I figured that storing `-1` in Hammersmith would be a good idea so I can decrement more cheaply, but in the end this may have cost more than it saved. If I find the patience to redo this, I might try just keeping a `-1` around in Upminster instead so I can use Hammersmith for something more useful.
[Answer]
# Haskell, 49 bytes
Using [*xnor's Corollary to Wilson's Theorem*](https://codegolf.stackexchange.com/a/27022/21487):
```
main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog) (V2), 1 byte
```
ṗ
```
[Try it online!](https://tio.run/nexus/brachylog2#@/9w5/T//w2N/wMA "Brachylog – TIO Nexus")
# [Brachylog](https://github.com/JCumin/Brachylog) (V1), 2 bytes
[```
#p
```](http://brachylog.tryitonline.net/#code=I3A&input=MTAx)
This uses the built-in predicate `#p - Prime`, which constrains its input to be a prime number.
Brachylog is my attempt at making a Code Golf version of Prolog, that is a declarative code golf language that uses backtracking and unification.
### Alternate solution with no built-in: 14 bytes
```
ybbrb'(e:?r%0)
```
Here is a breakdown of the code above:
```
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
)
```
[Answer]
# [Labyrinth](http://esolangs.org/wiki/Labyrinth), 29 bytes
```
1
?
:
}  +{%!@
(:'(
 } {
 :**
```
Reads an integer from STDIN and outputs `((n-1)!)^2 mod n`. [Wilson's theorem](https://en.wikipedia.org/wiki/Wilson%27s_theorem) is pretty useful for this challenge.
The program starts at the top-left corner, beginning with `1` which multiplies the top of the stack by 10 and adds 1. This is Labyrinth's way of building large numbers, but since Labyrinth's stacks are filled with zeroes, the end effect is as though we just pushed a 1.
`?` then reads `n` from STDIN and `:` duplicates it. `}` shifts `n` to the auxiliary stack, to be used at the end for the modulo. `(` then decrements `n`, and we are ready to begin calculating the squared factorial.
Our second `:` (duplicate) is at a junction, and here Labyrinth's control flow features come into play. At a junction after an instruction is executed, if the top of the stack is positive we turn right, for negative we turn left and for zero we go straight ahead. If you try to turn but hit a wall, Labyrinth makes you turn in the other direction instead.
For `n = 1`, since the top of the stack is `n` decremented, or `0`, we go straight ahead. We then hit a no-op `'` followed by another decrement `(` which puts us at `-1`. This is negative, so we turn left, executing `+` plus (`-1 + 0 = -1`), `{` to shift `n` back from the auxiliary stack to the main and `%` modulo (`-1 % 1 = 0`). Then we output with `!` and terminate with `@`.
For `n > 1`, at the second `:` we turn right. We then shift `}` our copied loop counter to the auxiliary stack, duplicate `:` and multiply twice `**`, before shifting the counter back `{` and decrementing `(`. If we're still positive we try to turn right but can't, so Labyrinth makes us turn left instead, continuing the loop. Otherwise, the top of the stack is our loop counter which has been reduced to 0, which we `+` add to our calculated `((n-1)!)^2`. Finally, we shift `n` back with `{` then modulo `%`, output `!` and terminate `@`.
I said that `'` is a no-op, but it can also be used for debugging. Run with the `-d` flag to see the state of the stack every time the `'` is passed over!
[Answer]
# Bash + GNU utilities, 16
* 4 bytes saved thanks to @Dennis
* 2 bytes saved thanks to @Lekensteyn
```
factor|awk NF==2
```
Input is one line taken from STDIN. Output is empty string for falsey and non-empty string for truthy. E.g.:
```
$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
```
[Answer]
# Java, ~~126~~ 121 bytes
I guess we need a Java answer for the scoreboard... so here's a simple trial division loop:
```
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);}}
```
As usual for Java, the "full program" requirement makes this much larger than it would be if it were a function, due mostly to the `main` signature.
In expanded form:
```
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);
    }
}
```
**Edit:** Fixed and regolfed by Peter in comments. Thanks!
[Answer]
## JavaScript, ~~39~~ 36 bytes
Saved 3 bytes thanks to ETHproductions:
```
for(i=n=prompt();n%--i;);alert(1==i)
```
Displays true for a prime, false otherwise.
The *for* loop tests every number *i* from *n-1* until *i* is a divisor.
If the first divisor found is *1* then it's a prime number.
---
**Previous solution (39 bytes):**
```
for(i=n=prompt();n%--i&&i;);alert(1==i)
```
How was left an unneeded 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
```
I only posted the 39 bytes solution because the best JavaScript answer was already 40 bytes.
[Answer]
# R, ~~37~~ 29 bytes
```
n=scan();cat(sum(!n%%1:n)==2)
```
Uses trial division. `scan()` reads an integer from STDIN and `cat()` writes to STDOUT.
We generate a vector of length `n` consisting of the integers 1 to `n` modulo `n`. We test whether each is 0 by negating (`!`), which returns a logical value that's true when the number is 0 and false when it's greater than 0. The sum of a logical vector is the number of true elements, and for prime numbers we expect the only nonzero moduli to be 1 and `n`, thus we expect the sum to be 2.
Saved 8 bytes thanks to flodel!
[Answer]
## [Stack Cats](https://github.com/m-ender/stackcats), 62 + 4 = 66 bytes
```
*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]
```
Needs to be run with the `-ln` command-line flags (hence +4 bytes). Prints `0` for composite numbers and `1` for primes.
[Try it online!](http://stackcats.tryitonline.net/#code=Kig-Ol5dKigqPns8LSE8Ol4-WzooKC08KTwoPCEtKT4-LV8pXzw8XT46XTxdXX0qPCldKig6KSo9PCopPl0&input=MTA3&args=LWxu)
I think this is the first non-trivial Stack Cats program.
### Explanation
A quick Stack Cats introduction:
* Stack Cats operates on an infinite tape of stacks, with a tape head pointing at a current stack. Every stack is initially filled with an infinite amount of zeros. I will generally ignore these zeros in my wording, so when I say "the bottom of stack" I mean the lowest non-zero value and if I say "the stack is empty" I mean there's only zeros on it.
* Before the program starts, a `-1` is pushed onto the initial stack, and then the entire input is pushed on top of that. In this case, due to the `-n` flag, the input is read as a decimal integer.
* At the end of the program, the current stack is used for output. If there's a `-1` at the bottom, it will be ignored. Again, due to the `-n` flag, the values from the stack are simply printed as linefeed-separated decimal integers.
* Stack Cats is a reversible program language: every piece of code can be undone (without Stack Cats keeping track of an explicit history). More specifically, to reverse any piece of code, you simply mirror it, e.g. `<<(\-_)` becomes `(_-/)>>`. This design goal places fairly severe restrictions on what kinds of operators and control flow constructs exist in the language, and what sorts of functions you can compute on the global memory state.
* To top it all off, every Stack Cats program has to be self-symmetric. You might notice that this is not the case for the above source code. This is what the `-l` flag is for: it implicitly mirrors the code to the left, using the first character for the centre. Hence the actual program is:
```
[<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]
```
Programming effectively with the entire code is highly non-trivial and unintuitive and haven't really figured out yet how a human can possibly do it. [We've brute forced such program](https://codegolf.stackexchange.com/a/82985/8478) for simpler tasks, but wouldn't have been able to get anywhere near that by hand. Luckily, we've found a basic pattern which allows you to ignore one half of the program. While this is certainly suboptimal, it's currently the only known way to program effectively in Stack Cats.
So in this answer, the template of said pattern is this (there's some variability in how it's executed):
```
[<(...)*(...)>]
```
When the program starts, the stack tape looks like this (for input `4`, say):
```
     4    
... -1 ...
     0
     ^
```
The `[` moves the top of the stack to the left (and the tape head along) - we call this "pushing". And the `<` moves the tape head alone. So after the first two commands, we've got this situation:
```
...   4 -1 ...
    0 0  0
    ^
```
Now the `(...)` is a loop which can be used quite easily as a conditional: the loop is entered and left only when the top of the current stack is positive. Since, it's currently zero, we skip the entire first half of the program. Now the centre command is `*`. This is simply `XOR 1`, i.e. it toggles the least significant bit of the top of the stack, and in this case turns the `0` into a `1`:
```
... 1 4 -1 ...
    0 0  0
    ^
```
Now we encounter the mirror image of the `(...)`. This time the top of the stack is positive and we *do* enter the code. Before we look into what goes on inside the parentheses, let me explain how we'll wrap up at the end: we want to ensure that at the end of this block, we have the tape head on a positive value again (so that the loop terminates after a single iteration and is used simply as a linear conditional), that the stack to the right holds the output and that the stack right of *that* holds a `-1`. If that's the case, we do leave the loop, `>` moves onto the output value and `]` pushes it onto the `-1` so we have a clean stack for output.
That's that. Now inside the parentheses we can do whatever we want to check the primality as long as we ensure that we set things up as described in the previous paragraph at the end (which can easily done with some pushing and tape head moving). I first tried solving the problem with [Wilson's theorem](https://en.wikipedia.org/wiki/Wilson's_theorem) but ended up well over 100 bytes, because the squared factorial computation is actually quite expensive in Stack Cats (at least I haven't found a short way). So I went with trial division instead and that indeed turned out much simpler. Let's look at the first linear bit:
```
>:^]
```
You've already seen two of those commands. In addition, `:` swaps the top two values of the current stack and `^` XORs the second value into the top value. This makes `:^` a common pattern to duplicate a value on an empty stack (we pull a zero on top of the value and then turn the zero into `0 XOR x = x`). So after this, section our tape looks like this:
```
         4    
... 1 4 -1 ...
    0 0  0
         ^
```
The trial division algorithm I've implemented doesn't work for input `1`, so we should skip the code in that case. We can easily map `1` to `0` and everything else to positive values with `*`, so here's how we do that:
```
*(*...)
```
That is we turn `1` into `0`, skip a big part of the code if we get indeed `0`, but inside we immediately undo the `*` so that we get our input value back. We just need to make sure again that we end on a positive value at the end of the parentheses so that they don't start looping. Inside the conditional, we move one stack right with the `>` and then start the main trial division loop:
```
{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}
```
Braces (as opposed to parentheses) define a different kind of loop: it's a do-while loop, meaning it always runs for at least one iteration. The other difference is the termination condition: when entering the loop Stack Cat remembers the top value of the current stack (`0` in our case). The loop will then run until this same value is seen again at the end of an iteration. This is convenient for us: in each iteration we simply compute the remainder of the next potential divisor and move it onto this stack we're starting the loop on. When we find a divisor, the remainder is `0` and the loop stops. We will try divisors starting at `n-1` and then decrement them down to `1`. That means a) we know this will terminate when we reach `1` at the latest and b) we can then determine whether the number is prime or not by inspecting the last divisor we tried (if it's `1`, it's a prime, otherwise it isn't).
Let's get to it. There's a short linear section at the beginning:
```
<-!<:^>[:
```
You know what most of those things do by now. The new commands are `-` and `!`. Stack Cats does not have increment or decrement operators. However it has `-` (negation, i.e. multiply by `-1`) and `!` (bitwise NOT, i.e. multiply by `-1` and decrement). These can be combined into either an increment, `!-`, or decrement `-!`. So we decrement the copy of `n` on top of the `-1`, then make another copy of `n` on the stack to the left, then fetch the new trial divisor and put it beneath `n`. So on the first iteration, we get this:
```
      4       
      3       
... 1 4 -1 ...
    0 0  0
      ^
```
On further iterations, the `3` will replaced with the next test divisor and so on (whereas the two copies of `n` will always be the same value at this point).
```
((-<)<(<!-)>>-_)
```
This is the modulo computation. Since loops terminate on positive values, the idea is to start from `-n` and repeatedly add the trial divisor `d` to it until we get a positive value. Once we do, we subtract the result from `d` and this gives us the remainder. The tricky bit here is that we can't just have put a `-n` on top of the stack and start a loop that adds `d`: if the top of the stack is negative, the loop won't be entered. Such are the limitations of a reversible programming language.
So to circumvent this issue, we do start with `n` on top of the stack, but negate it only on the first iteration. Again, that sounds simpler than it turns out to be...
```
(-<)
```
When the top of the stack is positive (i.e. only on the first iteration), we negate it with `-`. However, we can't just do `(-)` because then we wouldn't be *leaving* the loop until `-` was applied twice. So we move one cell left with `<` because we know there's a positive value there (the `1`). Okay, so now we've reliably negated `n` on the first iteration. But we have a new problem: the tape head is now in a different position on the first iteration than in every other one. We need to consolidate this before we move on. The next `<` moves the tape head left. The situation on the first iteration:
```
        -4       
         3       
...   1  4 -1 ...
    0 0  0  0
    ^
```
And on the second iteration (remember we've added `d` once into `-n` now):
```
      -1       
       3       
... 1  4 -1 ...
    0  0  0
    ^
```
The next conditional merges these paths again:
```
(<!-)
```
On the first iteration the tape head points at a zero, so this is skipped entirely. On further iterations, the tape head points at a one though, so we do execute this, move to the left and increment the cell there. Since we know the cell starts from zero, it will now always be positive so we can leave the loop. This ensures we always end up two stack left of the main stack and can now move back with `>>`. Then at the end of the modulo loop we do `-_`. You already know `-`. `_` is to subtraction what `^` is to XOR: if the top of the stack is `a` and the value underneath is `b` it replaces `a` with `b-a`. Since we first negated `a` though, `-_` replaces `a` with `b+a`, thereby adding `d` into our running total.
After the loop ends (we've reached a positive) value, the tape looks like this:
```
        2       
        3       
... 1 1 4 -1 ...
    0 0 0  0
        ^
```
The left-most value could be any positive number. In fact, it's the number of iterations minus one. There's another short linear bit now:
```
_<<]>:]<]]
```
Like I said earlier we need to subtract the result from `d` to obtain the actual remainder (`3-2 = 1 = 4 % 3`), so we just do `_` once more. Next, we need to clean up the stack that we've been incrementing on the left: when we try the next divisor, it needs to be zero again, for the first iteration to work. So we move there and push that positive value onto the other helper stack with `<<]` and then move back onto our operational stack with another `>`. We pull up `d` with `:` and push it back onto the `-1` with `]` and then we move the remainder onto our conditional stack with `<]]`. That's the end of the trial division loop: this continues until we get a zero remainder, in which case the stack to the left contains `n`'s greatest divisor (other than `n`).
After the loop ends, there's just `*<` before we join paths with the input `1` again. The `*` simply turns the zero into a `1`, which we'll need in a bit, and then we move to the divisor with `<` (so that we're on the same stack as for input `1`).
At this point it helps to compare three different kinds of inputs. First, the special case `n = 1` where we haven't done any of that trial division stuff:
```
         0    
... 1 1 -1 ...
    0 0  0
         ^
```
Then, our previous example `n = 4`, a composite number:
```
    2           
    1    2 1    
... 1 4 -1 1 ...
    0 0  0 0
         ^
```
And finally, `n = 3`, a prime number:
```
    3           
    1    1 1    
... 1 3 -1 1 ...
    0 0  0 0
         ^
```
So for prime numbers, we have a `1` on this stack, and for composite numbers we either have a `0` or a positive number greater than `2`. We turn this situation into the `0` or `1` we need with the following final piece of code:
```
]*(:)*=<*
```
`]` just pushes this value to the right. Then `*` is used to simplify the conditional situation greatly: by toggling the least significant bit, we turn `1` (prime) into `0`, `0` (composite) into the positive value `1`, and all other positive values will still remain positive. Now we just need to distinguish between `0` and positive. That's where we use another `(:)`. If the top of the stack is `0` (and the input was a prime), this is simply skipped. But if the top of the stack is positive (and the input was a composite number) this swaps it with the `1`, so that we now have `0` for composite and `1` for primes - only two distinct values. Of course, they are the opposite of what we want to output, but that is easily fixed with another `*`.
Now all that's left is to restore the pattern of stacks expected by our surrounding framework: tape head on a positive value, result on top of the stack to the right, and a single `-1` on the stack right of *that*. This is what `=<*` is for. `=` swaps the tops of the two adjacent stacks, thereby moving the `-1` to the right of the result, e.g. for input `4` again:
```
    2     0       
    1     3       
... 1 4   1 -1 ...
    0 0 0 0  0
          ^
```
Then we just move left with `<` and turn that zero into a one with `*`. And that's that.
If you want to dig deeper into how the program works, you can make use of the debug options. Either add the `-d` flag and insert `"` wherever you want to see the current memory state, [e.g. like this](http://stackcats.tryitonline.net/#code=Kig-Ol5dKigqPns8LSE8Ol4-WzooIigtPCk8KDwhLSk-Pi1fKV88PF0-Ol08XV19KjwpXSooOikqPTwqKT5d&input=NA&args=LWxuZA&debug=on), or use the `-D` flag [to get a complete trace of the entire program](http://stackcats.tryitonline.net/#code=Kig-Ol5dKigqPns8LSE8Ol4-WzooKC08KTwoPCEtKT4-LV8pXzw8XT46XTxdXX0qPCldKig6KSo9PCopPl0&input=Mw&args=LWxuRA&debug=on). Alternatively, you can use [Timwi's EsotericIDE](https://github.com/timwi/EsotericIDE) which includes a Stack Cats interpreter with a step-by-step debugger.
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), ~~112~~ 108 bytes
```
({}[()]){((({})())<>){{}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}}}<>{{}}([]{})
```
[Try it online!](http://brain-flak.tryitonline.net/#code=KHt9WygpXSl7KCgoe30pKCkpPD4pe3t9PD4oKHt9PCgoe31bKCldKSgpPD4pPik8Pik8Pnsoe31bKCldPCh7fVsoKV08KHt9KCkpPik-eyg8KCk-KX17fSl9e317fX19PD57e319KFtde30p&input=MjUx)
## How it works
Initially, the first stack will contain a positive integer **n**, the second stack will be empty.
We start by decrementing **n** as follows.
```
(
  {}      Pop n.
  [()]    Yield -1.
)       Push n - 1.
```
### n = 1
If **n = 1** is zero, the while loop
```
{
  ((({})())<>)
  {
    {}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}
  }
}
```
is skipped entirely. Finally, the remaining code is executed.
```
<>    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**
If **n - 1** is non-zero, we enter the loop that **n = 1** skips. It isn't a "real" loop; the code is only executed once. It achieves the following.
```
{                   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** is computed using the 42-byte modulus algorithm from [my divisibility test answer](https://codegolf.stackexchange.com/a/95210/12012).
Finally, we interpret the results to determine **n**'s primality.
```
<>    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.
```
[Answer]
# TI-BASIC, 12 bytes
```
2=sum(not(fPart(Ans/randIntNoRep(1,Ans
```
Pretty straightforward. `randIntNoRep(` gives a random permutation of all integers from 1 to `Ans`.
This bends the rules a little; because lists in TI-BASIC are limited to 999 elements I interpreted
> 
> assume that the input can be stored in your data type
> 
> 
> 
as meaning that all datatypes can be assumed to accommodate the input. OP agrees with this interpretation.
A **17-byte solution** which actually works up to 10^12 or so:
```
2=Σ(not(fPart(Ans/A)),A,1,Ans
```
[Answer]
# TI-BASIC, 24 bytes
Note that TI-Basic programs use a token system, so counting characters does not return the actual byte value of the program.
Upvote [Thomas Kwa's answer](https://codegolf.stackexchange.com/a/57870/38511), it is superior.
```
:Prompt N
:2
:While N≠1 and fPart(N/Ans
:Ans+1
:End
:N=Ans
```
Sample:
```
N=?1009
                         1
N=?17
                         1
N=?1008
                         0
N=?16
                         0
```
Now returns `0` if not a prime, or `1` if it is.
[Answer]
## C++ template metaprogramming. ~~166~~ ~~131~~ 119 bytes.
Code compiles if the constant is a prime, and does not compile if composite or 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];
```
(all newlines, except final one, are eliminated in "real" version).
I figure "failure to compile" is a falsey return value for a metaprogramming language. Note that it does not link (so if you feed it a prime, you'll get linking errors) as a full C++ program.
The value to test is the integer on the last "line".
[live example](http://coliru.stacked-crooked.com/a/d1073b477078ddeb).
[Answer]
# Ruby, 15 + 8 = 23 bytes
```
p$_.to_i.prime?
```
Sample run:
```
bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
```
[Answer]
# PARI/GP, 21 bytes
```
print(isprime(input))
```
Works for ridiculously big inputs, because this kind of thing is what PARI/GP is made for.
[Answer]
# Python 3, 59 bytes
Now uses `input()` instead of command line arguments. Thanks to @Beta Decay
```
n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
```
[Answer]
# C, 67 bytes
```
i,n;main(p){for(scanf("%d",&i),n=i;--i;p=p*i*i%n);putchar(48+p%n);}
```
Prints ~~`!1` (a falsey value, by [Peter Taylor's definition](http://meta.codegolf.stackexchange.com/questions/2190/interpretation-of-truthy-falsey/2194#2194))~~ `0` if `(n-1)!^2 == 0 (mod n)`, and `1` otherwise.
**EDIT**: After some discussion in chat, `puts("!1"+p%n)` seems to be considered a bit cheaty, so I've replaced it. The result is one byte longer.
**EDIT**: Fixed for big inputs.
## Shorter solutions
**56 bytes**: As recommended in the comments by pawel.boczarski, I could take input in unary by reading the number of command line arguments:
```
p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);putchar(48+p%n);}
```
invoking the program like
```
$ ./a.out 1 1 1 1 1
1                        <-- as 5 is prime
```
**51 bytes**: If you allow "output" by means of return codes:
```
p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
```
[Answer]
# Haskell, 54 bytes
```
import Data.Numbers.Primes
main=readLn>>=print.isPrime
```
Nothing much to explain.
[Answer]
## Python 2, 44
```
P=n=1
exec"P*=n*n;n+=1;"*~-input()
print P%n
```
Like [Sp3000's Python answer](https://codegolf.stackexchange.com/a/57681/20260), but avoids storing the input by counting the variable `n` up from `1` to the input value.
[Answer]
# Snails, 122
Input should be given in unary. The digits may be any mix of characters except newlines.
```
^
..~|!(.2+~).!~!{{t.l=.r=.}+!{t.!.!~!{{r!~u~`+(d!~!.r~)+d~,.r.=.(l!~u~)+(d!~l~)+d~,.l.},l=(.!.)(r!~u~)+(d!~!.r~)+d~,.r.!.
```
In this 2D pattern matching language, the program state consists solely of the current grid location, the set of cells which have been matched, and the position in the pattern code. It's also illegal to travel onto a matched square. It's tricky, but possible to store and retrieve information. The restriction against traveling onto a matched cell can be overcome by backtracking, teleporting (`t`) and assertions (`=`, `!`) which leave the grid unmodified after completing.
[![Factorization of 25](https://i.stack.imgur.com/yiSVR.png)](https://i.stack.imgur.com/yiSVR.png)
The factorization for an odd composite number begins by marking out some set of mutually non-adjacent cells (blue in diagram). Then, from each yellow cell, the program verifies that there are an equal number of non-blue cells on either side of the adjacent blue one by shuttling back and forth between the two sides. The diagram shows this pattern for one of the four yellow cells which must be checked.
Annotated code:
```
^                         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 . !.
    }
  }
}
```
[Answer]
# APL, ~~40~~ 13 bytes
```
2=+/0=x|⍨⍳x←⎕
```
Trial division with the same algorithm as [my R answer](https://codegolf.stackexchange.com/a/57675/20469). We assign `x` to the input from STDIN (`⎕`) and get the remainder for `x` divided by each integer from 1 to `x`. Each remainder is compared against 0, which gives us a vector of ones and zeros indicating which integers divide `x`. This is summed using `+/` to get the number of divisors. If this number is exactly 2, this means the only divisors are 1 and `x`, and thus `x` is prime.
]