# 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

• 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/… Dec 12, 2017 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. Dec 12, 2017 at 12:51
• Could a case be made for locking this challenge and posting a new, less restrictive one? Jun 25, 2018 at 12:59
• @Shaggy Seems like a question for meta. Jun 25, 2018 at 13:44
• Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. Jun 25, 2018 at 13:45

# Ruby, 16 + 6 = 22 bytes

[*$<];p$..prime?

or equivalently

p$<.count.prime? Rules abuse! Kind of, anyway. This answer requires that the input be in unary, and that the character used for input be a newline. Invoke like ruby -rprime prime_test.rb input Where input is a file containing n newlines. I calculate this at 22 bytes: 6 for "rprime" and 16 for the code. However, I also calculate manatwork's answer at 22 bytes if you golf the command line invocation (7 for 'nrprime' and 15 for the code). • Are you sure that Ruby's prime? doesn't use a probabilistic test? Sep 14, 2015 at 10:23 • Yes, it loops through a pseudoprime generator (which returns a superset of the primes) and checks for divisibility of each number less than it. Sep 14, 2015 at 12:07 # O, 23 bytes j.1>\J2/{Jn%0={0}{}?}dp Take 2! This one uses trial by division. # awk, 30 25 24 bytes "factor "$0|getline~--NF

Prints the number followed by a colon if it's is prime, prints nothing if it's not.

I check for NF, because the output line from factor has exactly two fields if the input number is prime. The pipe command changes $0, and returns 1 on successful execution. So if NF-1=1 I know we had a prime. You can use the ~ operator to compare two numbers, if you know that the second number would always be equal or greater. Example usage: echo 12347 | awk '"factor "$0|getline~--NF'

My previous idea didn't involve using system commands and is 29 bytes long:

{for(++d;$0%++d&&$0>1;);}d~$0 Prints the number if it's prime and nothing if it's not. Example usage: echo 12347 | awk '{for(++d;$0%++d&&$0>1;);}d~$0'
• And not only because I touched the ZX81 too: if you should have only 2 fields, it has not to be the 3rd. awk '"factor "$0|getline~!$3', one character less, but it answers prime number for 1 too (that it should be excluded), so I don't know if useful. Jul 19, 2016 at 17:53

# C, 61 bytes

r;main(i,j){r=(--i>1);for(j=i-1;j>1;)r*=!!(i%j--);return r;}

Uses unary representation - the number is encoded in the number of commandline arguments. The return value is initialized to 1 and then, it's multiplied by the sign of remainder of division of the tested number and numbers 2..i-1 in a loop. So it will be zeroed when any non-trivial divisor found.

The result is returned to the system as the exit code.

Test:

echo 'r;main(i,j){r=(--i>1);for(j=i-1;j>1;)r*=!!(i%j--);return r;}' > main.c
gcc -o main main.c
./main 1 ; echo $? ./main 1 1 ; echo$?
./main 1 1 1 ; echo $? ./main 1 1 1 1 ; echo$?
./main 1 1 1 1 1 ; echo $? ./main 1 1 1 1 1 1 ; echo$?
./main 1 1 1 1 1 1 1 ; echo $? ./main 1 1 1 1 1 1 1 1 ; echo$?
./main 1 1 1 1 1 1 1 1 1 ; echo $? ./main 1 1 1 1 1 1 1 1 1 1 ; echo$?

$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;
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;
float: left;
margin-right: 25px;
cursor: pointer;
}
.option {
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] {
background: #cc7801;
color: #fff;
}
#stdout-container, #stdin-container {
height: auto;
}
#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;
}
.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. Nov 7, 2015 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)
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.

((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... Dec 21, 2015 at 20:25 • This solution is valid for wikis that allow at least a recursive depth of 253. Dec 21, 2015 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? Oct 21, 2015 at 21:19 • @mathmandan: Yeah, there were 2 bugs. I'll fix them, but the block count will be the same. – user46167 Oct 21, 2015 at 22:54 • This seems to loop forever for input 1. Oct 22, 2015 at 1:46 • @Dennis: Noted. Will fix with 5 more blocks – user46167 Oct 22, 2015 at 18:55 • As before: Scratch is typically scored by the number of bytes in the corresponding scratchblocks code here. Oct 29, 2015 at 1:09 ## CASIO-BASIC, 28 bytes ?->A:For 2->B To A:A Rmdr B=0=>B->A:Next This prompts for a number, then outputs the number if it is prime, else zero. I'm not really sure how this works. I originally thought it would output the value from the last assignment (stored in Ans), but then it would output the lowest factor of the number, not zero. Note: -> and => are ASCII representations of one symbol each (the assign-to and conditional operators). The size was calculated as the size of this program (60 bytes) minus the size of an empty program (32 bytes). # JavaScript (ES6), 54 bytes for((x=prompt(a=i=1))>1||a--;++i<x;x%i?0:a=0);alert(a) 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. Sep 25, 2016 at 1:45 • @Dennis Fixed!! Sep 25, 2016 at 1:59 • @ConorO'Brien Submissions must terminate by default. Sep 25, 2016 at 3:42 • @Dennis oh ok then Sep 25, 2016 at 3:48 • I'm fairly sure I can golf some bytes, but the code is too.... ehhhh. It bugged out when I tried Oct 30, 2016 at 23:29 ## Haskell, 47 52 bytes main=do n<-readLn;printn>1&&all((>0).mod n)[2..n-1]

EDIT: I had failed to take 1 into account. Fixed!

• Welcome to ppcg! Nice first post! Congrats on out-golfing the other existing haskell answers! Feb 6, 2017 at 15:40
• This code returns True for 1 which is not valid according to the specification. Feb 19, 2017 at 11:42

## Samau, 2 bytes

▌τ

Hex dump:

dd ab

Yes, it's 2 bytes. Samau uses CP737 as its default character encoding.

τ      test if it is a prime

τ uses the isCertifiedPrime function in the haskell package arithmoi. It's not a probabilistic algorithm.

There's also a 7-bytes answer if built-ins are not allowed:

▌;\│Σ2=

Hex dump:

dd 3b 5c b3 91 32 3d

Most mathematical functions in Samau automatically thread over lists.

▌           read a number, let's call it n
;          duplicate
\         range from 1 to n
|        return 1 for divisors of n, and 0 for the other numbers
Σ       take the sum
=2     if the sum is 2, then it's a prime

## Alice, 12 11 bytes

/o|\ntdc
@i

Try it online!

Prints 1 for primes and 0 for composite numbers and 1. Here is an alternative solution that prints p-1 for primes instead:

/o|\tzt.
@i

Try it online!

### Explanation

/   Send the IP southeast, switching to Ordinal mode.
i   Read all input as a string.
|   Reflect the IP back where it came from.
i   Try reading input again, but this just pushes "".
/   Send the IP west, switching back to Cardinal mode.
The IP wraps around to the end of the line.
c   Convert the input to an integer and push its prime factors. Pushes nothing
at all for input 1.
d   Get the stack depth. This is 1 iff the input is a prime.
t   Decrement to give 0 for primes.
n   Logical NOT. Now we have 1 for primes, 0 otherwise.
\   Send the IP southwest, switching to Ordinal mode.
o   Print the result as a string.
@   Terminate the program.

# q, 35 34 bytes

Haven't golfed much yet, but we can drop 2 bytes easily if we're allowed to return nothing for 1 and 2. Really, the language truly shines in code golf where the seemingly golfed code is just idiomatic q. Using q instead of k lets us use min, mod and til operators to save some bytes.

Having to read STDIN isn't much idiomatic q, and costed us 11 bytes.

-> I was able to save a byte due to on-the-fly assignments which I forgot about

0>min 1,x mod/:2_til x:"I"$read0 0 ### 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! Mar 7, 2018 at 22:24