### Is this number a prime?

• Believe it or not, we do not yet have a code golf challenge for a simple 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 specifically and another using 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!" and Golf you a quine for great good!.

Furthermore, the capability of implementing a primality test is part of our definition of programming language, so this challenge will also serve as a directory of proven programming languages.

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

• 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, for example, will be scored in codels, which is the natural choice for this language.

Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

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

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

Can I take inputs as negative numbers, where abs(input) would be the number I am testing?

No, the input is a strictly positive integer.

Is there a reason for the *full program requirement*, rather than allowing the full range of default input types? E.g. answering with a function that takes its input as an argument, is currently disallowed? https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods

@LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests.

Could a case be made for locking this challenge and posting a new, less restrictive one?

@Shaggy Seems like a question for meta.

Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge.

Is it ok if an answer falsely says `1` is prime, or would this disqualify and answer?

• # hello, world!, 13

``hello, world!``

Did you, like, *just* create this language, *just* for this submission? ;)

@ETHproductions Looks like the latest commit was 10 days ago.

@Geobits Ah, my bad, I saw Sep 11 as the date. Still, that's an interesting language you got there. :)

Methinks the program should be `hello, worl!`, since `0` appears to be the only falsy value in the language. Also, it's shorter. ;)

Also, I don't know if I'm doing something wrong, but my tweaked version on Ideone hangs when given an input of `1`.

It's true, if I'd created this language exactly to the spec in the question I'd've done it slightly differently. :p My version suspends judgment on 1 as well.

I was hoping to have the language in slightly better shape before linking to it anywhere, but this challenge was posted and I couldn't resist.

@histocrat The good news is, due to the rules of this particular question, you can update the language and use the new version.

I would almost say that hanging on an input of 1 is correct functionality.

@histocrat It would be cool if your language would get an entry in the hello world challenge http://codegolf.stackexchange.com/questions/55422/hello-world

The best part about this is that the program isn't just a built-in, each character plays its own part in getting the correct result.

How does this work?

@user67719 I guess you could read how on the GitHub repo readme.

egsykhugtyrfv7y 4r7ot 4fv7dfo 434 3f8f <-- my reaction

• # Hexagony, 29 bytes

``.?'.)[email protected]@/'/.!.>+=(<.!)}(\$>(<%``

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 @

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

Holy crap, that's one impressive first post. :) I'll put up the bounty right now (I'll award it in 7 days, to draw some more attention to your answer). Welcome to PPCG!

Great answer! +1 for "*The readable version of this code is: <...>*" :-)

• # Hexagony, 2189258 55 bytes

Notice: This answer has been solidly beaten with a side-length 4 solution 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. 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:

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:

``&}=*{&'%[email protected]``

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:

``=}&)('%[email protected]``

(The `)(` is a no-op of course - I had to add the `(` because the `)` was already there.)

Phew... what a mess...

Nice! How new is this? Also, you may wish to create an esolangs page whenever you get a stable release

@mbomb007 I implemented the language two days ago (and designed it over two or three days before that). And yes, I'll definitely add an esolangs page, but I think the spec isn't 100% stable yet (there are still 3 unassigned commands for instance). Once I feel that it's more stable, I'll add it to both esolangs and our meta post.

Under the expanded hex is *it wraps to the left-most corner (the `1`)*. What `1` are you talking about there?

@mbomb007 fixed. The `)` used to be a `1`.

+1 just for the level of detail in your explanation of how it works. If more languages came with an example that detailed more people could use them :D

• # Pyth, 4 bytes

``}QPQ``

Prints `True` or `False`.

I know that this is old but now you can also do that like this: P_Q and save 1 byte.

It's now possible with `P_`

@drobilc You can cut the Q, as an EOF when the function is expecting an argument, it uses the input

If we're adding solutions that now work, `/P` is an alternate 2 byte option.

• ## Retina, 16 bytes

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

Try it online!

Let's start with a classic: detecting primes with a regex. 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 `..`.

That's actually an irregular expression, since the primes do not form a regular language.

@PyRulez Most real-world regex flavours are a lot more powerful than the theoretical concept of regular expressions. I improved the wording though.

The most powerful "regex" engines out in the open right now have recognition power equal to that of a linear bounded automata. Standard issue regex, pattern recursion, unlimited lookhead, and unlimited lookbehind are all you need for context-sensitive parsing (though backreferences and such generally help with complicating efficient parsing), and some have them all. Don't even get me started on the engines that let you embed code into the regex.

• ## CJam, 4 bytes

``qimp``

CJam has a built-in operator for primality testing.

Alternatively: `limp`

`pimp` my cjam.

`pimp` is objectively more pimp

You can also do `l~mp`

Wait, if CJam has a built in for primality testing, why is it 4 bytes?

@Cyoce, `q` reads a line of input, `i` parses it as an integer, and `mp` is the built-in. CJam has two groups of two-char built-ins: the "extended" ones begin `e` and the "mathematical"ones begin `m`

@flawr I believe (I forgot the source) the Cjam actually means CherryJam, which participated in Google's CodeJam contest.

• # 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.

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

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)

+1: This is my all time favourite abuse of HTML, and the kind of stuff that makes me love codegolf.

This is certainly interesting, but I'm not sure if it satisfies the rules of this challenge. In particular, I don't think it complies with *Your algorithm [...] should, in theory, work for arbitrarily large integers.* Couldn't you use a regex on the value of an input field as well?

@Dennis Maybe. Probably even. But that wouldn't solve the problem you mentioned. I leave it here as a non-competing entry, because this is the most on-topic challenge for that.

Why not? If you have a number in unary in an input field, your code would no longer depend on the maximum number.

Hm, I thought about this a bit more, and there's really no difference between having only x checkboxes and an interpreter that has only y-bit numbers. Disregard my previous comment.

A text input taking a string in unary would solve the nmax issue and allow you to count the number of bytes. It would also allow for theoretically arbitrarily high values (based on maximum URL length, which is a browser implementation detail).

• # Help, WarDoq!, 1 byte

``P``

Outputs 1 if the input is prime, 0 otherwise.

• # Hexagony, 28 bytes

Since Etoplay absolutely trounced me on this question, I felt that I had to outgolf his only other answer.

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

Try it online!

I use Wilson's Theorem, like Martin did in his answer: Given `n`, I output `(n-1!)² mod n`

Here it the program unfolded:

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

And here is the readable version:

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

I will be referring to these locations (and the Integers stored in them) by their labels on that diagram.

### Initialisation:

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.

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:

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:

The beautiful images of the control flow were made using Timwi's Hexagony Coloror.

Thank you to Martin Ender for generating all of the images, as I couldn't do it on my PC.

What are you using for these memory diagrams? I've seen Esoteric IDE but I couldn't get it to run...

@NieDzejkob you're better off asking Martin in chat , since he made them for me anyway.

@NieDzejkob Yeah, the memory diagram can be exported from the EsoIDE. https://chat.stackexchange.com/rooms/27364/esoteric-programming-languages if you want to chat about this some more.

• # Mornington Crescent, 2448 bytes

We're back in London!

``Take Northern Line to BankTake Circle Line to BankTake District Line to Parsons GreenTake District Line to BankTake Circle Line to HammersmithTake District Line to UpneyTake District Line to HammersmithTake Circle Line to VictoriaTake Victoria Line to Seven SistersTake Victoria Line to VictoriaTake Circle Line to VictoriaTake Circle Line to BankTake Circle Line to HammersmithTake Circle Line to Cannon StreetTake Circle Line to HammersmithTake Circle Line to Cannon StreetTake Circle Line to BankTake Circle Line to HammersmithTake Circle Line to AldgateTake Circle Line to AldgateTake Metropolitan Line to Chalfont & LatimerTake Metropolitan Line to AldgateTake Circle Line to HammersmithTake District Line to UpminsterTake District Line to HammersmithTake Circle Line to Notting Hill GateTake Circle Line to HammersmithTake Circle Line to Notting Hill GateTake District Line to UpminsterTake District Line to BankTake Circle Line to VictoriaTake Circle Line to TempleTake Circle Line to AldgateTake Circle Line to AldgateTake Metropolitan Line to Chalfont & LatimerTake Metropolitan Line to PinnerTake Metropolitan Line to Chalfont & LatimerTake Metropolitan Line to PinnerTake Metropolitan Line to Chalfont & LatimerTake Metropolitan Line to PinnerTake Metropolitan Line to AldgateTake Circle Line to HammersmithTake District Line to UpminsterTake District Line to VictoriaTake Circle Line to AldgateTake Circle Line to VictoriaTake Circle Line to VictoriaTake District Line to UpminsterTake District Line to EmbankmentTake Circle Line to EmbankmentTake Northern Line to AngelTake Northern Line to MoorgateTake Metropolitan Line to Chalfont & LatimerTake Metropolitan Line to AldgateTake Circle Line to AldgateTake Circle Line to Cannon StreetTake District Line to UpneyTake District Line to Cannon StreetTake District Line to Acton TownTake District Line to Acton TownTake Piccadilly Line to Russell SquareTake Piccadilly Line to HammersmithTake Piccadilly Line to Russell SquareTake Piccadilly Line to RuislipTake Piccadilly Line to RuislipTake Metropolitan Line to Preston RoadTake Metropolitan Line to AldgateTake Circle Line to AldgateTake Circle Line to Cannon StreetTake Circle Line to AldgateTake Circle Line to AldgateTake Metropolitan Line to Preston RoadTake Metropolitan Line to MoorgateTake Circle Line to MoorgateTake Northern Line to Mornington Crescent``

Timwi was so kind to implement the control flow stations `Temple` and `Angel` in Esoteric IDE 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. 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 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.

Is London turing complete?

@RohanJhunjhunwala probably

Wow! I love seeing well thought out questions. I especially love seeing questions where you have to write a program to write a program.

Minor question - how _did_ you store `-1` in Hammersmith? I'm thinking of doing the same for a program I'm writing. I'm guessing it was by Notting Hill Gate, but I could be wrong.

@Cloudy7 Yeah something like that. I just stepped through the program in the Esoteric IDE, and apparently I picked up the 7 from Seven Sisters, divided by itself in Chalfont & Latimer to get a 1, negated in Notting Hill Gate to get a -2 and added those together in Upminster for a -1. In hindsight, this seems a little unnecessarily complicated. I think I could've just done the last two steps to the input (without picking up the 7, or dividing by itself).

@MartinEnder Wow, that's still better than what I dreamed up, which was getting the name of the station "Bromley-by-Bow", getting the last seven characters at Mile End, using Charing Cross twice to get the hyphen out, then concatenating with a string containing a number at Paddington. (Interestingly, Notting Hill Gate seems to add 1 to any positive integer and then negate it. Weird.)

@Cloudy7 Yeah, you're right, I meant Cannon Street.

@MartinEnder I just realized, looking at this a year later, that a significant number of bytes could be shaved off here, as you can obtain the value `-1` by parsing a string without a number in it at Parsons Green to obtain `0`, then using Notting Hill Gate to turn it to `-1`. This would remove the need to use Cannon Street entirely. Also, there are a couple station names that could be reduced -- "Embankment" can be replaced with "Bank", for instance.