# 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

• Can I take inputs as negative numbers, where abs(input) would be the number I am testing? – Stan Strum Sep 6 '17 at 3:40
• 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? codegolf.meta.stackexchange.com/questions/2447/… – Lyndon White Dec 12 '17 at 6:21
• @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. – Dennis Dec 12 '17 at 12:51
• @Shaggy Seems like a question for meta. – Dennis Jun 25 '18 at 13:44
• Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. – Shaggy Jun 25 '18 at 13:45

# C#, 156133 130 bytes

(second attempt after the first didn't exactly work)

using System;class C{static void Main(string[]a){int i=2,n=int.Parse(a[0]),b=n-1;for(;i<=n/2;)b*=n%i++>0?1:0;Console.Write(b>0);}}

(and thanks to Dennis for helping me out with my first code golf :) )

• Welcome to Programming Puzzles & Code Golf! In its current form, your answer simply prints the result of the last divisibility test. You can fix that by initializing b=1 and multiplying b by the results (b*=...). – Dennis Sep 15 '15 at 16:05
• I'm not a C# expert, but since C# doesn't have implicit int-to-bool conversion, I don't think 1/0 satisfy the definition of truthy/falsy. using System;class C{static void Main(string[] a){int i=2,n=Int32.Parse(a[0]),b=n-1;for(;i<=n/2;)b*=n%i++>0?1:0;Console.Write(b>0);}} produces the proper output (and is 23 bytes shorter). – Dennis Sep 15 '15 at 16:14
• Ah, I see. I would have said that 1/0 does satisfy the condition, but I'll stick with your definition. :) – helencrump Sep 15 '15 at 16:16
• For most languages, it does. However, our definition counts 1 as truthy if if(1){...} executes the block, which doesn't seem to wok in C# (again, not an expert). – Dennis Sep 15 '15 at 16:20
• You can remove the space between string[] and a. Also, you can change Int32 to just int. – LegionMammal978 Sep 19 '15 at 15:53

# Perl, 25 bytes

#!perl -p
$_=2==grep$'%$_<1,//..$_

Counting the shebang as one. Input is taken, in decimal, from stdin.

Sample Usage:

$echo 101101 | perl isprime.pl$ echo 101107 | perl isprime.pl
1

Perl, 24 bytes

#!perl -p
$_=3>grep$'%$_<1,//..$_

One byte can be shaved by replacing 2== with 3>, however, it will incorrectly identify both 0 and 1 as prime.

## Ouroboros, 39 bytes

Sr0s1(
)S1+.@@.@@%!Ms+S.@@.@>6*(6s2=n1(

Each line of code in an Ouroboros program represents a snake eating its tail.

Snake 1

S switches to the shared stack; r0 reads a number from input and pushes a 0. Then s1( switches back to snake 1's stack, pushes a 1, and eats that many characters of the tail. The instruction pointer is on a character that gets eaten, so the snake dies.

Snake 2

Here the magic happens. We check every number from 1 up through n, adding 1 to a tally if it divides our input number. At the end we check whether the number of factors equals 2 and print 1 or 0 accordingly.

) is a no-op the first time through. S switches to the shared stack. We then push a 1 (just after the first snake pushes its 0) and add. The stack now contains the input number and the factor we're testing for divisibility.

.@@.@@%! makes copies of both numbers, takes the modulus, and negates (1 if it is a factor, 0 if not). M moves that result to snake 2's stack, where we're storing the tally of factors; then s+S switches to that stack, adds the top two numbers, and switches back to the shared stack.

Next, .@@.@>6* makes copies of both numbers and tests whether the input number is greater than the test factor, pushing 6 if so and 0 if not. ( then eats that many characters from the end of the snake.

• If the number is still greater than the factor, the uneaten code now ends after (6. This pushes a 6 and wraps execution back to the beginning. There ) regurgitates the 6 characters we just ate. S does nothing because we're already on the shared stack. 1+ then increments the test factor, and we go through the loop again.
• When the number is no longer greater than the factor, nothing gets eaten and execution continues. We push a 6 but then switch to snake 2's stack, where the number of factors is sitting. 2=n tests whether it's 2 and outputs the result (1 or 0) as a number. Finally, 1( eats the last character and dies.

Try it out

// Define Stack class
function Stack() {
this.stack = [];
this.length = 0;
}
Stack.prototype.push = function(item) {
this.stack.push(item);
this.length++;
}
Stack.prototype.pop = function() {
var result = 0;
if (this.length > 0) {
result = this.stack.pop();
this.length--;
}
return result;
}
Stack.prototype.top = function() {
var result = 0;
if (this.length > 0) {
result = this.stack[this.length - 1];
}
return result;
}
Stack.prototype.toString = function() {
return "" + this.stack;
}

// Define Snake class
function Snake(code) {
this.code = code;
this.length = this.code.length;
this.ip = 0;
this.ownStack = new Stack();
this.currStack = this.ownStack;
this.alive = true;
this.wait = 0;
this.partialString = this.partialNumber = null;
}
Snake.prototype.step = function() {
if (!this.alive) {
return null;
}
if (this.wait > 0) {
this.wait--;
return null;
}
var instruction = this.code.charAt(this.ip);
var output = null;
console.log("Executing instruction " + instruction);
if (this.partialString !== null) {
// We're in the middle of a double-quoted string
if (instruction == '"') {
// Close the string and push its character codes in reverse order
for (var i = this.partialString.length - 1; i >= 0; i--) {
this.currStack.push(this.partialString.charCodeAt(i));
}
this.partialString = null;
} else {
this.partialString += instruction;
}
} else if (instruction == '"') {
this.partialString = "";
} else if ("0" <= instruction && instruction <= "9") {
if (this.partialNumber !== null) {
this.partialNumber = this.partialNumber + instruction;  // NB: concatenation!
} else {
this.partialNumber = instruction;
}
next = this.code.charAt((this.ip + 1) % this.length);
if (next < "0" || "9" < next) {
// Next instruction is non-numeric, so end number and push it
this.currStack.push(+this.partialNumber);
this.partialNumber = null;
}
} else if ("a" <= instruction && instruction <= "f") {
// a-f push numbers 10 through 15
var value = instruction.charCodeAt(0) - 87;
this.currStack.push(value);
} else if (instruction == "") { // Toggle the current stack if (this.currStack === this.ownStack) { this.currStack = this.program.sharedStack; } else { this.currStack = this.ownStack; } } else if (instruction == "s") { this.currStack = this.ownStack; } else if (instruction == "S") { this.currStack = this.program.sharedStack; } else if (instruction == "l") { this.currStack.push(this.ownStack.length); } else if (instruction == "L") { this.currStack.push(this.program.sharedStack.length); } else if (instruction == ".") { var item = this.currStack.pop(); this.currStack.push(item); this.currStack.push(item); } else if (instruction == "m") { var item = this.ownStack.pop(); this.program.sharedStack.push(item); } else if (instruction == "M") { var item = this.program.sharedStack.pop(); this.ownStack.push(item); } else if (instruction == "y") { var item = this.ownStack.top(); this.program.sharedStack.push(item); } else if (instruction == "Y") { var item = this.program.sharedStack.top(); this.ownStack.push(item); } else if (instruction == "\\") { var top = this.currStack.pop(); var next = this.currStack.pop() this.currStack.push(top); this.currStack.push(next); } else if (instruction == "@") { var c = this.currStack.pop(); var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(c); this.currStack.push(a); this.currStack.push(b); } else if (instruction == ";") { this.currStack.pop(); } else if (instruction == "+") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(a + b); } else if (instruction == "-") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(a - b); } else if (instruction == "*") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(a * b); } else if (instruction == "/") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(a / b); } else if (instruction == "%") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(a % b); } else if (instruction == "_") { this.currStack.push(-this.currStack.pop()); } else if (instruction == "I") { var value = this.currStack.pop(); if (value < 0) { this.currStack.push(Math.ceil(value)); } else { this.currStack.push(Math.floor(value)); } } else if (instruction == ">") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(+(a > b)); } else if (instruction == "<") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(+(a < b)); } else if (instruction == "=") { var b = this.currStack.pop(); var a = this.currStack.pop(); this.currStack.push(+(a == b)); } else if (instruction == "!") { this.currStack.push(+ !this.currStack.pop()); } else if (instruction == "?") { this.currStack.push(Math.random()); } else if (instruction == "n") { output = "" + this.currStack.pop(); } else if (instruction == "o") { output = String.fromCharCode(this.currStack.pop()); } else if (instruction == "r") { var input = this.program.io.getNumber(); this.currStack.push(input); } else if (instruction == "i") { var input = this.program.io.getChar(); this.currStack.push(input); } else if (instruction == "(") { this.length -= Math.floor(this.currStack.pop()); this.length = Math.max(this.length, 0); } else if (instruction == ")") { this.length += Math.floor(this.currStack.pop()); this.length = Math.min(this.length, this.code.length); } else if (instruction == "w") { this.wait = this.currStack.pop(); } // Any unrecognized character is a no-op if (this.ip >= this.length) { // We've swallowed the IP, so this snake dies this.alive = false; this.program.snakesLiving--; } else { // Increment IP and loop if appropriate this.ip = (this.ip + 1) % this.length; } return output; } Snake.prototype.getHighlightedCode = function() { var result = ""; for (var i = 0; i < this.code.length; i++) { if (i == this.length) { result += '<span class="swallowedCode">'; } if (i == this.ip) { if (this.wait > 0) { result += '<span class="nextActiveToken">'; } else { result += '<span class="activeToken">'; } result += escapeEntities(this.code.charAt(i)) + '</span>'; } else { result += escapeEntities(this.code.charAt(i)); } } if (this.length < this.code.length) { result += '</span>'; } return result; } // Define Program class function Program(source, speed, io) { this.sharedStack = new Stack(); this.snakes = source.split(/\r?\n/).map(function(snakeCode) { var snake = new Snake(snakeCode); snake.program = this; snake.sharedStack = this.sharedStack; return snake; }.bind(this)); this.snakesLiving = this.snakes.length; this.io = io; this.speed = speed || 10; this.halting = false; } Program.prototype.run = function() { this.step(); if (this.snakesLiving) { this.timeout = window.setTimeout(this.run.bind(this), 1000 / this.speed); } } Program.prototype.step = function() { for (var s = 0; s < this.snakes.length; s++) { var output = this.snakes[s].step(); if (output) { this.io.print(output); } } this.io.displaySource(this.snakes.map(function (snake) { return snake.getHighlightedCode(); }).join("<br>")); } Program.prototype.halt = function() { window.clearTimeout(this.timeout); } var ioFunctions = { print: function (item) { var stdout = document.getElementById('stdout'); stdout.value += "" + item; }, getChar: function () { if (inputData) { var inputChar = inputData[0]; inputData = inputData.slice(1); result = inputChar.charCodeAt(0); } else { result = -1; } var stdinDisplay = document.getElementById('stdin-display'); stdinDisplay.innerHTML = escapeEntities(inputData); return result; }, getNumber: function () { while (inputData && (inputData[0] < "0" || "9" < inputData[0])) { inputData = inputData.slice(1); } if (inputData) { var inputNumber = inputData.match(/\d+/)[0]; inputData = inputData.slice(inputNumber.length); result = +inputNumber; } else { result = -1; } var stdinDisplay = document.getElementById('stdin-display'); stdinDisplay.innerHTML = escapeEntities(inputData); return result; }, displaySource: function (formattedCode) { var sourceDisplay = document.getElementById('source-display'); sourceDisplay.innerHTML = formattedCode; } }; var program = null; var inputData = null; function showEditor() { var source = document.getElementById('source'), sourceDisplayWrapper = document.getElementById('source-display-wrapper'), stdin = document.getElementById('stdin'), stdinDisplayWrapper = document.getElementById('stdin-display-wrapper'); source.style.display = "block"; stdin.style.display = "block"; sourceDisplayWrapper.style.display = "none"; stdinDisplayWrapper.style.display = "none"; source.focus(); } function hideEditor() { var source = document.getElementById('source'), sourceDisplay = document.getElementById('source-display'), sourceDisplayWrapper = document.getElementById('source-display-wrapper'), stdin = document.getElementById('stdin'), stdinDisplay = document.getElementById('stdin-display'), stdinDisplayWrapper = document.getElementById('stdin-display-wrapper'); source.style.display = "none"; stdin.style.display = "none"; sourceDisplayWrapper.style.display = "block"; stdinDisplayWrapper.style.display = "block"; var sourceHeight = getComputedStyle(source).height, stdinHeight = getComputedStyle(stdin).height; sourceDisplayWrapper.style.minHeight = sourceHeight; sourceDisplayWrapper.style.maxHeight = sourceHeight; stdinDisplayWrapper.style.minHeight = stdinHeight; stdinDisplayWrapper.style.maxHeight = stdinHeight; sourceDisplay.textContent = source.value; stdinDisplay.textContent = stdin.value; } function escapeEntities(input) { return input.replace(/&/g, '&amp;').replace(/</g, '&lt;').replace(/>/g, '&gt;'); } function resetProgram() { var stdout = document.getElementById('stdout'); stdout.value = null; if (program !== null) { program.halt(); } program = null; inputData = null; showEditor(); } function initProgram() { var source = document.getElementById('source'), stepsPerSecond = document.getElementById('steps-per-second'), stdin = document.getElementById('stdin'); program = new Program(source.value, +stepsPerSecond.innerHTML, ioFunctions); hideEditor(); inputData = stdin.value; } function runBtnClick() { if (program === null || program.snakesLiving == 0) { resetProgram(); initProgram(); } else { program.halt(); var stepsPerSecond = document.getElementById('steps-per-second'); program.speed = +stepsPerSecond.innerHTML; } program.run(); } function stepBtnClick() { if (program === null) { initProgram(); } else { program.halt(); } program.step(); } function sourceDisplayClick() { resetProgram(); } .container { width: 100%; } .so-box { font-family:'Helvetica Neue', Arial, sans-serif; font-weight: bold; color: #fff; text-align: center; padding: .3em .7em; font-size: 1em; line-height: 1.1; border: 1px solid #c47b07; -webkit-box-shadow: 0 2px 2px rgba(0, 0, 0, 0.3), 0 2px 0 rgba(255, 255, 255, 0.15) inset; text-shadow: 0 0 2px rgba(0, 0, 0, 0.5); background: #f88912; box-shadow: 0 2px 2px rgba(0, 0, 0, 0.3), 0 2px 0 rgba(255, 255, 255, 0.15) inset; } .control { display: inline-block; border-radius: 6px; float: left; margin-right: 25px; cursor: pointer; } .option { padding: 10px 20px; margin-right: 25px; float: left; } h1 { text-align: center; font-family: Georgia, 'Times New Roman', serif; } a { text-decoration: none; } input, textarea { box-sizing: border-box; } textarea { display: block; white-space: pre; overflow: auto; height: 50px; width: 100%; max-width: 100%; min-height: 25px; } span[contenteditable] { padding: 2px 6px; background: #cc7801; color: #fff; } #stdout-container, #stdin-container { height: auto; padding: 6px 0; } #reset { float: right; } #source-display-wrapper , #stdin-display-wrapper{ display: none; width: 100%; height: 100%; overflow: auto; border: 1px solid black; box-sizing: border-box; } #source-display , #stdin-display{ font-family: monospace; white-space: pre; padding: 2px; } .activeToken { background: #f93; } .nextActiveToken { background: #bbb; } .swallowedCode{ color: #999; } .clearfix:after { content:"."; display: block; height: 0; clear: both; visibility: hidden; } .clearfix { display: inline-block; } * html .clearfix { height: 1%; } .clearfix { display: block; } <!-- Designed and written 2015 by D. Loscutoff Much of the HTML and CSS was taken from this Befunge interpreter by Ingo Bürk: http://codegolf.stackexchange.com/a/40331/16766 --> <div class="container"> <textarea id="source" placeholder="Enter your program here" wrap="off">Sr0s1( )S1+.@@.@@%!Ms+S.@@.@>6*(6s2=n1(</textarea> <div id="source-display-wrapper" onclick="sourceDisplayClick()"><div id="source-display"></div></div></div><div id="stdin-container" class="container"> <textarea id="stdin" placeholder="Input" wrap="off">5</textarea> <div id="stdin-display-wrapper" onclick="stdinDisplayClick()"><div id="stdin-display"></div></div></div><div id="controls-container" class="container clearfix"><input type="button" id="run" class="control so-box" value="Run" onclick="runBtnClick()" /><input type="button" id="pause" class="control so-box" value="Pause" onclick="program.halt()" /><input type="button" id="step" class="control so-box" value="Step" onclick="stepBtnClick()" /><input type="button" id="reset" class="control so-box" value="Reset" onclick="resetProgram()" /></div><div id="stdout-container" class="container"><textarea id="stdout" placeholder="Output" wrap="off" readonly></textarea></div><div id="options-container" class="container"><div class="option so-box">Steps per Second: <span id="steps-per-second" contenteditable>20</span></div></div> # Vitsy, 2 bytes Yes, it's that Simple...x. pN Implicit grab of STDIN as number, if possible. p If it's prime, push 1 to the stack. Else, push 0. N Output as number. Interestingly, adding an i to this will also find prime characters. ipN For input % (ASCII character 37) will output 1. • Haha, so punny! +1 from me. – Conor O'Brien Nov 7 '15 at 19:00 # Jelly, 4 bytes ’!²% Try it online! Jelly has a built-in for primality testing (ÆP, 2 bytes), but it uses a probabilistic method. This answer uses Wilson's theorem instead. For input x, it calculates (x - 1)!² % x, which yields 1 if x is a prime number and 0 if not. Input: x ’ Decrement; compute x - 1. ! Apply factorial atop the previous result. Yields (x - 1)!. ² Apply square atop the previous result. Yields (x - 1)!². % Do a modulus hook; compute (x - 1)!² % x. # Par, 9 bytes Counted using its own, non-UTF-8 encoding. ✶↓″↑p~1=* Explanation: ✶ Parse the input (which is implicitly on the stack). n ↓ Subtract one. (n-1) ″ Duplicate. (n-1) (n-1) ↑ Add one. (n-1) n p Prime divisors. For 1, this strangely returns (1). (n-1) np ~ Length. (n-1) np~ 1= Is the length one? This is iff n isn't composite. (n-1) noncomposite(n) * Multiply the top of stack. (n-1)*noncomposite(n) # Binary-Encoded Golfical, 13+1 (-x flag) = 14 bytes This can converted to the standard graphical version using the included Encoder utility, or run directly by adding the -x flag. Hex dump: 00 40 02 15 14 49 1b 00 00 00 01 17 17 The original image: Zoomed in 100x with color value lables: Explanation: 10,0,0->Input number 14,3,0->Turn right if prime 11,0,1->Go east 0,0,0->Set to 0 0,0,1->Set to 1 10,1,0->Print number # Arcyóu, 42 7 bytes Note: I added a builtin for primality testing after I submitted this answer. In the interest of completeness, I have left the old answer below, but this is the new official answer: (p?(#(l Primality check on a line of input casted to int. ### Old answer: ((F(n)(?([ n)(&(f x(_ 2 n)(% n x)))f))(#(l Arcyóu is a LISP-like golfing language of my own devising. Explanation: ((F(n) ; Anonymous function taking one argument n (? ([ n) ; If-statement with condition n-1 (handling the special case) (& ; & is both bitwise AND and an 'all' function (f x (_ 2 n) ; For loop iterating over a range from 2 to n (% n x))) ; n mod x f)) ; If n did equal 1, return false (# (l ; Now call the function on a line of input casted to int The interpreter allows you to leave off final close-parens, since adding them back is trivial. # MediaWiki templates with ParserFunctions, 101 + 1 = 102 bytes (for title) {{#ifexpr:{{{n}}} mod {{{f|(n-1)}}}==0|false|{{#ifexpr:{{{f}}}==1|true|{{:p|n=n|f={{#expr:f-1}}}}}}}} Ungolfed: {{#ifexpr:{{{n}}} mod {{{f|(n-1)}}}==0|false| {{#ifexpr:{{{f}}}==1|true| {{p|n=n|f={{#expr:f-1}}}} }} }} This recursive trial division method theoretically works, but to determine the primality of a positive integer n,wgMaxTemplateDepth (in the MediaWiki config) must exceed n - 2.

• So, in practice, this works for no single input? According to the rules, it must work at least for integers 1 to 255... – Dennis Dec 21 '15 at 20:25
• This solution is valid for wikis that allow at least a recursive depth of 253. – DuhHello Dec 21 '15 at 20:29

# Befunge 93, 44 bytes

&:v>0.@       @.-1<
03<_v#%p03+1:g03::_^#g

This works by trial division.

There's a hidden unprintable character between the v> on the first line; it's the character whose value is 2. The base64 of the file is as follows:

Jjp2Aj4wLkAgICAgICAgQC4tMTwKMDM8X3YjJXAwMysxOmcwMzo6X14jYGc=

Opening it as hex in Sublime Text looks like this (newline confusion, though):

263a 7602 3e30 2e40 2020 2020 2020 2040
2e2d 313c 0d0a 3033 3c5f 7623 2570 3033
2b31 3a67 3033 3a3a 5f5e 2360 670d 0a

# 𝔼𝕊𝕄𝕚𝕟, 3 chars / 6 bytes

МȜï

Try it here (Firefox only).

Not sure why I didn't post this earlier...

### Bonus solution, 5 chars / 10 bytes

!МȝïꝈ

Try it here (Firefox only).

Checks if the input's array of prime factorization is greater than 0.

# Lambda Calculus, 615 bytes

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))

Inspired by the turing machine solution, here is a Lambda Calculus solution! You can test this code in this lambda evaluator, or in this one. The second one stops every 400 reductions so its more stable on big inputs (>11), but the first one is by far the nicest. Just paste the code in the text box and type a number behind it.

For example

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))
4

gives

\x y. y  ;false

And

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))
5

gives

\x y. x ;true

# MATL, 2 bytes

Zp

Try it online!

Takes input implicitly. For positive input, function Zp outputs true (displayed as 1) if the number is prime, ans false (0) otherwise.

# Scratch, 17 blocks (currently glitchy)

demo

Self-explanatory...
Edit: I fixed 2 bugs. But, if you enter 1, it gets in an infinite loop...

• I tried the demo, and entering 7 returns False? – mathmandan Oct 21 '15 at 21:19
• @mathmandan: Yeah, there were 2 bugs. I'll fix them, but the block count will be the same. – user46167 Oct 21 '15 at 22:54
• This seems to loop forever for input 1. – Dennis Oct 22 '15 at 1:46
• @Dennis: Noted. Will fix with 5 more blocks – user46167 Oct 22 '15 at 18:55
• As before: Scratch is typically scored by the number of bytes in the corresponding scratchblocks code here. – SuperJedi224 Oct 29 '15 at 1:09

# JavaScript (ES6), 54 bytes

Outputs 1 for prime, 0 for non-prime. All four JS solutions so far were based on the regex, so I thought I'd be brave and try one without.

# Turtlèd, 490 487 451 bytes

Turtlèd does not support newlines in code... so oneliner fun!

golfed some bytes for not needing to support 0

Golfed some bytes removing useless code, and some other tricks

?#0#.:l( >;,u,[ :ll[*,l]d],u{*{*r}l' d{ l}[ (*.d)(0'1d)(1'2d)(2'3d)(3'4d)(4'5d)(5'6d)(6'7d)(7'8d)(8'9d)(9.l( .))]u[ r]lu}u2[#[ ;{ l}[ (0u.)(1u'1)(2u'2)(3u'3)(4u'4)(5u'5)(6u'6)(7u'7)(8u'8)(9u'9)dl]ur[ r]l[#[ r]l[ (0'9l( '#;))(1.;)(2'1;)(3'2;)(4'3;)(5'4;)(6'5;)(7'6;)(8'7;)(9'8;)]uuu[*r]{*l}u{*r}'*{*l}:;{ l}[ l]r]' uu[*r]{*r}d]l(*,(*@1)(1@0)'*)u{*' l}:;d[ (0'9l( '#l))(1.d)(2'1d)(3'2d)(4'3d)(5'4d)(6'5d)(7'6d)(8'7d)(9'8d)]r( u[ r]uu)][ [ l]r[ ' r]ul],)

Try it online!

I am most certainly not going to explain this with the annotations for each part of the code, at least not right now.

## General explanation:

The program writes 0, takes integer input, if it is not one (if it is, it skips the rest of the code), it writes out two lines of asterisks, removing the zero that was written, one to compare for the prime checking, one to turn into a decimal string. It turns the lower one into a decimal string, then moves the decimal string up one. It writes out a single asterisk into a line above the other for each decrement of the upper decimal string. when goes below zero, the program moves the decimal string back up again, and keeps going on the upper line until it either aligns with the lower line, or goes past it. If it aligns, it sets the character variable to 1, if the character variable has not already been set to one. This is because it has no method to distinguish one when testing divisibility, so this makes it so it has to have more than one factor match. If it has been set to one, it sets it to zero. After it has tested all the numbers from n-1 to 1, it cleans up all the mess that it used to test the primality, then writes the character variable, which will be one if prime, else 0

• Input 1 seems to result in an infinite loop. – Dennis Sep 25 '16 at 1:45
• @Dennis Fixed!! – Destructible Lemon Sep 25 '16 at 1:59
• @ConorO'Brien Submissions must terminate by default. – Dennis Sep 25 '16 at 3:42
• @Dennis oh ok then – Conor O'Brien Sep 25 '16 at 3:48
• I'm fairly sure I can golf some bytes, but the code is too.... ehhhh. It bugged out when I tried – Destructible Lemon Oct 30 '16 at 23:29

### Explanation

code is executed right-to-left

"I"$read0 0 reads STDIN, and then casts it to an integer {..} denotes an anonymous function with x as an implicit variable, applied to the integer til x returns a range 0..(x-1) 2_ drops 0 and 1, which are not needed for prime checking 1,x mod/: then takes mod of x with every element of the list and prepends a 1 to the list due to 1 and 2 returning empty list 0<min takes the minimum of the mods, and checks if it is bigger than zero. If it is, then it must be a prime! • Welcome to PPCG! – Martin Ender Mar 7 '18 at 22:24 # Whitespace, 145137 134 bytes [S S S N _Push_0][S N S _Duplicate][T N T T _Read_STDIN_as_integer_in_heap_0][T T T _Retrieve][S S S T S N _Push_2][T S S T _Subtract][N T T T T N _Jump_to_Label_FALSE_if_negative][S S S T N _Push_1][S N S _Duplicate_1][N S S N _Create_Label_LOOP][S N N _Discard_top_stack][S S S T N _Push_1][T S S S _Add][S N S _Duplicate][S N S _Duplicate][S S S N _Push_0][T T T _Retrieve_heap_at_0][T S S T _subtract][N T S T N _Jump_to_Label_TRUE_if_0][S S S N _Push_0][T T T _Retrieve_heap_0][S N T _Swap_top_two][T S T T _Modulo][S N S _Duplicate][N T S T T N _Jump_to_Label_FALSE_if_0][N S N N _Jump_to_Label_LOOP][N S S T N _Create_Label_TRUE][S S S T N _Push_1][T N S T _Output_1][N N N _Exit][N S S T T N _Create_Label_FALSE][S S S N _Push_0][T N S T _Output_0] Letters S (space), T (tab), and N (new-line) added as highlighting only. [..._some_action] added as explanation only. Outputs 1 if a prime, 0 otherwise. Try it online (with raw spaces, tabs, and new-lines only). General explanation: 1. Read input 2. Is it less than 2: Return 0 3. Integer i=1 4. Start loop • 5) Increase i by 1 • 6) If the input and i are equal: Return 1 (last iteration of the loop) • 7a) Is the input modulo i 0: Return 0 • 7b) Else: Go back to step 5 Example run (with 5 as input): Command Explanation Stack Heap STDIN STDOUT SSSN Push 0 [0] {} SNS Duplicate (0) [0,0] {} TNTT Read STDIN as number [0] {0:5} 5 TTT Retrieve heap at 0 [5] {0:5} SSSTSN Push 2 [5,2] {0:5} TSST Subtract (5-2) [3] {0:5} NTTTTN Jump to Label_FALSE if neg. [] {0:5} SSSTN Push 1 [1] {0:5} SNS Duplicate (1) [1,1] {0:5} NSSN Create Label_LOOP [1,1] {0:5} SNN Discard top [1] {0:5} SSSTN Push 1 [1,1] {0:5} TSSS Add (1+1) [2] {0:5} SNS Duplicate (2) [2,2] {0:5} SNS Duplicate (2) [2,2,2] {0:5} SSSN Push 0 [2,2,2,0] {0:5} TTT Retrieve heap at 0 [2,2,2,5] {0:5} TSST Subtract (2-5) [2,2,-3] {0:5} NTSTN Jump to LABEL_TRUE if 0 [2,2] {0:5} SSSN Push 0 [2,2,0] {0:5} TTT Retrieve heap at 0 [2,2,5] {0:5} SNT Swap top two (2,5] -> 5,2]) [2,5,2] {0:5} TSTT Modulo (5%2) [2,1] {0:5} SNS Duplicate (1) [2,1,1] {0:5} NTSTTN Jump to Label_FALSE if 0 [2,1] {0:5} NSNN Jump to Label_LOOP [2,1] {0:5} SNN Discard top [2] {0:5} SSSTN Push 1 [2,1] {0:5} TSSS Add (2+1) [3] {0:5} SNS Duplicate (3) [3,3] {0:5} SNS Duplicate (3) [3,3,3] {0:5} SSSN Push 0 [3,3,3,0] {0:5} TTT Retrieve heap at 0 [3,3,3,5] {0:5} TSST Subtract (3-5) [3,3,-2] {0:5} NTSTN Jump to LABEL_TRUE if 0 [3,3] {0:5} SSSN Push 0 [3,3,0] {0:5} TTT Retrieve heap at 0 [3,3,5] {0:5} SNT Swap top two (3,5] -> 5,3]) [3,5,3] {0:5} TSTT Modulo (5%3) [3,2] {0:5} SNS Duplicate (2) [3,2,2] {0:5} NTSTTN Jump to Label_FALSE if 0 [3,2] {0:5} NSNN Jump to Label_LOOP [3,2] {0:5} SNN Discard top [3] {0:5} SSSTN Push 1 [3,1] {0:5} TSSS Add (3+1) [4] {0:5} SNS Duplicate (4) [4,4] {0:5} SNS Duplicate (4) [4,4,4] {0:5} SSSN Push 0 [4,4,4,0] {0:5} TTT Retrieve heap at 0 [4,4,4,5] {0:5} TSST Subtract (4-5) [4,4,-1] {0:5} NTSTN Jump to LABEL_TRUE if 0 [4,4] {0:5} SSSN Push 0 [4,4,0] {0:5} TTT Retrieve heap at 0 [4,4,5] {0:5} SNT Swap top two (4,5] -> 5,4]) [4,5,4] {0:5} TSTT Modulo (5%4) [4,1] {0:5} SNS Duplicate (1) [4,1,1] {0:5} NTSTTN Jump to Label_FALSE if 0 [4,1] {0:5} NSNN Jump to Label_LOOP [4,1] {0:5} SNN Discard top [4] {0:5} SSSTN Push 1 [4,1] {0:5} TSSS Add (4+1) [5] {0:5} SNS Duplicate (5) [5,5] {0:5} SNS Duplicate (5) [5,5,5] {0:5} SSSN Push 0 [5,5,5,0] {0:5} TTT Retrieve heap at 0 [5,5,5,5] {0:5} TSST Subtract (5-5) [5,5,0] {0:5} NTSTN Jump to LABEL_TRUE if 0 [5,5] {0:5} NSSTN Create Label_TRUE [5,5] {0:5} SSSTN Push 1 [5,5,1] {0:5} TNST Output top as number [5,5] {0:5} 1 NNN Stop program [5,5] {0:5} # APL, 9 chars/bytes 2≡≢∪∨∘⍳⍨⎕ get the input compute least common divisor between n and all integers from 1 to n ∨∘⍳⍨ count of unique values ≢∪ if it's exactly 2, then it's prime 2≡ # GolfScript, 15 bytes ~:z,{)z\%!},,2= This uses trial division: • stores the input in variable z • computes the remainder of dividing z by all numbers from 1 to z • expects to find a remainder of 0 exactly 2 times Try it here. # Ruby, 21 + 1 = 22 19 + 1 = 20 bytes Also throwing my hat into the Ruby battle using the regex approach (and improved using histocrat's suggestion): p !/^(11+)\1+$|^1$/ Takes input as a unary string and invoked using the n flag:$ ruby -ne 'p !/^(11+)\1+$|^1$/' <<< 11111
true
• Ooh, you can drop two in fact. p !/^(11+)\1+$|^1$/ – histocrat Sep 11 '15 at 18:25
• @histocrat Interesting. I didn't know about that. However, it gives me warning: regex literal in condition. Since the rules state "if possible, output should consist solely of the string representation of a truthy or falsy value," I'd need to add the W0 flag, so it's a wash. Thanks for the tip, though. – Reinstate Monica -- notmaynard Sep 11 '15 at 18:52
• @histocrat A-ha, it only gives that warning when I run it from a file rather than as a one-liner. So thank you indeed for that. – Reinstate Monica -- notmaynard Sep 11 '15 at 20:45

# Python 2, 466552 51 bytes

1. Went up to 65 bytes - Fix made thanks to feersum & Mauris
2. Went down to 52 bytes - Suggestions made by kirbyfan64sos and accepts in input from STDIN to complete the code.
3. Went down to 51 bytes - Suggestion made by kirbyfan64sos (thanks again!) to remove the space between 1 and and. Apparently if you have a letter that follows a number, a space isn't needed... how weird, but cool!

This finds the remainder / modulus of the input integer n divided by every number from 2 up to n-1. If there is at least one number in this sequence that has no remainder, or results in 0, this means that the number is not prime. If every value in this sequence is non-zero, the value is prime. Also by definition, 1 isn't prime and so that has to be taken care of separately.

n=input();print n!=1and all(n%i for i in range(2,n))

# Example Runs

I ran this in IPython:

In [10]: n=input();print n!=1and all(n%i for i in range(2,n))
1
False

In [11]: n=input();print n!=1and all(n%i for i in range(2,n))
2
True

In [12]: n=input();print n!=1and all(n%i for i in range(2,n))
3
True

In [13]: n=input();print n!=1and all(n%i for i in range(2,n))
4
False

In [14]: n=input();print n!=1and all(n%i for i in range(2,n))
5
True

In [15]: n=input();print n!=1and all(n%i for i in range(2,n))
6
False

In [16]: n=input();print n!=1and all(n%i for i in range(2,n))
7
True

In [17]: n=input();print n!=1and all(n%i for i in range(2,n))
10
False

In [18]: n=input();print n!=1and all(n%i for i in range(2,n))
15
False

In [19]: n=input();print n!=1and all(n%i for i in range(2,n))
17
True

In [20]: n=input();print n!=1and all(n%i for i in range(2,n))
20
False

In [21]: n=input();print n!=1and all(n%i for i in range(2,n))
30
False
• It has to return false for 1. – feersum Sep 12 '15 at 0:40
• You made it return False for every possible input but 1, which should be False :) – Lynn Sep 12 '15 at 1:05
• @Mauris - Oops. I didn't fix that properly lol. Was on mobile. I'm on my computer now. Fixing. – rayryeng Sep 12 '15 at 1:07
• @Mauris - Fixed now. Thanks. – rayryeng Sep 12 '15 at 1:12
• Wow, this is almost the exact same code I wrote :) You can save a char by using > instead of !=. – J Atkin Sep 21 '15 at 15:14

# Fortran 90, 208 bytes

program a
integer::n,i
logical::p
if(n==2) then
p=.true.
else if(n<2 .or. mod(n,2)<1) then
p=.false.
else
p=.true.
do i=3,n-1,2
if(mod(n,i)<1) then
p=.false.
exit
endif
enddo
endif
write(*,*)p
end

This uses trial division. Not a whole lot has been golfed here beyond removing spaces. Here it is with spaces for readability:

program primes
integer :: n, i
logical :: p

if (n == 2) then
p = .true.
else if (n < 2 .or. mod(n, 2) == 0) then
p = .false.
else
p = .true.
do i = 3, n-1, 2
if (mod(n, i) == 0) then
p = .false.
exit
endif
enddo
endif

! Write a logical to STDOUT
write (*,*) p
end program
• Surely need a space before then? – Erik the Outgolfer Jul 17 '16 at 15:49
• @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Unfortunately yes. – Alex A. Jul 17 '16 at 16:13

# Bash+coreutils, 29 bytes

echo $[factor$1|wc -w==2]

Test:

echo 'echo $[factor$1|wc -w`==2]' > primetest.sh
chmod +x primetest.sh
./primetest.sh <NUMBER_TO_TEST>

# APL, 13 bytes

2=0+.=X|⍨⍳X←⎕

Inefficient, but it works. A number is a prime if it is only evenly divisible by 1 and itself, so it just tests all of these. Output is 0 or 1.

Explanation:

X←⎕  ⍝ read a number, store it in X
X|⍨⍳      ⍝ X mod [1..X]
0+.=          ⍝ count the 0s
2=              ⍝ are there 2?

# Lua, 71 67 bytes

n=io.read"*n"for i=2,n-1 do if n%i==0 then r=1 end end print(not r)

Ungolfed:

for i=2,n-1 do
if n%i==0 then
r=1
end
end
print(not r)

This program just uses trial division to find if a number is prime or not.

3 bytes saved thanks to @Ruth Franklin

• You can save a couple of bytes by using r=1 instead of r=true (as not 1 is false anyway) – Ruth Franklin Sep 13 '15 at 13:24
• Ah okay, thanks for the tip :) – Nikolai97 Sep 13 '15 at 17:15
• Inputs less than 2 (1, 0, and negative numbers) all return true. – ECS Jan 25 '16 at 8:33

# Perl, 38 or 47 bytes

use ntheory":all";say is_prime(shift);

Prints 0 if composite, 2 if definitely prime, 1 if a probable prime. The results for all 64-bit inputs are deterministic. With 0.53+ this extends to 82-bit inputs. It's also sometimes done for up to 200-bit inputs (special form or very easy proof). The probable prime test is an extra-strong BPSW test followed by 1-5 random-base Miller-Rabin tests.

use ntheory":all";say is_provable_prime(shift);

Uses BLS75-T5 or ECPP to prove the result. Deterministic for all inputs. Very fast to ~500 digits, works pretty well to 1000 or so digits.

This is included in Strawberry Perl for Windows. Certainly using a module is iffy under the golfing loopholes, but this is a normal module and Perl is all about CPAN. It's also ridiculously faster and more useful than the clever but stupid regex.

• What does "probably prime" mean? – ASCIIThenANSI Sep 11 '15 at 19:02
• It means it passed some probabilistic prime test that, very rarely, might give a false positive, and you may optionally want to run a more thorough test. – Lynn Sep 11 '15 at 19:11
• For ntheory, it means it passed an ES BPSW test (that has no counterexamples found in the 35 years since it was introduced) plus one or more extra random-base Miller-Rabin tests. I just added the new result for deterministic M-R testing out to ~82 bits. A bit stronger than Mathematica's PrimeQ function. Primality proofs can be done, but very few people care vs. good probable prime tests. Arguably the chance of failure is smaller than a software or hardware error in the proof code. Not to mention most people want the result for a 2000 digit number in 0.1 seconds instead of 1,5 hours. – DanaJ Sep 12 '15 at 5:05
• The challenge explicitly asks for non-probabilistic solutions. – Martin Ender Sep 14 '15 at 10:19
• @MartinBüttner Adjusted text and also asked the challenge to be more specific about what "deterministic" means. Thanks. – DanaJ Sep 14 '15 at 11:56