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

• Can I take inputs as negative numbers, where abs(input) would be the number I am testing? – Stan Strum Sep 6 '17 at 3:40
• Is there a reason for the full program requirement, rather than allowing the full range of default input types? E.g. answering with a function that takes its input as an argument, is currently disallowed? codegolf.meta.stackexchange.com/questions/2447/… – Lyndon White Dec 12 '17 at 6:21
• @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. – Dennis Dec 12 '17 at 12:51
• @Shaggy Seems like a question for meta. – Dennis Jun 25 '18 at 13:44
• Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. – Shaggy Jun 25 '18 at 13:45

## Pyke, 2 bytes

_P


If the P function is given a negative number, it returns whether it's prime or not.

# Factor, 56 bytes

Literally ungolfable.

USING: math.primes conv io ;

• I haven't used Factor recently, so I don't remember what must be done to print the t/f result of prime? – kernigh Nov 17 '17 at 1:04
• @kernigh print or maybe >string print? why are you asking – cat Nov 18 '17 at 18:24
• The task wants the result on STDOUT or something like it. This code leaves the result on the stack, and I can't remember if Factor would print the result, or if one must add more code to print the result. – kernigh Nov 20 '17 at 5:59

## Pyth, 2 bytes

P_


Try it here!

Pyth now has implicit input!

# Molecule, 3 bytes

Inp


Explanation:

Inp
n  convert to number
p primality test


## LiveCode 8, 708 bytes

on mouseUp
put p(it) into field "a"
end mouseUp
function p n
if n is 1 then return false
repeat with i=2 to n-1
if n mod i is  0 then return false
end repeat
return true
end p



This code can be placed inside any button. It will print true or false to a field named a. It should work for small-ish integers, but will probably freeze/crash on anything too large. Byte count is size of saved LiveCode stack with one button and one field and with this code in the button.

# Unipants' Golfing Language, 53 47 bytes

i$cu^d^-l_u^^/%cu%?%d%:_?coc$d:__^d^-:_u?cuo:


Try it online!

(It has been implemented as a standard example in the interpreter.)

# Fith, 30 bytes

*math* load line >int prime? .


This language isn't great for golfing...

This uses the prime? function in the *math* library. Here's a version using only builtins, which is pretty much what the library function does:

line >int -> x 2 x range { x swap mod } map all .


Explanation:

line           \ line of input
>int           \ cast to int
-> x           \ set x to the top of the stack
2 x            \ push 2, then x
range          \ range from [2, x)
{ x swap mod } \ anonymous function which calculates x mod its argument
map            \ map that function onto the generated range
all            \ return 1 if everything in the list is Boolean true, else 0
.              \ print the top of the stack


You may be able to tell that this language is just a little bit inspired by Forth. It also takes cues from PostScript, Python, and functional programming.

## C, 54 bytes

i;main(j){for(scanf("%d",&i);i%++j;);putchar(49^j<i);}

• Must be run without parameters, so j is initialized to 1.
• Prints 1 for primes, 0 for composites (no newline).
• Could save 2 bytes with unprintable output - I'm not sure if \x00 and \x01 qualify as falsy/truthy.
• '\0' and '\1' are truthy and falsy according to our definition, so printing NUL or SOH should be fine. – Dennis Jun 16 '16 at 22:58

# brainfuck, 208 202 bytes

This is the code I wrote for my Sesos answer. See that answer for a detailed explanation.

This code assumes input fits in a single cell. Attempting to take input from an empty file must set the cell to zero. It works on an unbounded tape with no wrapping, including one that can go negative. It works for all positive numbers. Output will be a byte with a value of 0 or 1.

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


# Idris, 78 bytes

main:IO()
main=let S n=length!getLine in print$0<(pow(product[1..n])2modS n)  This takes input as a unary string (it uses the string length as input). Compile this with idris -O3 or you’ll spend forever in Nat-computey hell. ## RPN, 16 bytes lambda x isprime  This define a function checking the primality of it's argument. Call like this: <number> lambda x isprime eval  # Python 3.5, 5852 58 bytes import math;n=int(input());print(math.factorial(n-1)**2%n)  I unassumed. Thanks Dennis. I assumed something about the way the input would be given. Thanks daHugLenny. import math;lambda n:print(math.factorial(n-1)**2%n) • You can save 13 bytes by using a lambda: import math;lambda n:math.factorial(n-1)**2%n – acrolith Aug 7 '16 at 2:21 • In this particular challenge, lambdas are not allowed. The spec says Write a full program that... (CC @daHugLenny) – Dennis Aug 10 '16 at 2:57 # Nim, 70 56 bytes import os,math let x=1.paramStr.len echo fac(x-1)^2mod x  Uses Wilson's theorem; that is, x is prime if (x - 1)!² mod x is 1. Takes input in unary (any character) via the first command-line argument. Outputs 1 if the input is prime, and 0 otherwise. To test: $ nim c prime.nim
$./prime 11111111 0$ ./prime 1111111
1
$./prime 1 0  Note that according to the Nim os docs, this solution will not work on POSIX as paramStr isn't available for some reason. # PHP, 70 65 bytes for($i=2;$i<$n=$argv[1];$i++)if(is_int($n/$i)?1:0){echo 0;break;}


Empty output if the number is prime, print 0 if the number is not prime.

Not very original or best answer, but this is it...

Test online

## Ruby, 33 bytes

A little longer than other solutions, but doesn't require flags:

require'prime';p$*[0].to_i.prime? Can be run putting in a file, say prime.rb: ruby prime.rb 97 Or directly on the command line: ruby -e "require'prime';p$*[0].to_i.prime?" 97

## Logy, 82 bytes

f[X]->X<2&1|X*f[X-1];p[&1]->0<0;p[X]->f[X-1]%X==X-1;main[A]->print[p[atoi[A(1)]]];


I have no idea what I am doing.

Use Wilson's theorem.

Ungolfed code:

factorial[X] -> X < 2 & 1 | X*factorial[X - 1];
prime[&1] -> FALSE;
prime[X] -> factorial[X - 1]%X == X - 1;
main[Args] -> print[prime[atoi[Args(1)]]];


# Batch, 121 bytes

set i=2
if %1%==2 exit /b
if %1%==1 echo 0
:b
set /a a=%1%%%i%
set /a i=%i%+1
if %i%==%1% exit /b
if %a%==0 echo 0
goto b


Outputs 0 if it's no prime. This works only for inputs input > 0.

# Dip, 1 byte

P


Pretty self-explanatory...

## Unary, 165192711826249169871716905363504385377479408598339493836 bytes

Well, basically 165192711826249169871716905363504385377479408598339493836 zeros. Here is a Java program that prints the actual program:

public class Main{
public static void main(String[]args){
for(BigInteger i = new BigInteger("165192711826249169871716905363504385377479408598339493836"),BigInteger j = BigInteger.ZERO;j.compareTo(i)!=0;j = j.add(BigInteger.ONE)){
System.out.println("0");
}
}
}


This a port of this Brainfuck answer.

## memes, 2 bytes

I decided to hop on the language train. Code:

}"


Explanation:

} //Takes next input.
" //Returns True or False, representing if the input is prime.


# Ceylon, 107 112

That was my first try:

shared void p(){if(exists a=process.readLine(),exists c=parseInteger(a)){print(!(2:c-2).any((d)=>c%d<1));}}


This is a simple trial division of all numbers between 2 and c - 1, using the range operator : and the any method for iterating.

But this will also note 1 as prime. So here the corrected version:

shared void p(){if(exists a=process.readLine(),exists c=parseInteger(a)){print(1<c&&!(2:c-2).any((d)=>c%d<1));}}


That works for numbers up to 2^63-1 ... and takes quite long for larger primes (or composite numbers with large factors) – I think it took about half a minute to confirm 2147483647 (=2^31-1) as prime.

The formatted version:

shared void p() {
exists c = parseInteger(a)) {
print(1 < c && !(2 : c - 2).any((d) => c % d < 1));
}
}


I originally wrote the check as d.divides(c), but the modulo operator is so much shorter.

As a bonus, here is a variant for arbitrary size integers, though there is not really a point in using this due to the slowness.

import ceylon.math.whole {
w=parseWhole,
t=two,
o=one
}
shared void q() {
exists c = w(a)) {
print(c == t || !(t .. c - t).any((d) => c % d < o));
}
}


The : range operator needs an Integer (the number of elements) as a second argument, so we use the .. operator, which takes the same type as the first argument, i.e. here a Whole, as second argument (the upper limit). 2..c-1 is the same as 2:c-2 for large c, but this becomes an empty list for two (and a non-empty list for one), so we need a different exception here than in the Integer version. It becomes mainly longer due to the imports.

The space-reduced version has length 153:

import ceylon.math.whole{w=parseWhole,t=two,o=one}shared void q(){if(exists a=process.readLine(),exists c=w(a)){print(c==t||!(t..c-o).any((d)=>c%d<o));}}


# Maverick, 25 bytes

(1:(<>@-1)//$*)%<>@=<>@-1  Try it online! This is a pretty fun language IMO. Infix and esoteric. (1:(<>@-1)//$*)%<>@=<>@-1
1:                         range from 1 to
(<>@                     first command line arg (<> called with no args)
-1)                  minus 1
//$* folded over multiplication ( )% modulus <>@ the input = does the above equal <>@-1 the input minus 1? If so, yields prime  # Valyrio, 14 bytes s∫main [ipo]  Outputs 1 if the input is prime. Otherwise outputs 0. ### Explanation s∫ tells the interpreter to enter stack mode main [ starts the main code block i takes an input and evaluates it p pushes 1 or 0 to the stack depending on primality o outputs the top item on the stack ] ends the main code block ## Racket 75 bytes (let p((c 2))(cond[(> c(sqrt n))#t][(= 0(modulo n c))#f][else(p(+ 1 c))]))  Ungolfed: (define (f n) ; COMMENTS: (let loop ((c 2)) (cond [(> c (sqrt n)) #t] ; if no divisor found till sq root of number, it must be a prime [(= 0 (modulo n c)) #f] ; if divisor found, it is not a prime [else (loop (add1 c))] ; try with next number )))  Following version is longer but more efficient for checking larger numbers since it keeps & uses previously found prime numbers: (λ(N)(define(p n(o'(2))(c 2))(cond[(> c n)o][(ormap(λ(x)(= 0(modulo c x)))o) (p n o(+ 1 c))][else(p n(cons c o)(+ 1 c))]))(= N(car(p N))))  Ungolfed version: (p=subfunction to build prime number list till n; o= list of prime numbers found; c=current number being checked) (define f (λ (N) (define (p n (o '(2)) (c 2)) (cond [(> c n) o] [(ormap (lambda(x) (= 0 (modulo c x))) o) (p n o (add1 c)) ] [else (p n (cons c o) (add1 c))])) (= N (first (p N)))))  Testing: (f 109) (f 10) (f 11) (f 12) (f 13) (f 49) (f 43) (f 57) (f 47)  Output: #t #f #t #f #t #f #t #f #t  • If I understand correctly, the solution given is a snippet, not a full program, because it inputs from the variable n. – Esolanging Fruit Apr 24 '17 at 6:43 # PHP, 43 39 54 44 43 bytes improved my answer from stackoverflow: for($i=$n=$argv[1];--$i&&$n%$i;);echo$i==1;


Run with -r. prints 1 if argument is prime, empty string else.

loops $i down from $n-1 until it finds a divisor of $n; $n is prime if that divisor is 1.

6 bytes extra for the 1 case. almost happy.

# √ å ı ¥ ® Ï Ø ¿ , 3 bytes

Ipo


p is the primality test.

# NO!, 34 bytes

This was taken from the NO! GitHub page. It isn't mine

NOOOOOOO?NOOOOOOOOOOO
NOOOOOOOO?no

• This should be marked as community wiki if you didn't write it. – Esolanging Fruit May 11 '17 at 14:09

Ruby 16+15 bytes

require 'prime';p->e{e.prime?}


## QBIC, 2120 3 bytes (nc)

Since the purpose of the challenge is to build a catalog, I feel it's important to keep the QBIC post up-to-date with the current state of the language:

­?µ:


Explanation:

?    PRINT
µ   QBIC's prime test, returns -1 for primes, 0 otherwise
:  Read a number from the command line, insert that here
The function is closed automatically because of EOF.


Previously, at 20 bytes:

:[a|~a%b|\p=p+1}?p<3


Simple trial divider. Every time b (the loop counter) cleanly divides a (our prime-candidate), p is increased. Primes will end with p at 2 (or p=1 for a=1). This then prints -1 for primes, and 0 for non-primes, which are QBasic default values for true and false resp.

Original entry, 21 bytes. This prints 1 for primes, and 0 for others. This feels more 'natural' to me than QBasic's default -1/0. Also, this only does slightly less than a/2 divisions for primes (and quits when it detects a non-prime), instead of doing a divisions regardlessly.

:[2,a/2|~a%b=0|_Xp}?q


Explanation:

:       Get the input number, 'a'
[2,a/2| FOR(b=2, b<=(a/2), b++)
~a%b=0  IF a MOD b == 0     --> Clean division == no prime
|_Xp    THEN exit program, printing 'p' (which never gets set and is 0 by default)
}       Close all language constructs: IF/END IF, FOR/NEXT
?q      We've made it through the FOR loop without division, N is prime.
In QBIC, 'q' is auto-initialised to 1, '?' prints it.


D,f,@,P
+?
\$f,x
O


Try it online!

10 bytes are boilerplate for the full program requirement.

## Function, 7 bytes

D,f,@,P


Fairly basic, just defines a function that performs a primality test

## Built-in, 1 byte

P


As functions and main code use both different memory models and different commands, this only works in function mode and so would be invalid.