# 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, language: match, 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/… 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

# Java, 108 bytes

interface P{static void main(String[]a){long l=new Long(a),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),
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. May 16, 2019 at 15:42

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

# Vyxal, 3 bytes

KḢ₃


Try it Online!

I thought something non trivial would be nice for a change. æ does the job for one byte but where's the fun in that?

-1 thanks to EmanresuA

## Explained

KḢ₃
KḢ   # factors(input)[1:]
₃  # len(^) == 1 // prime numbers have only [1, n] as factors...other numbers have 1 or 3+ factors

• This can be KḢ₃ Nov 1, 2021 at 8:57
• Also, 5 bytes version with no factorisation - 4 with r if you remove the $ Nov 1, 2021 at 9:03 # Nibbles, 4 bytes %^*<<,  Uses Wilson's theorem, which states that an integer $$\ n \$$ $$\ (n > 1) \$$ is prime iff $$\ (n-1)! + 1 \$$ is divisible by $$\ n \$$. To capitalize on Nibbles' implicit args feature, I slightly modified the formula to check for $$\ (n - 1)!^n \bmod n > 0 \$$, which also nicely handles the $$\ n = 1 \$$ edge case. In Nibbles, an integer is Truthy if it is positive, and Falsy otherwise. Under this definition, checking whether the modulus is positive isn't necessary. ### Ungolfed % # Modulo of ^ # power of * # product of <<, # [1..n-1] (implicit$)
#   n (implicit $) # n (implicit$)


## <>^v, 184 bytes

Prints 1 if number is prime, otherwise 0.

>]v2i>IT%0=vIT[vv
> vv
1          I   TI
T          T    )
T          =    i
t          > ^  v
,    ^          <
v
>"1";
>        >"0";
^@|


#### Explanation

@  Pointer starts here, goes right
|  Mirror — reverse pointer direction
@  No-op because the program is already running
^  Send instruction pointer up
,  Read number from stdin and push to stack
t  Pop and store in variable t
T  Push value of variable t
T  Same
1  Push 1
>  Send instruction pointer right
]  If top element of stack is greater or equal to the second element of the stack
v  Send instruction pointer down
>  Send instruction pointer right
Go to [not prime]
Else
2  Push 2
i  Pop and store into variable i
[loop start]
>  Send instruction pointer right
I  Push value of variable i
T  Push value of variable t
%  Set top of stack to top of stack modulo second element of stack
0  Push 0
=  If the top two elements of the stack are equal
v  Send instruction pointer down
I  Push value of variable i
T  Push value of variable t
=  If the top two elements of the stack are equal
>  Send instruction pointer right
^  Send instruction pointer up
>  Send instruction pointer right
Go to [prime]
Else
[not prime]
>  Send instruction pointer right
"0"  Push "0"
;  Print top of stack
';' was the last character of this row, program exits
Else
I  Push value of variable i
T  Push value of variable t
If the first element of the stack (t) is smaller or equal to the second element of the stack (i)
v  Send instruction pointer down
[prime]
v  Send instruction pointer down
T  Push value of T
v  Send instruction pointer down (there only to ensure the row is long enough)
>  Send instruction pointer right
"1"  Push "1"
;  Print top of stack
Since ';' was the last character of the row, exit
v  Send instruction pointer down
v  Idem
I  Push value of variable i
)  Increment top of stack
i  Pop stack and store in variable i
v  Send instruction pointer down
<  Send instruction pointer left
^  Send instruction pointer up
Go to [loop start]


More simply, it first checks if the number is lower or equal to 1. If so, it prints 0 and exits. Then, it sets the variable i (current divisor) to 2. Then the program enters a loop. In that loop:

• If the number modulo i is 0:
• If i == number, print 1 and exit (prime). Else, print 0 and exit (has found a divisor, number isn't prime).
• Then it increments i, and goes back to the beginning of the loop.

run online

# Cubestack, 98 bytes

M R2 M' b' M R M' r M R' M' U2 S S' y b' M R M' r S S' y2 U M R M' D x M R M' b f2 x' y' M R' M' b


Try it Online!

Brief explanation:

M R2 M' b' M R M' r M R' M' U2 S S'  # Set up the for loop
M R2 M'                              # Push 2 to the stack
b'                           # Get all inputs wrapped in a list
M R M' r                  # Get the first item of the list pushed
M R' M'          # Push 1 to the stack
U2       # Range (start, end, step)
S S'  # Push an empty string (the loop variable)

y b' M R M' r S S' y2 U M R M' D  # Check if n is divisible the loop variable
y                                 # Open a for loop
b' M R M' r                     # Get the first (and only) input
S S' y2             # Get the value of the loop variable
U           # Perform modulo operation on the top two items
M R M' D  # Check if the top item equals 0

x M R M' b f2 x' y'  # If n is divisible be the loop variable, print 0 and exit
x                    # Open an if statement (code runs if top item is truthy)
M R M'             # Push 0 to the stack
b           # Print
f2        # Exit program
x'     # Finish if statement
y'  # End for loop

M R' M' b  # Provided that the program didn't exit in the loop, print 1


=mod(fact(A1-1),A1)=mod(-1,A1


Try it on my Google Sheet It uses Wilson’s theorem, which, in modular arithmetic, is:

(n − 1)! ≡ −1 (mod n)


read: n − 1 factorial is congruent modulo n to negative 1

However, it is important to maintain the distinction between (mod n) notation and and the modulo operator. We could rewrite Wilson’s theorem using more familiar mod operators:

(n − 1)! % n = -1 % n


and that’s what i wrote into google sheets. Google Sheets also does parenthesis autocompletion, so i omitted the final parentheses.

Although there are several other answers that use a regex, none of them discuss the history of matching primes in this way, or show alternative regexes that match primes, or examine the range of compatibility of the regex with various engines. So that is what this post is all about.

All of the answers shown here take their input in bijective unary, as a string of x characters whose length represents the number. Output is in the form of "match" (prime) or "no match" (non-prime).

First, the shortest form:

^(?!(xx+)\1+$)  There does not exist any $$\q \ge 2\$$ that divides $$\n\$$ with a quotient of $$\2\$$ or greater. Try it online! This is the standard, well-known primality test for numbers expressed in unary. I first became aware of it when arriving upon this 14 byte form independently in the course of solving one of the levels of Regex Golf on 2014-02-12 (which kick-started my interest in regex code golf). But in there, the set of test cases only started at $$\2\$$ (xx), thus glossing over the fact that this regex matches the non-primes $$\0\$$ and $$\1\$$. I later learned that this regex dates back to at least as early as a 1997-10-22 Perl post by Abigail, which then began being discussed on the next day, extending to the next two pages. The first appearance of a regex primality test on CGCC was a 2012-01-16 answer by ChristopheD to "Finding Not-Quite-Prime Numbers". # Regex (ECMAScript or better), 16 bytes ^(?!(xx+)\1+$)xx


There does not exist any $$\q \ge 2\$$ that divides $$\n\$$ with a quotient of $$\2\$$ or greater, and $$\n \ge 2\$$.

Try it online!

## Regex (ECMAScript or better), 18 bytes

(?=(x(x*))\1+$)\2^  The largest $$\q \ge 1\$$ that divides $$\n\$$ with a quotient of $$\2\$$ or greater exists, and $$\q-1=0\$$. Try it online! This was arrived at first by Grimmy on 2019-04-21. I independently came up with it on 2021-03-06, basing it on my earlier finding of ^(?>(x(x*))\1+$)\2 (below).

There may be circumstances in which this could be useful in the context of a larger regex. For example, if the very first thing a regex needs to do is assert that the input is prime, without consuming any characters, this would be 2 bytes shorter than ^(?=(?!(xx+)\1+$)xx). ## Regex (Perl / Java / Boost / Python / Ruby / PCRE / .NET), 18 bytes ^(?>(x(x*))\1+$)\2


The largest $$\q \ge 1\$$ that divides $$\n\$$ with a quotient of $$\2\$$ or greater exists, and $$\q-1=0\$$.

Try it online! - PCRE

I came up with this on 2018-12-07. It could conceivably be useful within the context of a larger regex. It consumes the entire prime number, like ^(?=(xx+?)\1*$)\1$, but its captures seem less likely to be useful; they are just \1=$$\1\$$ and \2=$$\0\$$. However, there may be niche circumstances where this could be coupled with NPCG (non-participating capture group) behavior, such that \1 or \2 matches if the path including the primality expression was crossed, but doesn't match otherwise. This would be equal in length to ^(?!(xx+)\1+$)xx() but capture two potentially useful optionally-unset groups instead of just one. # Regex (Tcl ARE), 16 bytes ^((x(x*))\2+$)\3


Try it online!

Tcl ARE has both positive and negative lookaheads, but neither backreferences nor captures can be done inside one. So seemingly, it would be impossible to match primes instead of non-primes.

But as it so happens, in some contexts, wrapping an expression in a capture group apparently makes it atomic (prevents the engine from doing the equivalent of backtracking into that expression if the pattern fails to match at a later point). Exactly what kind of context this requires, I have not yet determined.

This regex is based on the 18 byte PCRE regex above. Both capture groups are shifted forward by 1, so \2 is $$\q\$$ and \3 is $$\q-1\$$.

# $$\\large{\text{Inverted logic}}\$$

In the following answers, "no match" indicates a prime, and a match indicates a non-prime.

## Regex (GNU ERE or better), 14 bytes

^(xx+)\1+$|^x$


Try it online! - GNU ERE (very slow)
Try it online! - Tcl ARE
Try it online! - ECMAScript

There does not exist any $$\q \ge 2\$$ that divides $$\n\$$ with a quotient of $$\2\$$ or greater, and $$\n \ne 1\$$.

Gives a false positive for $$\n=0\$$. As explained below, this cannot be avoided.

Alternative form:

^((xx+)\2+|x)$ # Regex (Tcl ARE or better), 15 bytes ^(xx+)\1+$|^x?$ Try it online! - Tcl ARE Try it online! - ECMAScript There does not exist any $$\q \ge 2\$$ that divides $$\n\$$ with a quotient of $$\2\$$ or greater, and $$\n \ge 2\$$. Gives a correct answer for all $$\n\ge 0\$$. Doesn't work under GNU ERE, nor does any variation of it such as ^((xx+)\2+|x|)$ or ^(xx+)\1+$|^x$|^$. The moment the ability to match an empty string is added, it falsely matches all primes greater than $$\7\$$. This appears to be a bug in GNU ERE. This form of primality test, eliminating the false positives on $$\0\$$ and $$\1\$$, dates back to at least as early as Abigail's 1997-11-18 signature on Perl Users Digest. It was not golfed at this point, and used a lazy quantifier for performance reasons (a change that occurred on 1997-10-24). This got carried over into some early CGCC answers, making them at least 1 byte longer than necessary. The form presented here puts ^x?$ in the second alternative for performance reasons, so that it won't slow down the testing of $$\n‍≥2\$$ with the slight overhead of always trying that match first.

Alternative form:

^((xx+)\2+|x?)$ # Trilangle 1.3, 31 29 bytes <'?<#2%._zS<.>(>.,)2-/\\_/!@@  Reads a single integer from STDIN, and prints 0 iff it's prime. Try it on the online interpreter! ## TL;DR Keeps a running counter that starts at 2, and increments it until (input % counter) == 0. Then, it prints '0' if input == counter. ## What is Trilangle? Trilangle is a 2-D stack-based programming language. Program flow can be redirected with "mirrors" /|\_ or with branches <^7>vL. The branches can split, merge, or reflect control flow, depending on how they're used. If the IP walks off the board, it continues one row or diagonal to its left. ## Code Explanation Unfolds to this example from the README:  < ' ? < # 2 % . _ z S < . > ( > . , ) 2 - / \ \ _ / ! @ @ . . . . . . . Equivalent to this C code: #include <stdio.h> // Get an integer from stdin. Implementation provided by the interpreter. extern int getint(void); int main() { // RED PATH int input = getint(); int counter = 2; while (input % counter) // GREEN PATH ++n; // BLUE PATH if (input == counter) // YELLOW PATH return 0; // MAGENTA PATH puts("0"); return 0; }  This uses the new 2DUP instruction z to make stack management easier: it copies both the input and counter so that they may be operated on non-destructively. The older version below used a combination of j (indexed read), 2 (duplicate), and S (swap) to achieve a similar effect. ## Older answer: Trilangle 1.0, 42 41 40 bytes '2.?..<[email protected]'2,<|>(%!.\S)S,,)S<.....@>-  # floor, 105 bytes F:x->floor x r:x->1/(x-F x) I:x->1+F(F x-x) p:k->(F k*r k)+1/(r k-1) f:n->(n-1)*I(F p^(n-2)(1+1/(n-1))/n)  returns nonzero for primes and zero for non-primes ## Explanation Ungolfed version: intPair: x y -> x + 1/y left: x -> floor x right: x -> 1/(x-floor x) is_int: x -> 1+floor(floor x - x) fakt_1: n_k -> intPair ((left n_k)*(right n_k)) (right n_k - 1) f: n -> (n-1)*is_int( (left fakt_1^(n-2) intPair 1 (n-1))/n)  Uses Wilson's theorem to determine if the input is a prime number fakt_1^(n-2) intPair 1 (n-1) computes (n-1)!+1 (abusing that storing one in the second component of a pair, will increase the first component by 1) The rest of f checks if (n-1)!+1 is evenly divisible by n and returns 1 if yes and zero otherwise. The multiplication with (n-1) is to ensure that 1 is not falsely detected as prime ## Implementation: To run the program, execute the Python-script with the arguments -f <source-file> -- <input-number> # floor, 116 bytes F:x->floor x r:x->1/(x-F x) I:x->-F(F x-x) s:p->I(F p/r p)*F p+1/(1+r p) f:n->-F((1-n)/((1-n)^2+1))*F s^(n-2)(n+1/2)  returns non-zero for primes and zero for composites # Explanation: Ungolfed version: lt: x y -> -(floor((x-y)/((x-y)^2+1))) intPair: x y -> x + 1/y left: x -> floor x right: x -> 1/(x-floor x) not_int: x -> -floor(floor x - x) prime_step: n_k -> intPair (not_int(left n_k / right n_k) * left n_k) (1+right n_k) f: n -> (lt 1 n)*(left prime_step^(n-2)(intPair n 2))  prime_step takes a pair of integers (n,k) (encoded as a single rational number) as input an returns (0,k+1) if k is a divisor of n, and (n,k+1) otherwise. f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0 # 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

# Ruby, 21 + 1 = 22 19 + 1 = 20 bytes

Also throwing my hat into the Ruby battle using the regex approach (and improved using histocrat's suggestion):

p !/^(11+)\1+$|^1$/


Takes input as a unary string and invoked using the n flag:

$ruby -ne 'p !/^(11+)\1+$|^1$/' <<< 11111 true  • Ooh, you can drop two in fact. p !/^(11+)\1+$|^1$/ Sep 11, 2015 at 18:25 • @histocrat Interesting. I didn't know about that. However, it gives me warning: regex literal in condition. Since the rules state "if possible, output should consist solely of the string representation of a truthy or falsy value," I'd need to add the W0 flag, so it's a wash. Thanks for the tip, though. Sep 11, 2015 at 18:52 • @histocrat A-ha, it only gives that warning when I run it from a file rather than as a one-liner. So thank you indeed for that. Sep 11, 2015 at 20:45 # O, 23 bytes j.1>\J2/{Jn%0={0}{}?}dp  Take 2! This one uses trial by division. # Python 2, 466552 51 bytes 1. Went up to 65 bytes - Fix made thanks to feersum & Mauris 2. Went down to 52 bytes - Suggestions made by kirbyfan64sos and accepts in input from STDIN to complete the code. 3. Went down to 51 bytes - Suggestion made by kirbyfan64sos (thanks again!) to remove the space between 1 and and. Apparently if you have a letter that follows a number, a space isn't needed... how weird, but cool! This finds the remainder / modulus of the input integer n divided by every number from 2 up to n-1. If there is at least one number in this sequence that has no remainder, or results in 0, this means that the number is not prime. If every value in this sequence is non-zero, the value is prime. Also by definition, 1 isn't prime and so that has to be taken care of separately. n=input();print n!=1and all(n%i for i in range(2,n))  # Example Runs I ran this in IPython: In : n=input();print n!=1and all(n%i for i in range(2,n)) 1 False In : n=input();print n!=1and all(n%i for i in range(2,n)) 2 True In : n=input();print n!=1and all(n%i for i in range(2,n)) 3 True In : n=input();print n!=1and all(n%i for i in range(2,n)) 4 False In : n=input();print n!=1and all(n%i for i in range(2,n)) 5 True In : n=input();print n!=1and all(n%i for i in range(2,n)) 6 False In : n=input();print n!=1and all(n%i for i in range(2,n)) 7 True In : n=input();print n!=1and all(n%i for i in range(2,n)) 10 False In : n=input();print n!=1and all(n%i for i in range(2,n)) 15 False In : n=input();print n!=1and all(n%i for i in range(2,n)) 17 True In : n=input();print n!=1and all(n%i for i in range(2,n)) 20 False In : n=input();print n!=1and all(n%i for i in range(2,n)) 30 False  • It has to return false for 1. Sep 12, 2015 at 0:40 • You made it return False for every possible input but 1, which should be False :) – Lynn Sep 12, 2015 at 1:05 • @Mauris - Oops. I didn't fix that properly lol. Was on mobile. I'm on my computer now. Fixing. Sep 12, 2015 at 1:07 • @Mauris - Fixed now. Thanks. Sep 12, 2015 at 1:12 • Wow, this is almost the exact same code I wrote :) You can save a char by using > instead of !=. Sep 21, 2015 at 15:14 # 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 $? ./main 1 1 1 1 1 1 1 1 1 1 1 ; echo$?


# Bash+coreutils, 29 bytes

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


Test:

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


## 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. Sep 13, 2015 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),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*=...). Sep 15, 2015 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),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). Sep 15, 2015 at 16:14
• Ah, I see. I would have said that 1/0 does satisfy the condition, but I'll stick with your definition. :) Sep 15, 2015 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). Sep 15, 2015 at 16:20
• You can remove the space between string[] and a. Also, you can change Int32 to just int. Sep 19, 2015 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; 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" || "9" < inputData)) { inputData = inputData.slice(1); } if (inputData) { var inputNumber = inputData.match(/\d+/); 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. 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) ↑ 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... 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.