# Is this number a prime?

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.

Rosetta code features lists by language of idiomatic approaches to primality testing, one using the Miller-Rabin test specifically and another using trial division. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!" and Golf you a quine for great good!.

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

Write a full program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.

### Input

• If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).

• If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.

In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

For scoring purposes, submit the program that corresponds to the input 1.

### Output

Output has to be written to STDOUT or closest alternative.

If possible, output should consist solely of a truthy or falsy value (or a string representation thereof), optionally followed by a single newline.

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

• This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

• Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

The language Piet, for example, will be scored in codels, which is the natural choice for this language.

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

• Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

• If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

• Built-in functions for testing primality are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

• Unless they have been overruled earlier, all standard rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

### Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

## Language Name, N bytes


where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes


If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes


You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes


<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 57617; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

• 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
• Could a case be made for locking this challenge and posting a new, less restrictive one? – Shaggy Jun 25 '18 at 12:59
• @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

## Fortran 90, 66 55 bytes

Using trial division.

read*,i
do1 j=2,i
1 if(mod(i,j)==0)exit
print*,i==j
end


Saved 11 bytes thanks to sigma.

A do loop with labelled statement (not an enddo or continue) is still valid in Fortran 90, but obsolete.

Alternative using Wilson's theorem (56 bytes):

read*,j
k=1
do1 i=2,j-1
1 k=mod(k*i,j)
print*,k==j-1
end

• Aww you beat me, now I'll have to come up with a different Fortran solution! Some tips though: the program statement is not necessary, which will save you 9 bytes, and you can also get away with writing do1 instead of do 1. – sigma Sep 13 '15 at 20:43

# Smalltalk, 47 characters

Obviously no competition for isPrime if the Smalltalk dialect has it, but not all do. For example, the one used in Coding Ground (GNU Smalltalk v3.2.5) does not have it.

I'm relying on the observation that GCD((n - 1)!, n) = 1 for prime n which I haven't seen used very often. Ridiculously bad algorithm, but Smalltalk has no problem working with large integers. Replace the 2 with whatever you want to test:

|n|n:=2.((n>1)&((n-1)factorial gcd:n)=1)inspect


It does not consider 1 as prime as required by the OP. However, one widely accepted definition of a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. So by this definition, 1 shouldn't be a candidate for primality testing, any more than 0, ½, i, e or π should be.

Note that in some situations, -1 is considered prime, because -1 = 1 × -1, and is used as such in some factorization algorithms.

## J, 4 bytes

1&p:


This is essentially a built-in function for J as p: provides several different prime-related functions, depending on the left argument (attached here with 1&).

As with J in general, it is incredibly array-friendly:

   1&p: 0 1 2 3 4 5 6 7 8 9 10
0 0 1 1 0 1 0 1 0 0 0


# 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

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. – 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≡  # Arn, 13 12 10 7 bytes “sƥNm(┤  Previous versions: ï_C3<│ì♦3(  ├¦&┼6k┐ÇŠq""  {•Õ╝_¸”b¦¤º!E  Try it! # Explained Unpacked: !(1+fact-1)%. I may add a builtin for checking primality, but until then I made use of Wilson's Theorem; that is, $$((n - 1)! + 1)\mod n\equiv 0$$ will yield true iff n is a prime number. ! Boolean Not ( Begin expression 1 Literal one + Addition fact factorial function _ Variable initialized to STDIN; implied - Subtraction 1 Literal one ) End expression % Modulo _ Implied  Thank goodness I finally fixed operator precedence. • Finally! You proved that Arn is a programming language. – user96495 Aug 24 '20 at 1:44 • Idea: Add stuff that translates to (( or (((. – user96495 Aug 24 '20 at 1:46 • I do plan on adding a lot more builtins the future, so for the sake of more space I probably won't do anything like that (at least for now). That is a good idea though, Arn's opinionated fix chaining can be very annoying at times :p – ZippyMagician Aug 24 '20 at 1:50 • Unfortunately that would evaluate to <s>!(( _.fact / (_ + 1)) % _</s>!((_.(fact / _) + 1) % _). curse you fix chains! – ZippyMagician Aug 24 '20 at 1:54 • Although, that did reveal another bug in my interpreter (naturally). Guess it's time to fix it! – ZippyMagician Aug 24 '20 at 1:55 # ARM Thumb, no div instructions, 43 bytes f7ff fffe represents placeholders for libc calls, to scanf and printf respectively. b503 4669 a008 f7ff fffe bc03 2802 d907 2202 0001 1a89 d003 d8fc 3201 4282 d1f8 a001 f7ff fffe bd00 6425 00  Assembly code:  .globl main .thumb .thumb_func main: push {r0, r1, lr} mov r1, sp adr r0, printf_scanf_str bl scanf pop {r0, r1} cmp r0, #2 bls .Ltrue movs r2, #2 .Lloop1: movs r1, r0 .Ldivloop: subs r1, r2 beq .Lfalse bhi .Ldivloop .Ldivloop_end: adds r2, #1 cmp r2, r0 bne .Lloop1 .Ltrue: @ movs r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value .Lfalse: adr r0, printf_scanf_str bl printf pop {pc} printf_scanf_str: .asciz "%d"  Accepts a number from stdin, and prints nonzero if it is a prime, or zero if it isn't. ### Walkthrough Behold, a prime searcher that is so slow you'd swear it was Python. It is a brute force modulo check using a subtraction loop with zero shortcuts. Here, we use a trick with push to make space for the scanf output and save the link register. push will subtract from sp and store the registers in ascending order in memory. So for example, push {r0, r1, lr} will end up like this: | sp + 0 | sp + 4 | sp + 8 | | argc | argv | return |  We don't actually care about argc - we care about the space on sp. We can then just pass the stack pointer directly to scanf. We do sorta care about argv. Not about what it points to, but that it is a valid (non-zero) pointer. scanf("%d", &r0) main: push {r0, r1, lr} mov r1, sp adr r0, printf_scanf_str bl scanf  Then, we can pop the result from scanf we stored into r0, and argv into r1 as a "non-zero" value.  pop {r0, r1}  Immediately return true for values <= 2. This is exactly why we pushed and popped r1.  cmp r0, #2 bls .Ltrue  Begin factorizing against 2.  movs r2, #2  Use a subtraction loop on a copy of r0 to check if r0 % r2 == 0. Specifically, the subs will reach zero on an even multiple and set the zero flag (which corresponds to the eq condition). Otherwise, we loop until it underflows (not hi) .Lloop1: movs r1, r0 .Ldivloop: subs r1, r2 beq .Lfalse bhi .Ldivloop  Increment the number we factor against and loop if it is not equal to r0. .Ldivloop_end: adds r2, #1 cmp r2, r0 bne .Lloop1  Optionally, with the true condition, we set r1 to 1 if it is a prime. But non-zero is "truthy" enough for us even if it is a little ugly. It will either be the last inverted modulo we tested, or the address of argv, all of which will be non-zero. Due to how our subtraction loop works, by the time we jump to .Lfalse, r1 will already be zero. .Ltrue: @ movs r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value .Lfalse:  r1 is already conveniently (and intentionally) in the right place to forward directly to printf, and all we need to do is reload the printf/scanf string to r0 (no easy way around this) and call printf. Note that due to how pop works in Thumb, it isn't really that useful to do tail calls because we cannot pop directly into lr without a wide instruction. printf("%d", r1)  adr r0, printf_scanf_str bl printf  Last, pop the return address from lr we pushed earlier directly into the program counter to return from main.  pop {pc}  # Java, 108 bytes interface P{static void main(String[]a){long l=new Long(a[0]),i=1;for(;0<l%++i%l;);System.out.print(l==i);}}  Try it online! Port of my Ink answer. Would beat all existing answers in C#, Python (2 and 3), and possibly other languages if ported. # Ungolfed interface PrimeChecker { // Unlike members of classes, members of interfaces are public by default. static void main(String[] args) { long input = new Long(args[0]), div = 1; for (; 0 < ( input % (++div) // Trial division, finish when div divides input % input /* If input is at least 2, this has no effect. But (1 % n) = 1 for any n > 1 so without this, the loop would never end when the input is 1 */ ); ) { /* The loop body is empty, we're just using it to set div */ } // div is now the lowest number greater than 1 that divides the input // (or 2, if the input is 1) // The input is prime iff that number is equal to the input System.out.println(input == div); } }  • Note for those who, like me, didn't understand the existence of the last %l at first, it's to shortcut the loop when the input is 1. – Olivier Grégoire May 16 '19 at 15:42 ## JavaScript (ES6), 42 41 bytes !/^(.|(.+.)\2+)$/.test(Array(-~prompt()))


Based off of this regex solution. Array(+prompt()+1) creates a string of commas from the input, and it is simply passed through the (slightly edited) aforementioned solution. Array(+prompt()+1) can be replaced with 10**prompt()/9|0, but that seems to fail for numbers greater than 10.

• Nice! Array(-~prompt()) is a full 3 bytes shorter than 'x'.repeat(prompt()). Did you come up with this? – Deadcode Apr 11 at 8:20
• Well I see it was used before. – Deadcode Apr 11 at 8:59
• @Deadcode I came up with it myself but I did not doubt that someone had done it before – CubeyTheCube Apr 16 at 2:21

# Taxi, 1238 bytes

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Cyclone.Pickup a passenger going to The Underground.Go to The Underground:n 2 r 2 r.Switch to plan q i.[l]Pickup a passenger going to Cyclone.Go to Zoom Zoom:n 3 l 2 r.Go to Cyclone:w.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Divide and Conquer.Go to Sunny Skies Park:n 1 r.Go to Divide and Conquer:n 1 r 1 r 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:e 1 l 1 l 2 l.Pickup a passenger going to The Underground.Pickup a passenger going to Equal's Corner.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Switch to plan c i.Go to The Underground:n 3 r 1 r 2 l.Switch to plan p i.[q]0 is waiting at Writer's Depot.[p]1 is waiting at Writer's Depot.Go to Writer's Depot:n 3 l 2 l.Pickup a passenger going to Post Office.Go to Post Office:n 1 r 2 r 1 l.[c]Go to Sunny Skies Park:n.Pickup a passenger going to Cyclone.Go to The Underground:n 1 r 1 r 2 r.Switch to plan l.


Try it online!

With many ideas from this answer, but 1 character shorter using the same shortening techniques.note This takes a slightly different approach so that “The Underground” is the return point for each iteration instead of “Zoom Zoom”. Even though this ends up only 1 character shorter, it's actually one whole instruction shorter! The reduction is relatively little because there's 2 more turns and “The Underground” is mentioned more.

• Removing all quotes around plans and strings. As long as there is no space or other special character they are not needed.
• For the Switch to plan "name" if no one is waiting the only check is whether there is any text after "name". This means that the  if no one is waiting part can be replaced with  i.
• If we did use quotes like the original answer we could also remove the spaces after closing quotes.

This is the code ungolfed with some comments.

    [Read number and convert to int]
Go to Post Office: west 1st left, 1st right, 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left, 1st right.

[Duplicate to get numerator and denominator]
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left, 1st left, 2nd right.

[Decrement denominator and duplicate both]
Pickup a passenger going to Cyclone.
Pickup a passenger going to The Underground.
Go to The Underground: north 2nd right, 2nd right.
Switch to plan "not prime" if no one is waiting.
[loop]
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north 3rd left, 2nd right.
Go to Cyclone: west.

[Pickup for division...]
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Divide and Conquer.
Go to Sunny Skies Park: north 1st right.
Go to Divide and Conquer: north 1st right, 1st right, 2nd right, 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: east 1st left, 1st left, 2nd left.

[Copy result to check if integer, first pickup ]
Pickup a passenger going to The Underground.
Pickup a passenger going to Equal's Corner.
Pickup a passenger going to Trunkers.
Go to Trunkers: south 1st left.
Pickup a passenger going to Equal's Corner.

[Check if integer]
Go to Equal's Corner: west 1st left.
Switch to plan "continue" if no one is waiting.
Go to The Underground: north 3rd right, 1st right, 2nd left.
Switch to plan "prime" if no one is waiting.

[Print whether it's a prime or not]
[not prime]
0 is waiting at the Writer's Depot.
[prime]
1 is waiting at the Writer's Depot.
Go to Writer's Depot: north 3rd left, 2nd left.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st right, 2nd right, 1st left.

[Pickup numerator and decrement denominator for checking lower numbers]
[continue]
Go to Sunny Skies Park: north.
Pickup a passenger going to Cyclone.
Go to The Underground: north 1st right, 1st right, 2nd right.
Switch to plan "loop".
`

Try it online!