# 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

# Python 3, 52 bytes

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


Saved a byte thanks to xnor in chat.

• It gives an error because there lacks a semicolon in the string. And you could save a character by removing the *n and adding a minus sign in the output. – Labo Nov 9 '15 at 13:33
• @Labo That won't work. It would print 2 for input 4. – Dennis Nov 10 '15 at 17:12
• Yes, sorry, I forgot this case… – Labo Nov 10 '15 at 20:55
• Is that a tadpole operator I see? – Yakk Nov 13 '15 at 15:17
• Yes! ~-x is shorter than x-1 here, because I can avoid a pair of parentheses. – Lynn Nov 13 '15 at 16:49

## Seriously 0.1, 2 bytes

,p


, reads a value from STDIN. p pops from the stack and pushes 1 if it is prime, else 0. At EOF, all values on the stack are popped and printed.

Currently, Seriously uses trial division to test primality, so for large inputs it may take a while. In a future version, I'll probably use ECPP or Miller-Rabin.

Try it online

• Seriously. Seriously? – Dennis Nov 9 '15 at 3:03

# 05AB1E, 1 byte

Code:

p


Explantation:

p     # Implicit input, check whether it is prime or not.


Try it online!

• @Okx Actually, that isn't necessary to state in this challenge, because this challenge explicitly states that newer languages are welcome here. – Adnan Jan 26 '17 at 17:34

## Sesos, 6362 58 bytes

0000000: 1651bc afcddc c4fbbe 3e739e c0f1be 3673c3 eecdf8  .Q.......>s....6s....
0000015: cc75b8 677ce2 b57bc6 78cddc 796de3 7eed33 b7c113  .u.g|..{.x..ym.~.3...
000002a: ef9da3 a0fbbc 77ece7 3adc2b 354e33 f9             ......w..:.+5N3.


The ASM code that I wrote, along with some comments can be run on Try it online:

set numin
set numout
get
sub 1
jmp ; if
jmp ; copy
fwd 1
fwd 1
rwd 2
sub 1
jnz ; end copy
fwd 2
sub 1
jmp ; triplicate loop
fwd 1
fwd 1
fwd 1
rwd 3
sub 1
jnz ; end triplicate
fwd 1
sub 1
fwd 1
sub 1
jmp ; factorial loop
jmp ; multiply loop
fwd 1
jmp ; forward add step of multiply loop
fwd 1
fwd 1
rwd 2
sub 1
jnz ; end forward add step of multiply loop
fwd 2
jmp ; after add step, reset tape
rwd 2
fwd 2
sub 1
jnz ; end reset tape
rwd 3
sub 1
jnz ; end multiply
fwd 1
get ; sets to 0
fwd 1
jmp ; transfer intermediate value
rwd 1
fwd 1
sub 1
jnz ; end transfer
rwd 3
sub 1
jmp ; reset loop counter
fwd 1
rwd 2
fwd 1
sub 1
jnz ; end reset
rwd 1
jmp ; fix memory location of header
fwd 1
rwd 1
sub 1
jnz ; end fix
fwd 2
jnz ; end factorial
fwd 1
rwd 4
jmp ; transfer input for mod
fwd 5
rwd 5
sub 1
jnz ; end transfer
fwd 4
jmp ; mod
sub 1
fwd 1
sub 1
jmp ; a
fwd 1
fwd 2
jnz ; a
fwd 1
jmp ; b
jmp ; c
sub 1
rwd 1
fwd 1
jnz ; b
fwd 1
fwd 2
jnz ; c
rwd 5
jnz ; end mod
fwd 1
get ; sets to zero
fwd 1
jmp ; invert a
rwd 1
fwd 1
get ; blanks
jnz ; end invert a
rwd 1
jmp ; invert b
fwd 1
sub 1
rwd 1
sub 1
jnz ; end invert b
jnz ; end if
fwd 1
put


I've never written any BF variant code before, outside of very simple tasks, so I'm sure some of this is not optimal. The divmod algorithm and the logical negation algorithm used were taken from the esolangs algorithms page.

This implements Wilson's theorem. We compute (n-1)! + 1 and then logically negate that value mod n. The factorial code hangs on input 1, so the code is wrapped in an if loop that totally skips running in that case. At the very end, the tape head is manipulated to be over where we would have left the mod value if we ran the code, or over some random zero if the input was 1. I'll add a more thorough explanation when I am done golfing.

# Mini-Flak, 202 bytes

Mini-Flak is a turing complete subset of the Brain-Flak language. (It is currently the smallest know turing complete subset of Brain-Flak) It works exactly like Brain-Flak except the <> and [] nilads and the <...> monad are forbidden.

(({})){(({}[()])(((({}({}))[({}[{}])]([()]()))({({}[()((({}()[({})])){{}((({}({})))[{}])}{})]{})}({}{}({})[{}]))[{}]))[{}])}{}{}({}({})[{}()()()]){({}[()((({})){(({}{}(({})))[{}])}{}({}({})[{}]))]{})}{}


Try it online

## Explanation

The reason <...> is banned in mini-flak is that it is equivalent to (...)[{}]. So to start this explanation I am going to use this translation in reverse to create an equivalent Brain-Flak program for increased readability for anyone who is already familiar with Brain-Flak.

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


This program has two main parts, performs the modulus on the input for every number smaller than than the input and leaves them in a stack.

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


This uses a old version of modulo I wrote ({}(<()>)){({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)

The second part ands together all of the results of the last part

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


If any one of the results is zero the result of all the ands will be zero otherwise it will be truthy and the number will be prime.

# Japt, 1 byte

j


Built-ins are useful for long challenges, but aren't fun in mini-challenges like this. So here's an alternate version without the built-in; still pretty short:

# Japt, 8 bytes

o2 e@U%X


Try it online!

### How it works

      // Implicit: U = input number. Implicitly place a U at the beginning of the program
o2    // Create an array of all integers from 2 to U. (2o6 = [2,3,4,5])
// For numbers below 2, this returns n to 2. (2o-3 = [-3,-2,-1,0,1])
e@    // Check if every number X in this range returns truthily to:
U%X   //   the remainder of U divided by X.
//   In other words, if any of these remainders are 0, return false.
//   For numbers less than 2, the range contains 1,
//   so this always returns false for these cases.
// Implicit: output last expression


# J, 19 17 Bytes

echo(p:[:".1!:1)1


### Explanation:

echo(p:[:".1!:1)1  | Full program.
echo(          )   | Hook: (f g) y is evaluated as y f (g y)
[:".1!:1    | Right verb in the hook
1!:1    | With argument 1, reads a line of input
".        | Evaluate, converts valid string to int
[:          | Cap, treat these two verbs as one
p:            | With a left argument of 1, as supplied by the hook, tests primality of its right argument
echo               | Print

• I might be missing something, but 1 p: is shorter than 1=#q: (built-in primality testing isn't disallowed as far as I can tell). – cole Jan 16 '18 at 22:25

# Pip, 10 8 bytes

1=0Na%,a


Try it online! (testing numbers 0 through 29)

Takes the number as a command-line argument (a) and uses the definition of prime number (has only 1 and itself for factors):

      ,a  Range of numbers from 0 through a-1
a%    Take a mod each number in range; this is 0 if the number is a divisor,
nil if the number is 0, and nonzero otherwise
0N      Count the number of zeros in that list
1=        True (1) if the count is exactly 1, false (0) otherwise
Print (implicit)


# Lua, 56 bytes

n=io.read"*n"p=1
for i=1,n-1 do
p=p*i*i%n
end
print(p%n)

• p=1 for i=1,...-1 do p=p*i*i%...end print(p%...>0) does the job in 50 bytes, by switching the input to command-line argument, and printing true and false instead of 0 and 1. Also, Be aware that 0 evaluates to true and is therefore a truthy value in lua, so your current answer technically always input true. – Katenkyo Apr 11 '16 at 12:31

# APL, 21

{∧/0≠⍵|⍨(⍵≠1)+⍳|⍵-2}⎕


Trial division. It would incorrectly state that ¯1 (minus one) is a prime but it's outside the domain so it's all right.

• Welcome to Programming Puzzles & Code Golf! Because APL has its own legacy code page, we usually count APL as one byte per character here. – Dennis Sep 13 '15 at 5:28

# Prelude, 12580755955 52 bytes

1-^ (1-v#0)#)#1+1-))(0
?(1-
^  ^1-( 0#v+^-( 0##10)!


For convenience, I'd suggest using my modified interpreter which reads input and prints output as decimal integers. (Otherwise, I/O would be via a single character's ASCII value.)

It turns out that simple trial division is shorter in Prelude than the squared-factorial approach, because multiplication is fairly expensive. I also found new shortest solutions to compute a modulo and a logical NOT while working on this.

## Explanation

The basic algorithm is trial division: check how many numbers in [0,n-1] divide the input n via modulo (where my modulo implementation happens to return i for i%0, such that 0 is never a divisor, but doesn't crash the program either). If there was exactly one divisor (1) we have a have a prime, otherwise we don't. So the print the logical NOT of the number of divisors minus 1.

Let's go through the voices:

1. This voice counts the number of divisors, and is also used for the outer loop of the modulo.
2. This voice merely reads the input and then performs the main loop from n-1 down to 0.
3. This voice does the main work of the modulo computation and computes and prints the logical NOT of the number of divisors.

Finally, we can look at some parts of the code in detail:

  ^ (1-v#0)#)#

^1-( 0#v+^-


This is the modulo. The top voice starts by copying n from the bottom voice and the bottom voice copies the current (potential) divisor from the middle voice. The idea is to decrement both values until n is zero, but whenever the divisor hits zero we restore it.

The restoring works like this: we always copy the divisor into the top voice with v. But while the bottom voice is non-zero, we immediately discard it and push a zero instead. This value is then shifted to the bottom voice and added to the current value there.

Finally, the modulo is how far we are into the current cycle, so we subtract the divisor from the result with ^- (which is actually minus the modulo, but we only want to know if it's zero or not, so this doesn't matter).

1-     mod    1+1-))
?(1-
^     mod     ( 0##


This is then the main loop. The top voice is initialised to -1 (to account for the fact that 1 is always a divisor), the middle voice reads the input and the bottom voice receives a copy. Before computing the modulo, the middle voice decrements the current divisor.

After the modulo is computed we increment the counter, but decrement it again if the modulo was non-zero.

Finally, we compute the logical not, by pushing a 1 onto the bottom voice but putting a 0 on top if the divisor counter was non-zero, before printing it:

                    (0

10)!


# Fortran 2003, 51 bytes

Here is a solution using Fortran's array capabilities. Fortran 2003 is really only required for the shorter array constructor [ ] instead of the old (/ /).

read*,n
print*,count([(mod(n,i),i=1,n)]==0)==2
end


# MATLAB, 2431 36 bytes

1. Changed to 31 bytes in order to add in the case of n=1
2. Changed to 36 bytes to make a full program and to incorporate the 1 byte saving from a suggestion by pawel.boczarski (thanks!)

Since isprime is already taken, an alternative is to take a look at the greatest common divisor of the number in question n with every number from 2 up to n-1. If the GCD of every number in the output is 1, then the number is prime. However, we need to check for the case of n=1, and so by definition, this shouldn't be prime:

n=input('');n-1&all(gcd(n,2:n-1)==1)


This creates an anonymous function that checks if the number is prime and assigns it to the variable f. To call the function, simply do f(n) once it's created with n being a positive integer.

# Sample Runs

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
1

ans =

0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
2

ans =

1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
3

ans =

1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
4

ans =

0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
5

ans =

1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
7

ans =

1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
10

ans =

0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
13

ans =

1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
15

ans =

0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
20

ans =

0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
23

ans =

1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
33

ans =

0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
37

ans =

1

• Two tips: you can omit f= - the anonymous handle is a perfect solution (2 bytes saved), moreover in case of positive integer n~=1 can be replaced by n-1 (1 byte saved) - I tried in Octave and it worked, should work in Matlab as well. – pawel.boczarski Sep 12 '15 at 8:59
• @pawel.boczarski thanks! I had the anonymous handle but thought it conflicted with the definition of a "full program". Could you perhaps clarify on what this means? – rayryeng Sep 12 '15 at 9:02
• Uhm, you're right. This is clarified in the task spec that a full program is demanded, I didn't notice that. But the tip with n-1 instead of n~=1 will still work. – pawel.boczarski Sep 12 '15 at 9:10
• @pawel.boczarski that'll shave one byte off. Thanks! Also thanks for the clarification – rayryeng Sep 12 '15 at 9:19

## HPR, 1217 bytes

393 bytes with macros

HPR is an unusable language I created for a challenge here. It has only five commands, and it's not Turing complete; I was actually surprised that a primality test could be programmed in HPR. This answer stretches the conditions of input formats a bit, since the input has to be provided as a descending list of integers from n to 1, encoded in unary and separated by 0s. There has to be a trailing 0, so the number 4 would be encoded as 11110111011010. The program prints 1 if the input is a prime, and an empty line if not. Here's the source code:

$!($)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(--))(*#(!(-)(#(-)()))())))!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))())!(#(*#(!(-)(#(-)()))())(!(-)(#(-)()))-!(-)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(#(#(!($)(#(*)()#(!(-)(#(-)()))())!(-)(#(-)())*)()#(!(-)(#(-)()))())(!(-)(#(-)())))(-#(!(-)(#(-)()))())#(!(-)(#(-)()))())))(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())($!($)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())(#(*)()#(!(-)(#(-)()))()))!(-)(#(-)())#(*)(!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))#(!(-)(#(-)()))())!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(*)(!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))#(!(-)(#(-)()))())))-#(!(-)(#(-)()))())-#(!(-)(#(-)()))())!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(--))(*#(!(-)(#(-)()))()))!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(-)  This was not written by hand, but generated from this 393-byte source by TheNumberOne's macro system: def d 0 !(-)(#(-)()) def l 0 #(<d>)() def f 1 !({0})(#({0})()) def n 1 !(<d><l>)({0}) def o 2 <n>(<n>({0})){1} def m 0 <d><f>(-#(!(*)(#(*)())<l>)(<d>))#(-)(<l>) def x 0 <d>#(*)(<m>)<l> def z 1 <d>*<l>!(-)(-{0}) def i 0 <d>#(<z>(-))(*<l>)$!($)(<o>(<i>,<m>!(#(*<l>)(<d>)-!(-)(<n>(!(#(#(!($)(#(*)()<l>)<d>*)()<l>)(<d>))(-<l>)<l>)))(<o>($!($)(<o>(#(*)()<l>,<x>))<n>(<x>),-<l>))-<l>))<n>(<i>)<z>()


## Explanation

An HPR program is run in an environment, which is a set containing nonnegative integers and lists. Initially, it contains the input list, and the five commands modify the environment in different ways. However, it's not possible to obtain larger numbers than the maximum of the list, and it's not possible to add new elements to lists. Thus, trial division is the way to go. I'm not going to completely explain the code in this post, but an expanded version with comments can be found here.

# Sesos, 28 24 bytes

0000000: 1651b8 77cd1c 345e33 c67bbe c673b8 676c38 67fe98  .Q.w..4^3.{..s.gl8g..
0000015: 70e201


Uses trial division. Try it online! Check Debug to see the generated binary code.

### How it works

The binary file above has been generated by assembling the following SASM code.

set numin     ; Switch to numeric input.
set numout    ; Switch to numeric output.

get, sub 1    ; Read an integer n from STDIN and decrement it.
; If n is 1, this will leave a 0 in cell 0.
jmp           ; While loop entry point; if the cell is 0, skip the loop body.

; The following is the actual primality test. To see how it works, consult the
; corresponding section of this answer.

jmp, rwd 1, add 1, fwd 2, add 1, rwd 1, sub 1, jnz
fwd 1
jmp
sub 1, rwd 1
jmp, fwd 1, add 1, rwd 1, sub 1, jnz
rwd 1
jmp
fwd 1, add 1, fwd 1, sub 1, fwd 1, add 1, rwd 1
jmp, fwd 1, jnz
fwd 1
jmp, rwd 1, add 1, fwd 1, sub 1, jnz
rwd 2
jmp, rwd 1, jnz
fwd 1, sub 1
jnz
fwd 3
jnz
rwd 1, sub 1
jmp, rwd 1, jnz

jnz           ; While loop exit marker; since the previous instruction also sets
; an exit marker, the current cell will be 0 and we exit the loop.
rwd 1, put    ; Retrocede to the previous cell and print its content to STDOUT.
; If n > 1, this will print the result from the primality test.
; If n = 1, it will simply print 0.


### Modulus computation

The core of this answer is its modulus algorithm, which is based on the divmod algorithm from Esolangs. Unlike the latter, it doesn't compute a quotient and works if the divisor is 1.

Suppose the tape in in the following state, where n and d are positive integers.

  v
n     0     d     0     0     0


To compute n % d, we will decrement the third cell n times. Each time we decrement it, we also increment the fourth cell (so their sum is d at all times), and swap their contents every time the third cell reaches 0.

We have to decrement the first cell once for each iteration, and stop once it reaches 0. Since this will destroy the content of the first cell, we'll also increment the second cell once for each iteration, effectively copying n to the second cell.

Once the first cell reaches 0, the tape will be in the following state.

  v
0     n   d-n%d  n%d    0     0


We achieve this as follows.

jmp           ; While the first cell is non-zero:
fwd 1     ;     Advance to the second cell.
fwd 1     ;     Advance to the third cell.
sub 1     ;     Decrement it.
fwd 1     ;     Advance to the fourth cell.
rwd 1     ;     Retrocede to the third cell.
jmp       ;     While the current cell in non-zero.
fwd 1 ;         Advance to the next cell.
jnz       ;     This will advance to the fifth cell if the third is non-zero
;     and stay on the third cell otherwise.
fwd 1     ;     Advance either to the fourth or sixth cell.
jmp       ;     While the fourth/sixth cell is non-zero:
rwd 1 ;         Retrocede to the third/fifth cell.
fwd 1 ;         Advance to the fourth/sixth cell.
sub 1 ;         Decrement it.
jnz       ;     This will add the fourth/sixth cell to the third/fifth cell,
;     zeroing the former in the process. Since the sixth cell has a
;     value of 0, this loop is a no-op if the third cell in 0; other-
;     wise, it sets the third cell to d and the fourth cell to 0.
rwd 2     ;     Retrocede to the second/fourth cell.
jmp       ;     While the current cell is non-zero:
rwd 1 ;         Retrocede to the previos cell.
jnz       ;     This places the head to the left of the first cell.
fwd 1     ;     Advance to the first cell.
sub 1     ;     Decrement it.
jnz           ;


### Primality test (WIP)

For input n > 1, we can use the modulus algorithm from the previous section to implement a primality test by trial division.

If n is already on the tape, we procede as follows.

1. Create a copy of n and decrement it to leave the tape as

                  v
n     0     d     0     0     0


where d = n - 1.

2. Retrocede to n and use the modulus algorithm to compute n % d, leaving the tape as follows.

      v
0     n   d-n%d  n%d    0     0

3. Advance to the cell containing n % d.

1. If n % d > 0, add d - n % d to n % d to restore d, decrement it, and go back to step 2.

2. If n % d = 0, we found the first divisor of n (1 for primes); go to step 4.

4. Since n % d = 0, d - n % d = d.

We retrocede to that cell, decrement it to leave d - 1 in it (0 if and only if n is prime), and retrocede until finding the first 0 cell. This leaves the tape as

             v            V
0      0     n     d-1   0    0     0


where v marks the location of the tape head if d - 1 > 0, and V the location if **d - 1 = 0.

Note that the value of the cell under the tape head will be 0 in either case. The cell to the left will contain n if n is prime, and 0 if n is composite.

• You should add the BF version of your modulus algorithm to the Esolangs page. – mbomb007 Jul 25 '16 at 15:35
• Done. – Dennis Jul 25 '16 at 17:09

# brainfuck, 62 bytes

,-[+[<+>>+<-]>[-<[>+<-]<[>+>->+<[>]>[<+>-]<<[<]>-]>>>]<-[<]]<.


This is a port of my Sesos answer. Input and output are character-based. For a character whose code point is prime, the program will print the character itself; otherwise, it will print NUL.

Try it online!

## Jellyfish, 13 bytes

p|&*!<
E   i


Try it online!

Uses the squared-factorial approach based on Wilson's theorem.

### Explanation

Jellyfish is Zgarb's language based on his 2D syntax challenge. The semantics are largely inspired by J, but the syntax is where it gets interesting. All functions are single characters and laid out on a grid. Functions take their arguments from the next token south and east of them and return the result north and west. This let's you create an interesting web of function calls where you reuse values by passing them into several functions from multiple directions. There are also higher-order functions called operators, which let you construct more complex functions from the built-in ones.

The only non-functions in the above code are E and &. The former redirects |'s search for its southern argument to the east, so that | actually takes i as that input.

& applied to a single unary function (in this case *) uses the binary definition by supplying the single argument twice. Since the binary definition of * is multiplication, this yields a squaring function.

Taking these things into account, we can write up a more conventional expression:

p(i | (&* ! < i))


Here, i is just the input we're testing for primality. < decrements it, ! computes its factorial, &* squares it. | is modulo although it divides its right-hand operator by its left to compute the remainder. Hence the stuff inside the p(...) computes (n-1)!^2 % n. The p just prints the result.

• I'm a little surprised how much you can do with my nonsensical collection of built-ins. :D But thanks for the praise! – Zgarb Aug 3 '16 at 20:19

# WolframAlpha, 10 bytes

isprime(n)

• haha, this is interesting... – ABcDexter Aug 31 '16 at 9:56
• Save some bytes with 'n prime'. – Pavel Dec 29 '16 at 22:40

# Logicode, 601511 467 bytes

circ o(n)->cond n<->0+n/o(n>)
circ p(n)->[
cond n->var c=~((~(o(n)))>)/var c=0
cond (~n)<->var d=p(c)+0/var d=c+1
d
]
circ q(n)->[
cond n->var e=~((~(o(n)))>)/var e=0
cond (~n)<->var f=e+0/var f=q(e)+1
f
]
circ r(a,b)->cond *a&*b->r(q(a),q(b))/a
circ s(a,b)->!(*(r(b,a)))
circ t(a,b)->cond b->t(q(a),q(b))/a
circ u(a,b)->cond s(a,b)->u(t(a,b),b)/!(*a)
circ v(a)->[
var j=p(j)
cond s(a,j)->[
var k=k+u(a,j)
var l=v(a)
]/[
var k=k
]
*((~k)>)
]
var j=1
var k
out v(binp)


Oh my, that is a lot of code.

Here's a rundown of what each circuit does:

• o is a trimmer, and it strips the extra 0's at the start (this is used for p and q.
• p is a successor, and q is a decrement.
• r is a preliminary bit to s (lessthan).
• s is the lessthan (which uses the remainder checker).
• t is a subtractor, which calculates a - b for any two positive integers a and b (in binary).
• u is a mod checker, which returns 1 if a%b is not 0, and 0 if it is 0.
• v is the actual prime checker, which returns 1 if the number is not prime, and 0 if the number is.
• The j and k at the bottom are the divisor (b in the mod checker) and the un-bool'd output respectively.

The final line is the "input" bit, which asks for user input in binary (any other character that is not 0 or 1 in the input will be ignored), and returns 1 if the result is not prime, and 0 if the result is.

# Tcl, 78 75 bytes

Thanks to sergiol

if $argv<2 {exit 1} incr d while {[incr d]<$argv} {if $argv%$d==0 {exit 1}}


Original version

if {$argv<2} {exit 1} incr d while {[incr d]<$argv} {if {$argv%$d==0} {exit 1}}


Works for all integer values (both negative and arbitrarily large). However, as this aims to be short and not efficient, it is written with a simple divisor={2,3,4,...} loop, so you'll begin getting noticeable lag around eight digit numbers (n ≥ 108).

The input is taken on the command-line; the output is an exit code: 0 for prime and 1 for not prime.

On Windows you can use the following batch file to test it:

@echo off
tclsh a.tcl %1
if ERRORLEVEL 1 (
echo not prime
) else (
echo prime
)


Use it as:

C:\foo> run.bat 2017
prime


On *nixen you can use the following bash script to test it:

#! /bin/sh
tclsh a.tcl $1 if [$? -eq 0 ]
then
echo prime
else
echo not prime
fi


Use it as:

% ./run.sh 2017
prime


Enjoy!

• You can save some bytes: tio.run/##K0nO@f8/… – sergiol Oct 23 '17 at 0:40
• Please be careful to test stuff before suggesting edits. ! has higher precedence than %, so the ==0 remains... Other edits made from your suggestion. Thanks! – Dúthomhas Oct 23 '17 at 1:49
• I tested it on my local machine and it seemed to work – sergiol Oct 23 '17 at 9:18

# Symbolic Python, 48 bytes

___=_
__("__=_/_"+";_=-~_;__*=_*_"*~-_)
_=__%___


Try it online!

Uses Wilson's theorem, i.e. that $$\(n-1)!^{2} \% n = 1\$$ if $$\n\$$ is a prime, otherwise it equals $$\0\$$.

### Explanation:

___=_                              # Save the value of input to ___
__(                             )  # Evaluate string
"__=_/_"                        # Initialise __ as 1
+";             "*~-_   # Then repeat n-1 times
_=-~_;               # Decrement n
__*=_*_        # Multiply __ by n squared
_=__%___                           # Output the value of __ modulo ___


# Alchemist, 126 bytes

_->In_a
a->b+c
0e+b+c->g+h
f+0c+b->e+b
e+0h+c->f+c
f+0b+c->c
0e+0f+g->b
0f+h+0s->c
0f+0a+0g+0h+c->f
f+0b+0c+h->s
s+0h->Out_"1"


Try it online!

Outputs 1 for primes, and nothing for composite numbers. Here's a script that tests the program against numbers below 100.

This is rather inefficient, as I removed a restriction that prevented one rule undoing another rule for a sweet one byte save (worth it!). To be much more efficient, we can replace the 0e in the third rule with f and add f to the other side too. Try it online!

### Explanation:

_->In_a           # Create the input number of a atoms
a->b+c            # Convert all them to b and c atoms
# b will serve as a permanent save of the input
# c will be a counter starting at the input

0f+0a+0g+0h+c->f  # Decrement c and start the main loop by setting the f flag
# Note that f and 0e are mostly interchangeable, and the same with 0f and e
0e+b+c->g+h       # Subtract the counter from the input, keeping a copy of both
f+0c+b->e+b       # When the counter runs out, set the e flag
0f+h+0s->c        # Move the temporary counter atoms back to the main counter
e+0h+c->f+c       # Once done, set the f flag again
f+0b+c->c         # If the counter isn't 0 when the input reaches 0
# Then the input is not divisible by the counter

0e+0f+g->b        # Convert the temporary input atoms back to the main input
# Reuse the temp counter to main counter rule again

# Once both are done, start the loop over again, decrementing the counter
# This continues until:

f+0b+0c+h->s      # If both the counter and the input reach 0 at the same time
# Then the input is currently divisible by the counter
# Decrement the temporary counter atom
s+0h->Out_"1"     # If the temp counter is 0 after that (i.e. the highest factor is 1)
# Print 1


# 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? – Martin Ender Sep 14 '15 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. – histocrat Sep 14 '15 at 12:07 # O, 23 bytes j.1>\J2/{Jn%0={0}{}?}dp  Take 2! This one uses trial by division. # awk, 30 25 24 bytes "factor "$0|getline~--NF


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

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


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

{for(++d;$0%++d&&$0>1;);}d~$0  Prints the number if it's prime and nothing if it's not. Example usage: echo 12347 | awk '{for(++d;$0%++d&&$0>1;);}d~$0'

• And not only because I touched the ZX81 too: if you should have only 2 fields, it has not to be the 3rd. awk '"factor "$0|getline~!$3', one character less, but it answers prime number for 1 too (that it should be excluded), so I don't know if useful. – Hastur Jul 19 '16 at 17:53

# C, 61 bytes

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


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

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

Test:

echo 'r;main(i,j){r=(--i>1);for(j=i-1;j>1;)r*=!!(i%j--);return r;}' > main.c
gcc -o main main.c
./main 1 ; echo $? ./main 1 1 ; echo$?
./main 1 1 1 ; echo $? ./main 1 1 1 1 ; echo$?
./main 1 1 1 1 1 ; echo $? ./main 1 1 1 1 1 1 ; echo$?
./main 1 1 1 1 1 1 1 ; echo $? ./main 1 1 1 1 1 1 1 1 ; echo$?
./main 1 1 1 1 1 1 1 1 1 ; echo $? ./main 1 1 1 1 1 1 1 1 1 1 ; echo$?
./main 1 1 1 1 1 1 1 1 1 1 1 ; echo $?  # XSLT 3.0, 178 bytes <transform xmlns="http://www.w3.org/1999/XSL/Transform" xmlns:x="x" version="3.0"><template match="d" expand-text="yes">{.>1 and empty((2 to .-1)[current() mod .=0])}</template></transform>  Posted as an alternative, because it uses a significantly different approach than my previous post. In expanded form, with the usual prefixes: <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="3.0"> <xsl:template match="d" expand-text="yes">{ . > 1 and empty((2 to . - 1)[current() mod . = 0]) }</xsl:template> </xsl:stylesheet>  This method also uses a variant of my XPath solution for primality testing, which is explained there. Since the default in XSLT is to process all nodes in the input document, this is what happens here as well. For input, you need to hand it a proper, validated XML document with a root element <d>: <d>101</d>  The result will be output as true or false. It utilizes an XSLT 3.0 feature that allows inline XPath expressions in text nodes. It uses the XSLT 2.0 feature of schema-aware processing. If you don't have such a processor, add the XSD namespace and replace the XPath expression with the following: . > 1 and empty((2 to . cast as xs:integer - 1)[current() mod . = 0])  For a non schema-aware processor, it would make the code at least 62 bytes larger. ## 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. # JavaScript, 5352 40 bytes alert(/^(?!(..+)\1+$)../.test(prompt()))


Just realized the question allows unary input, which cuts the size down to 40 bytes. Previous answer of 52 bytes is below (ES6):

alert(/^(?!(..+)\1+$)../.test('1'.repeat(prompt())))  Uses that cool unary regex to determine primality. I actually originally wrote this without seeing the Retina answer, and using a different regex, as seen here: !/^1?$|^(11+?)\1+$/. I moved to the Retina one since saves a character by avoiding the need for negation. • I think this (and the other JavaScript answers) should use alert or console.log. Otherwise it's assuming a REPL environment (like a browser console) whereas the challenge explicitly asks for a full program. That said, your own regex wouldn't have been longer than mine, because you only need ^1$ (zero is not a valid input). – Martin Ender Sep 14 '15 at 10:11
• @MartinBüttner I agree on it needing a print statement, but when doing so puts an otherwise shorter answer behind longer ones that don't follow that rule... I chose instead to mention why I didn't. If the other answers conform, I'll gladly adjust mine as well. Thanks! =) Good point, hadn't noticed the 0 part. It would be the same length in that case. – Mwr247 Sep 14 '15 at 15:05
• Well if the others think the same no one will change it. ;) You could just leave a comment (if I haven't done so already) and hope for Dennis to invalidate the answer (to remove it from the leaderboard) if the author doesn't fix it within a couple of days. – Martin Ender Sep 14 '15 at 15:07
• @MartinBüttner I left a comment on one of them a few days back, but fair enough haha. I suppose I could just edit them all for it as well and update the counts. – Mwr247 Sep 14 '15 at 15:21
• You can actually shorten the original regex by one character by making it !/^.?$|^(..+)\1+$/ – Aplet123 Mar 27 '16 at 13:05