Is this number a prime?

Question

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.

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

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

hello, world!, 13

hello, world!

Answer 2

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 3

Hexagony, 218 92 58 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:

&}=*{&'%!@

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 4

Pyth, 4 bytes

}QPQ

Prints True or False.

Answer 5

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

Answer 6

HTML+CSS, 254+n_max*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 n_max checkboxes with the same name (n_max*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)

Answer 7

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

Answer 8

CJam, 4 bytes

qimp

CJam has a built-in operator for primality testing.

Answer 9

Help, WarDoq!, 1 byte

P

Outputs 1 if the input is prime, 0 otherwise.

Answer 10

Mornington Crescent, 2448 bytes

We're back 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 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.

Answer 11

Haskell, 49 bytes

Using xnor's Corollary to Wilson's Theorem:

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

Answer 12

Brachylog (V2), 1 byte

ṗ

Try it online!

Brachylog (V1), 2 bytes

#p

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 13

Labyrinth, 29 bytes

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

Reads an integer from STDIN and outputs ((n-1)!)^2 mod n. Wilson's 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 14

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 15

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 16

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 17

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 18

Stack Cats, 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!

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 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 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, or use the -D flag to get a complete trace of the entire program. Alternatively, you can use Timwi's EsotericIDE which includes a Stack Cats interpreter with a step-by-step debugger.

Answer 19

Brain-Flak, 112 108 bytes

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

Try it online!

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.

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 20

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 21

Ruby, 15 + 8 = 23 bytes

p$_.to_i.prime?

Sample run:

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

Answer 22

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

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.

Answer 24

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 25

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 26

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

Haskell, 54 bytes

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

Nothing much to explain.

Answer 28

Python 2, 44

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

Like Sp3000's Python answer, but avoids storing the input by counting the variable n up from 1 to the input value.

Answer 29

Regex (.NET), 604 517 499 469 455 bytes

^((?=[6-9](?<1>){6}|)(?=[3-59](?<1>){3}|)(?=[258](?<1>){2}|)(?=[147](?<1>)|).)+$(?<!(?=(?<-1>.)+(?(1)^))\11(?=((?<=(?=(?=((?<-2>)(?=.*$((?<-2>\2)(?<3>)|){9}).)+(?(2)^))(?>(?<-1>)(.)(?<=((?<5-1>\1)|){9}^.*))*(?<2>.(?<=((?<5>)(?<-1>\1)|){9}((?<-1>\1){10}|())((?<2-1>)(?<-3>\3)|){9}(?<-9>(?<-1>))?(?<1>){10}(?<-3>)(?<-1>)(?<5>^.*)))+$(?!\9)(?(3)^)(?<=(?<-5>(?=(?<1>(?=.*$\5)|.)).)*){10}(\12)?()|){9}^.*).)*)(?<-13>){3}^(?<-14>(?(14)|((?<2>(.)?))){10})+.*|^1)

Try it online!
Try it online! - primes matched in unary, for comparison

Takes its input in decimal, which must not have any leading zeros. Output is in the form of "match" (prime) or "no match" (non-prime).

Processing numbers in decimal with a regex has been a very under-explored territory. Previously, the most complicated tasks that had ever been done were:

• Match numbers divisible by 7
• Match correct statements of addition
  • non-negative integers
  • signed numbers with optional decimal point

Matching prime numbers with a regex has been done in unary, but had never before been done in decimal.

The challenges faced here are:

• All the computation of a regex must be done inside the space of the input, and its "variables" (capture groups) can only either be empty or contain substrings from the input.
• The number of times a loop may iterate cannot exceed a polynomial function of the length of the input. (This limit only applies loops of continuous calculation, in which the result of each iteration must be carried on to the next. Searching for a value that fits a property can use backtracking, whose number of "iterations" can go as high as an exponential function of the length of the input, and this regex exploits that for the divisor search.)
• In most regex flavors, there's no mutable data type analogous to an array. In .NET however, Balanced Groups provide what is essentially a stack data type; this can (cumbersomely) be used to emulate an array. The only way to iterate through such a stack is to destroy it, though, so every time this is done, it must be copied to another stack, in reverse order. Thus, it must be copied in reverse a second time to be reused.

I had already written a .NET regex to match primes in decimal a couple weeks before, but it must be given a hard-coded maximum bound. It's 192 bytes in length (and isn't shortened by reducing its limit from \$999\$ to \$255\$, but is shortened to 189 bytes by dropping zero-handling), and does its calculations in unary, after converting the decimal input to unary. (Its numeric variables are represented by the number of captures on each stack, being agnostic to the contents of the captures.) At the time, I thought it would be impossible to do this without a bound.

In order to match primes up to infinity, a very different algorithm must be used: actual base-encoded arithmetic, with long division. This is only possible in the .NET regex engine.

This regex captures the input in unary-coded decimal, where, on a balanced capture group that encodes a number, each digit is represented by a series of contiguous empty captures on the stack (with their count being the digit's value), and each digit is terminated by a non-empty capture. Depending on the capture group, some of them have their termination mark below each digit, and some have it above each digit; when a stack is reversed, this gets flipped. The long division is done in this data type.

Other alternatives would be converting the input from decimal to binary and then doing the arithmetic in binary, or using binary-coded decimal. I initially expected the former would turn out to be shortest, but after finishing and golfing an implementation of reading decimal input into binary, I realized that a prime regex using that would be well over 900 bytes.

.NET has a fairly obscure balanced group operation that is rarely used: (?<name1-name2>pattern). This matches (but does not capture) pattern, captures (pushes a value onto) \k<name1> as the interval from the end of the top capture on \k<name2> to the current cursor position, and then deletes (pops) that top capture from \k<name2>. If the interval is "negative", this actually causes .NET to throw an exception, Index was outside the bounds of the array, the next time that capture is used.

This regex takes advantage of the (?<name1-name2>pattern) syntax for golf reasons, using it as an equivalent for (?<-name2>)(?<name1>). It makes sure to only do this when the cursor is at the beginning of the input string, so that only empty values are pushed onto \k<name1>. This is used in two places, and the first instance only works in RegexOptions.Compiled mode; without it, the above-described exception is thrown with inputs \$\ge 21\$, probably because some of the \1 empties it pops were captured from elsewhere than the beginning of the string. A third potential place for this trick would seem to be (?<-2>\2)(?<3>), but if an attempt is made to convert it from (?=.*$((?<-2>\2)(?<3>)|){9}) to (?<=((?<3-2>\2)|){9}^.*), the exception is thrown regardless of mode. Seeing as there's no debugger for .NET regex, it would be tricky to dig deeper into the conditional nature of this error.

When interpreting the explanation below, remember that lookbehinds in .NET, (?<=...) and (?<!...), are evaluated from right to left – so read those from bottom to top, one quantified token at a time. When entering a lookahead inside a lookbehind, go back to reading from top to bottom.

^
# Read decimal number into C1, in unary-coded decimal
(
    # Read this digit, adding it to C1
    (?=[6-9] (?<1>){6}|)  # C1 digit += 6, if digit is in [      6789]
    (?=[3-59](?<1>){3}|)  # C1 digit += 3, if digit is in [   345   9]
    (?=[258] (?<1>){2}|)  # C1 digit += 2, if digit is in [  2  5  8 ]
    (?=[147] (?<1>)   |)  # C1 digit += 1, if digit is in [ 1  4  7  ]
    .                     # C1: push separator
)+$
# C1 now has least-significant digit on top, separator above
(?<!
    (?= # Assert C1==0; since it must have the same number of separators as
        # there are digits in the input, if once we remove that number of
        # captures from it, it has nothing remaining, its value was zero.
        (?<-1>.)+
        (?(1)^)
    )
    \11 # Assert the quotient is not a power of 10 (all we really want is to
        # assert the quotient != 1, but that would be more complex to do);
        # discarding the powers of 10 other than 1 is harmless, because in those
        # cases where the remainder is zero, twice the divisor will yield half
        # the quotient and the remainder will still be zero.
    (?= # Calculate the remainder of division, letting C1 = C1 % C2:
        # C2 now has most-significant digit on top, separator above
        (                                      # C2
            (?<=
                (?=
                    # C1 now has least-significant digit on top, separator above
                    (?=                        # C3 = reverse(C2)
                        (                      # C3
                            (?<-2>)            # C2: pop separator
                            (?=
                                .*$
                                (
                                    (?<-2>\2)
                                    (?<3>)
                                |
                                ){9}
                            )
                            .                  # C3: push separator
                        )+
                        # Don't let C2 grow to be longer in digits than the
                        # input number
                        (?(2)^)
                    )
                    # C3 now has least-significant digit on top, separator above

                    # mutually align C1 with C3: C5 = reverse(C1), giving it its
                    # least-significant portion with no C3 digits to subtract
                    (?>
                        (?<-1>)                # C1: pop separator
                        (.)                    # C5: push separator
                        (?<=
                            (
                                # I'm not currently sure why "(?<5-1>\1)" can be
                                # used here as a shorthand for "(?<-1>\1)(?<5>)"
                                # but I think it has something to do with the
                                # fact that this mutually-align loop will only
                                # do a nonzero number of iterations after C2 has
                                # been padded with at least one leading zero,
                                # meaning C1 will have already been rewritten by
                                # reversing C5, i.e. we won't be dealing with
                                # the original capture of C1.
                                (?<5-1>\1)
                            |
                            ){9}
                            ^.*
                        )
                    )*

                    # \9 = borrow flag = unset = 0 (clear)

                    # C5 = reverse(C1 - C3); C2 = reverse(C3)
                    (?<2>
                        .       # C2: push separator at the end of each
                                #     iteration
                        (?<=
                            (                  # C5 digit = C1 digit
                                (?<5>)
                                (?<-1>\1)
                            |
                            ){9}
                            (
                                (?<-1>\1){10}  # C1 digit -= 10
                            |              # or...
                                ()             # \9 borrow flag = set
                            )
                            (                  # C1 digit -= C3 digit;
                                               # C2 digit  = C3 digit
                                # Using "(?<2-1>)" as a shorthand for
                                # "(?<-1>(?<2>))" works here because it is
                                # guaranteed to pull only from the captures
                                # pushed by "(?<1>){10}", which is always done
                                # at the beginning of the string.
                                (?<2-1>)
                                (?<-3>\3)
                            |
                            ){9}
                            (?<-9>             # if \9 borrow flag is set,
                                               # unset it...
                                (?<-1>)        # ...and C1 digit -= 1
                            )?
                            (?<1>){10}         # C1 digit += 10
                            (?<-3>)            # C3: pop separator
                            (?<-1>)            # C1: pop separator
                            (?<5>^.*)          # C5: push separator
                        )
                    )+$
                    (?!\9)       # Assert borrow is 0 (clear)
                    (?(3)^)      # Assert C3 has been emptied, and thus
                                 # completely processed (and by implication,
                                 # so has C1 been)
                    # C2 now has most-significant digit on top, separator above
                    # C5 now has most-significant digit on top, separator below
                    (?<=                       # C1 = reverse(C5)
                        (?<-5>
                            (?=
                                (?<1>
                                    (?=.*$\5)
                                |
                                    .
                                )
                            )
                            .
                        )*
                    ){10}
                    # C1 now has least-significant digit on top, separator above
                    (\12)?       # \11 = set if \12 is already set
                    ()           # \12 = set
                |
                    # or do nothing
                ){9}             # This digit of the quotient can range from
                                 # 0 to 9 (but we don't have to save the
                                 # quotient, just the remainder)
                ^.*
            )
            .   # pad C2 with one more leading zero
        )*
    )
    (?<-13>){3} # Assert C2 >= 2, unless C2 has a leading zero, using C13 as a
                # disposable copy of C2. The only numeric value of C2 without a
                # leading zero that puts only 2 captures on it is C2 == 1.
                # Values of C2 with leading zero(s) will cause the long division
                # algorithm to give an incorrect result, but never a false
                # positive of getting a remainder of zero, so this only results
                # in a little slowdown, testing invalid divisors.
    # C2 now has most-significant digit on top, separator above
    ^
    (?<-14>     # C13 = C2 = arbitrary number (a divisor to test)
        (?(14)|
            ((?<2>
                (.)?    # \14 = set optionally, ending incrementing of digit and
                        #      pushing a separator onto C2; due to the outer
                        #      loop being "(?<-14>)", if it still isn't set by
                        #      the last iteration of this loop, it will be.
            ))
        ){10}
    )+
    .*          # allow C2 to have fewer digits than the input
|
    ^1          # exclude 1, which is non-composite but also non-prime
)

As per the challenge rules, this does not bother to avoid matching \$0\$. But this can be fixed by changing |^1 to |^0*1? or |^[01], at a cost of 3 bytes.

Speed-improved version, 525 495 483 bytes

^((?=[6-9](?<1>){6}|)(?=[3-59](?<1>){3}|)(?=[258](?<1>){2}|)(?=[147](?<1>)|).)+$(?<!(?=(?<-1>.)+(?(1)^))\11(?=((?<=(?=(?=((?<-2>)(?=.*$((?<-2>\2)(?<3>)|){9}).)+(?(2)^))(?>(?<-1>)(.)(?<=((?<5-1>\1)|){9}^.*))*(?<2>.(?<=((?<5>)(?<-1>\1)|){9}((?<-1>\1){10}|())((?<2-1>)(?<-3>\3)|){9}(?<-9>(?<-1>))?(?<1>){10}(?<-3>)(?<-1>)(?<5>^.*)))+$(?!\9)(?(3)^)(?<=(?<-5>(?=(?<1>(?=.*$\5)|.)).)*){10}(\12)?()|){9}^.*).)*)(?<-13>){2}\13(?<-13>)^(?<-14>(?(14)|((?<2>(.)?))){10}(?<-15>))+(?<15>)(.)*|^1)

Try it online!
Try it online! - primes matched in unary, for comparison
Try it on regex101 - 487 bytes*

This version limits its divisor search to \$\lceil{n\over 2}\rceil\$ digits, where \$n\$ is the number if digits in the input. This is guaranteed to go at least as high as the square root of the input number. It can test all the numbers up to \$3333\$ on TIO in 59 seconds.

Only the section that differs is explained below:

    # Assert C2 >= 2, using C13 as a disposal copy of C2:
        # The only numeric value of C2 without a leading zero that puts only 2
        # captures on it is C2 == 1
        (?<-13>){2}
        \13
        (?<-13>)
    # C2 now has most-significant digit on top, separator above
    ^
    (?<-14>         # C13 = C2 = arbitrary number (a divisor to test)
        (?(14)|
            ((?<2>
                (.)?    # \14 = set optionally, ending incrementing of digit and
                        #      pushing a separator onto C2; due to the outer
                        #      loop being "(?<-14>)", if it still isn't set by
                        #      the last iteration of this loop, it will be.
            ))
        ){10}
        (?<-15>)
    )+
    (?<15>)         # C15 += 1
    (.)*            # allow C2 to have fewer digits than the input;
                    # C15 += number digits skipped

*regex101 doesn't make it possible to enable the Compiled flag, so it throws the error in versions that use the (?<5-1>\1) shorthand. Here is commented view of the section modified to avoid this error (making it 4 bytes longer):

                    # mutually align C1 with C3: C5 = reverse(C1), giving it its
                    # least-significant portion with no C3 digits to subtract
                    (?>
                        (?<-1>)                # C1: pop separator
                        (.)                    # C5: push separator
                        (?=
                            .*$
                            (
                                (?<-1>\1)
                                (?<5>)
                            |
                            ){9}
                        )
                    )*

                    # \9 = borrow flag = unset = 0 (clear)

Regex (.NET), 692 449 396 325 bytes

^((?=(0|)).){2,}$(?<!(?=(?=((?<=(?=(?=(?<-3>(?=((?=.*$\3)|.)).)+(?(3)^))(?<-2>(?=((?=.*$\2)|.)).)*(?<-2>.(?<=(?=(?=(\2\4^|(?!\2^|\4^)|.))(?=(?<5>\7\6^|(?!\7|\6^)|.))(?(7)\2^(?!\4^)(?<-7>)|(?!\2^)\4^())?(?<3>\4^|.))^.*)(?<-4>))+$(?!\7)(?(4)^)(?<=(?<-5>(?=(?<2>(?=.*$\5)|.)).)+)|)^.*).)*)(?<-2>\2)+$)^(\B(?<3>.)|.(?<3>)){2,}.+)

Try it online!
Try it online! - primes matched in unary, for comparison

Takes its input in binary, which must not have any leading zeros. As such, it is non-competing in this challenge, which specifies that input may be taken in decimal, unary, or byte array.

The internal representation of a binary number as a capture stack is for \$0\$s to be non-empty captures, and \$1\$s to be empty captures. As such, the latter can match after the end of the string, and the former cannot.

^
# Read binary number into C2
(
    (?=
        (0|)  # C2
    )
    .
){2,}$  # at least 2 iterations to exclude 0 and 1 as non-prime
# C2 now has least-significant bit on top
(?<!
    (?=
        (?=
            (                                      # C3
                (?<=
                    (?=
                        # C2 now has least-significant bit on top
                        (?=
                            (?<-3>                 # C4 = reverse(C3)
                                (?=
                                    (              # C4
                                        (?=.*$\3)
                                    |
                                        .
                                    )
                                )
                                .
                            )+
                            # Don't let C3 grow to be longer in bits than the
                            # input number
                            (?(3)^)
                        )
                        # C4 now has least-significant bit on top

                        # mutually align C2 with C4
                        (?<-2>                     # C5 = reverse(C2)
                            (?=
                                (                  # C5
                                    (?=.*$\2)
                                |
                                    .
                                )
                            )
                            .
                        )*

                        # \7 = borrow flag = unset = 0 (clear)

                        # C5 = reverse(C2 - C4); C3 = reverse(C4)
                        (?<-2>
                            .
                            (?<=
                                (?=
                                    (?=
                                        (                # \6 = \2 xnor \4
                                            \2\4^
                                        |
                                            (?!\2^|\4^)
                                        |
                                            .
                                        )
                                    )
                                    (?=
                                        (?<5>            # C5: push bit \6 xnor \7
                                            \7\6^
                                        |
                                            (?!\7|\6^)
                                        |
                                            .
                                        )
                                    )
                                    # if \2 xnor \7, and \4 xor \7, then \7 = not \7
                                    (?(7)
                                        \2^
                                        (?!\4^)
                                        (?<-7>)          # \7 = unset borrow flag
                                    |
                                        (?!\2^)
                                        \4^
                                        ()               # \7 = set borrow flag
                                    )?
                                    (?<3>                # C3: push bit from C4
                                        \4^
                                    |
                                        .
                                    )
                                )
                                ^.*
                            )
                            (?<-4>)
                        )+$
                        (?!\7)       # Assert borrow is 0 (clear)
                        (?(4)^)      # Assert C4 has been emptied, and thus
                                     # completely processed (and by implication,
                                     # so has C2 been)
                        # C5 and C3 now have most-significant bit on top
                        (?<=
                            (?<-5>                 # C2 = reverse(C5)
                                (?=
                                    (?<2>
                                        (?=.*$\5)
                                    |
                                        .
                                    )
                                )
                                .
                            )+
                        )
                    |
                        # or do nothing
                    )
                    ^.*
                )
                .   # pad C3 with one more leading zero
            )*
        )
        # Assert C2 == 0
        (?<-2>
            \2
        )+$
    )
    # C3 now has most-significant bit on top
    ^
    (         # C3 = arbitrary number
        \B  # most-significant digit must be 1
        (?<3>.)  # C3: push 0 (non-empty)
    |
        .(?<3>)  # C3: push 1 (empty)
    ){2,}     # give C3 at least 2 bits, to force C3 >= 2
    .+        # force C3 to have at least 1 less bit than C5, making C3 < C5
)

Answer 30

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.

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