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.


  • 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 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.

Additional rules

  • 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.


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.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

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

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

368 Answers 368

3 4
6 7

𝔼𝕊𝕄𝕚𝕟, 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.


MATL, 2 bytes


Try it online!

Takes input implicitly. For positive input, function Zp outputs true (displayed as 1) if the number is prime, ans false (0) otherwise.


Scratch, 17 blocks (currently glitchy)

Edit: I fixed 2 bugs. But, if you enter 1, it gets in an infinite loop...

  • \$\begingroup\$ I tried the demo, and entering 7 returns False? \$\endgroup\$
    – mathmandan
    Oct 21, 2015 at 21:19
  • \$\begingroup\$ @mathmandan: Yeah, there were 2 bugs. I'll fix them, but the block count will be the same. \$\endgroup\$
    – user46167
    Oct 21, 2015 at 22:54
  • \$\begingroup\$ This seems to loop forever for input 1. \$\endgroup\$
    – Dennis
    Oct 22, 2015 at 1:46
  • \$\begingroup\$ @Dennis: Noted. Will fix with 5 more blocks \$\endgroup\$
    – user46167
    Oct 22, 2015 at 18:55
  • \$\begingroup\$ As before: Scratch is typically scored by the number of bytes in the corresponding scratchblocks code here. \$\endgroup\$ Oct 29, 2015 at 1:09

JavaScript (ES6), 54 bytes


Outputs 1 for prime, 0 for non-prime. All four JS solutions so far were based on the regex, so I thought I'd be brave and try one without.


Turtlèd, 490 487 451 bytes

Turtlèd does not support newlines in code... so oneliner fun!

golfed some bytes for not needing to support 0

Golfed some bytes removing useless code, and some other tricks

?#0#.:l( >;,u,[ :ll[*,l]d],u{*{*r}l' d{ l}[ (*.d)(0'1d)(1'2d)(2'3d)(3'4d)(4'5d)(5'6d)(6'7d)(7'8d)(8'9d)(9.l( .))]u[ r]lu}u2[#[ ;{ l}[ (0u.)(1u'1)(2u'2)(3u'3)(4u'4)(5u'5)(6u'6)(7u'7)(8u'8)(9u'9)dl]ur[ r]l[#[ r]l[ (0'9l( '#;))(1.;)(2'1;)(3'2;)(4'3;)(5'4;)(6'5;)(7'6;)(8'7;)(9'8;)]uuu[*r]{*l}u{*r}'*{*l}:;{ l}[ l]r]' uu[*r]{*r}d]l(*,(*@1)(1@0)'*)u{*' l}:;d[ (0'9l( '#l))(1.d)(2'1d)(3'2d)(4'3d)(5'4d)(6'5d)(7'6d)(8'7d)(9'8d)]r( u[ r]uu)][ [ l]r[ ' r]ul],)

Try it online!

I am most certainly not going to explain this with the annotations for each part of the code, at least not right now.

General explanation:

The program writes 0, takes integer input, if it is not one (if it is, it skips the rest of the code), it writes out two lines of asterisks, removing the zero that was written, one to compare for the prime checking, one to turn into a decimal string. It turns the lower one into a decimal string, then moves the decimal string up one. It writes out a single asterisk into a line above the other for each decrement of the upper decimal string. when goes below zero, the program moves the decimal string back up again, and keeps going on the upper line until it either aligns with the lower line, or goes past it. If it aligns, it sets the character variable to 1, if the character variable has not already been set to one. This is because it has no method to distinguish one when testing divisibility, so this makes it so it has to have more than one factor match. If it has been set to one, it sets it to zero. After it has tested all the numbers from n-1 to 1, it cleans up all the mess that it used to test the primality, then writes the character variable, which will be one if prime, else 0

  • \$\begingroup\$ Input 1 seems to result in an infinite loop. \$\endgroup\$
    – Dennis
    Sep 25, 2016 at 1:45
  • \$\begingroup\$ @Dennis Fixed!! \$\endgroup\$ Sep 25, 2016 at 1:59
  • \$\begingroup\$ @ConorO'Brien Submissions must terminate by default. \$\endgroup\$
    – Dennis
    Sep 25, 2016 at 3:42
  • \$\begingroup\$ @Dennis oh ok then \$\endgroup\$ Sep 25, 2016 at 3:48
  • \$\begingroup\$ I'm fairly sure I can golf some bytes, but the code is too.... ehhhh. It bugged out when I tried \$\endgroup\$ Oct 30, 2016 at 23:29

Haskell, 47 52 bytes

main=do n<-readLn;print$n>1&&all((>0).mod n)[2..n-1]

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

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

Samau, 2 bytes


Hex dump:

dd ab

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

▌       read a number
 τ      test if it is a prime

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

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


Hex dump:

dd 3b 5c b3 91 32 3d

Most mathematical functions in Samau automatically thread over lists.

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

Alice, 12 11 bytes


Try it online!

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


Try it online!


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

q, 35 34 bytes

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

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

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

0>min 1,x mod/:2_til x:"I"$read0 0


code is executed right-to-left

"I"$read0 0 reads STDIN, and then casts it to an integer

{..} denotes an anonymous function with x as an implicit variable, applied to the integer

til x returns a range 0..(x-1)

2_ drops 0 and 1, which are not needed for prime checking

1,x mod/: then takes mod of x with every element of the list and prepends a 1 to the list due to 1 and 2 returning empty list

0<min takes the minimum of the mods, and checks if it is bigger than zero. If it is, then it must be a prime!

  • 3
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ Mar 7, 2018 at 22:24

Whitespace, 145 137 134 bytes

[S S S N
_Push_0][S N
S _Duplicate][T N
T   T   _Read_STDIN_as_integer_in_heap_0][T T   T   _Retrieve][S S S T  S N
_Push_2][T  S S T   _Subtract][N
T   T   T   T   N
_Jump_to_Label_FALSE_if_negative][S S S T   N
_Push_1][S N
S _Duplicate_1][N
_Create_Label_LOOP][S N
_Discard_top_stack][S S S T N
_Push_1][T  S S S _Add][S N
S _Duplicate][S N
S _Duplicate][S S S N
_Push_0][T  T   T   _Retrieve_heap_at_0][T  S S T   _subtract][N
T   S T N
_Jump_to_Label_TRUE_if_0][S S S N
_Push_0][T  T   T   _Retrieve_heap_0][S N
T   _Swap_top_two][T    S T T   _Modulo][S N
S _Duplicate][N
T   S T T   N
S S T   N
_Create_Label_TRUE][S S S T N
_Push_1][T  N
S T _Output_1][N
S S T   T   N
_Create_Label_FALSE][S S S N
_Push_0][T  N
S T _Output_0]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Outputs 1 if a prime, 0 otherwise.

Try it online (with raw spaces, tabs, and new-lines only).

General explanation:

  1. Read input
  2. Is it less than 2: Return 0
  3. Integer i=1
  4. Start loop
    • 5) Increase i by 1
    • 6) If the input and i are equal: Return 1 (last iteration of the loop)
    • 7a) Is the input modulo i 0: Return 0
    • 7b) Else: Go back to step 5

Example run (with 5 as input):

Command   Explanation                   Stack       Heap    STDIN   STDOUT

SSSN      Push 0                        [0]         {}
SNS       Duplicate (0)                 [0,0]       {}
TNTT      Read STDIN as number          [0]         {0:5}   5
TTT       Retrieve heap at 0            [5]         {0:5}
SSSTSN    Push 2                        [5,2]       {0:5}
TSST      Subtract (5-2)                [3]         {0:5}
NTTTTN    Jump to Label_FALSE if neg.   []          {0:5}
SSSTN     Push 1                        [1]         {0:5}
SNS       Duplicate (1)                 [1,1]       {0:5}
NSSN      Create Label_LOOP             [1,1]       {0:5}
 SNN      Discard top                   [1]         {0:5}
 SSSTN    Push 1                        [1,1]       {0:5}
 TSSS     Add (1+1)                     [2]         {0:5}
 SNS      Duplicate (2)                 [2,2]       {0:5}
 SNS      Duplicate (2)                 [2,2,2]     {0:5}
 SSSN     Push 0                        [2,2,2,0]   {0:5}
 TTT      Retrieve heap at 0            [2,2,2,5]   {0:5}
 TSST     Subtract (2-5)                [2,2,-3]    {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [2,2]       {0:5}
 SSSN     Push 0                        [2,2,0]     {0:5}
 TTT      Retrieve heap at 0            [2,2,5]     {0:5}
 SNT      Swap top two (2,5] -> 5,2])   [2,5,2]     {0:5}
 TSTT     Modulo (5%2)                  [2,1]       {0:5}
 SNS      Duplicate (1)                 [2,1,1]     {0:5}
 NTSTTN   Jump to Label_FALSE if 0      [2,1]       {0:5}
 NSNN     Jump to Label_LOOP            [2,1]       {0:5}

 SNN      Discard top                   [2]         {0:5}
 SSSTN    Push 1                        [2,1]       {0:5}
 TSSS     Add (2+1)                     [3]         {0:5}
 SNS      Duplicate (3)                 [3,3]       {0:5}
 SNS      Duplicate (3)                 [3,3,3]     {0:5}
 SSSN     Push 0                        [3,3,3,0]   {0:5}
 TTT      Retrieve heap at 0            [3,3,3,5]   {0:5}
 TSST     Subtract (3-5)                [3,3,-2]    {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [3,3]       {0:5}
 SSSN     Push 0                        [3,3,0]     {0:5}
 TTT      Retrieve heap at 0            [3,3,5]     {0:5}
 SNT      Swap top two (3,5] -> 5,3])   [3,5,3]     {0:5}
 TSTT     Modulo (5%3)                  [3,2]       {0:5}
 SNS      Duplicate (2)                 [3,2,2]     {0:5}
 NTSTTN   Jump to Label_FALSE if 0      [3,2]       {0:5}
 NSNN     Jump to Label_LOOP            [3,2]       {0:5}

 SNN      Discard top                   [3]         {0:5}
 SSSTN    Push 1                        [3,1]       {0:5}
 TSSS     Add (3+1)                     [4]         {0:5}
 SNS      Duplicate (4)                 [4,4]       {0:5}
 SNS      Duplicate (4)                 [4,4,4]     {0:5}
 SSSN     Push 0                        [4,4,4,0]   {0:5}
 TTT      Retrieve heap at 0            [4,4,4,5]   {0:5}
 TSST     Subtract (4-5)                [4,4,-1]    {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [4,4]       {0:5}
 SSSN     Push 0                        [4,4,0]     {0:5}
 TTT      Retrieve heap at 0            [4,4,5]     {0:5}
 SNT      Swap top two (4,5] -> 5,4])   [4,5,4]     {0:5}
 TSTT     Modulo (5%4)                  [4,1]       {0:5}
 SNS      Duplicate (1)                 [4,1,1]     {0:5}
 NTSTTN   Jump to Label_FALSE if 0      [4,1]       {0:5}
 NSNN     Jump to Label_LOOP            [4,1]       {0:5}

 SNN      Discard top                   [4]         {0:5}
 SSSTN    Push 1                        [4,1]       {0:5}
 TSSS     Add (4+1)                     [5]         {0:5}
 SNS      Duplicate (5)                 [5,5]       {0:5}
 SNS      Duplicate (5)                 [5,5,5]     {0:5}
 SSSN     Push 0                        [5,5,5,0]   {0:5}
 TTT      Retrieve heap at 0            [5,5,5,5]   {0:5}
 TSST     Subtract (5-5)                [5,5,0]     {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [5,5]       {0:5}

NSSTN     Create Label_TRUE             [5,5]       {0:5}
SSSTN     Push 1                        [5,5,1]     {0:5}
TNST      Output top as number          [5,5]       {0:5}          1
NNN       Stop program                  [5,5]       {0:5}

APL, 9 chars/bytes


get the input


compute least common divisor between n and all integers from 1 to n


count of unique values


if it's exactly 2, then it's prime


GHC 8.2.2, 716 bytes

{-#LANGUAGE FlexibleInstances,FunctionalDependencies,UndecidableInstances,CPP#-}
#define i instance
#define c class
data F
data T
data S n
data C x s
c A p q r|p q->r
i A F q F
i A T q q
c E p x y z|p x y->z
i E F x y y
i E T x y x
c G x y b|x y->b
i G x F T
i G F(S y)F
i G x y b=>G(S x)(S y)b
c M x y z|x y->z
i M x F x
i M F(S y)F
i M x y z=>M(S x)(S y)z
c D x y b|x y->b
i D x F T
i(G(S y)x p,M(S y)x z,D x z q,A p q b)=>D x(S y)b
c K f x y|f x->y
i D m n b=>K(S n)m b
c I f s n|f s->n
i I f F F
i(K f x b,I f s m,E b(S m)m n)=>I f(C x s)n
c R n s|n->s
i R F F
i R n s=>R(S n)(C(S n)s)
c Q m n b|m n->b
i Q F F T
i Q F(S y)F
i Q(S x)F F
i Q x y b=>Q(S x)(S y)b
c P n b|n->b
i(R n s,I(S n)s m,Q m(S(S F))b)=>P n b

Try it online!

This has got to be the most beautiful code I've ever written. It's a compile-time metaprogram that determines whether a type (represented Peano-style, where F is zero and S n is n's successor) is prime.

This works in GHC 8.2.2, the version TIO currently uses. It works locally in 8.8.3 as well. I have included the language extensions in the code, all except one—the TIO example linked above has MonoLocalBinds to suppress a warning. The program works just fine without them.

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

Output has to be written to STDOUT or closest alternative.

As far as I know, metaprograms like this have no means of I/O. With FunctionalDependencies, typeclasses can act much like functions, and in this way, the typeclass P is a "function" from natural numbers to booleans (T and F—yes, the same type represents zero, false, and the empty list). I believe this to be the closest alternative to the standard streams.

The test suite I provided covers numbers from one to twenty. Try changing any T to F or vice-versa, and the program will fail to compile.

I know there are improvements that can be made, and I'll be updating this answer soonish with them.


Arn, 13 12 10 7 bytes


Previous versions:


Try it!


Unpacked: !(1+fact-1)%.

I may add a builtin for checking primality, but until then I made use of Wilson's Theorem; that is, $$((n - 1)! + 1)\mod n\equiv 0$$ will yield true iff n is a prime number.

!                   Boolean Not
    (               Begin expression
        1           Literal one
      +             Addition
        fact        factorial function
            _       Variable initialized to STDIN; implied
          -         Subtraction
            1       Literal one
    )               End expression
  %                 Modulo
    _               Implied

Thank goodness I finally fixed operator precedence.

  • \$\begingroup\$ Finally! You proved that Arn is a programming language. \$\endgroup\$
    – user96495
    Aug 24, 2020 at 1:44
  • \$\begingroup\$ Idea: Add stuff that translates to (( or (((. \$\endgroup\$
    – user96495
    Aug 24, 2020 at 1:46
  • \$\begingroup\$ I do plan on adding a lot more builtins the future, so for the sake of more space I probably won't do anything like that (at least for now). That is a good idea though, Arn's opinionated fix chaining can be very annoying at times :p \$\endgroup\$ Aug 24, 2020 at 1:50
  • \$\begingroup\$ Unfortunately that would evaluate to <s>!(( _.fact / (_ + 1)) % _</s>!((_.(fact / _) + 1) % _). curse you fix chains! \$\endgroup\$ Aug 24, 2020 at 1:54
  • 1
    \$\begingroup\$ Although, that did reveal another bug in my interpreter (naturally). Guess it's time to fix it! \$\endgroup\$ Aug 24, 2020 at 1:55

ARM Thumb, no div instructions, 43 bytes

f7ff fffe represents placeholders for libc calls, to scanf and printf respectively.

b503 4669 a008 f7ff fffe bc03 2802 d907
2202 0001 1a89 d003 d8fc 3201 4282 d1f8
a001 f7ff fffe bd00 6425 00

Assembly code:

        .globl main
        push    {r0, r1, lr}
        mov     r1, sp
        adr     r0, printf_scanf_str
        bl      scanf
        pop     {r0, r1}
        cmp     r0, #2
        bls     .Ltrue
        movs    r2, #2
        movs    r1, r0
        subs    r1, r2
        beq     .Lfalse
        bhi     .Ldivloop
        adds    r2, #1
        cmp     r2, r0
        bne     .Lloop1
        @ movs    r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value
        adr     r0, printf_scanf_str
        bl      printf
        pop     {pc}

        .asciz "%d"

Accepts a number from stdin, and prints nonzero if it is a prime, or zero if it isn't.


Behold, a prime searcher that is so slow you'd swear it was Python.

It is a brute force modulo check using a subtraction loop with zero shortcuts.

Here, we use a trick with push to make space for the scanf output and save the link register.

push will subtract from sp and store the registers in ascending order in memory.

So for example, push {r0, r1, lr} will end up like this:

| sp + 0 | sp + 4 | sp + 8 |
| argc   | argv   | return |

We don't actually care about argc - we care about the space on sp. We can then just pass the stack pointer directly to scanf.

We do sorta care about argv. Not about what it points to, but that it is a valid (non-zero) pointer.

scanf("%d", &r0)

        push    {r0, r1, lr}
        mov     r1, sp
        adr     r0, printf_scanf_str
        bl      scanf

Then, we can pop the result from scanf we stored into r0, and argv into r1 as a "non-zero" value.

        pop     {r0, r1}

Immediately return true for values <= 2. This is exactly why we pushed and popped r1.

        cmp     r0, #2
        bls     .Ltrue

Begin factorizing against 2.

        movs    r2, #2

Use a subtraction loop on a copy of r0 to check if r0 % r2 == 0.

Specifically, the subs will reach zero on an even multiple and set the zero flag (which corresponds to the eq condition). Otherwise, we loop until it underflows (not hi)

        movs    r1, r0
        subs    r1, r2
        beq     .Lfalse
        bhi     .Ldivloop

Increment the number we factor against and loop if it is not equal to r0.

        adds    r2, #1
        cmp     r2, r0
        bne     .Lloop1

Optionally, with the true condition, we set r1 to 1 if it is a prime.

But non-zero is "truthy" enough for us even if it is a little ugly. It will either be the last inverted modulo we tested, or the address of argv, all of which will be non-zero.

Due to how our subtraction loop works, by the time we jump to .Lfalse, r1 will already be zero.

        @ movs    r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value

r1 is already conveniently (and intentionally) in the right place to forward directly to printf, and all we need to do is reload the printf/scanf string to r0 (no easy way around this) and call printf.

Note that due to how pop works in Thumb, it isn't really that useful to do tail calls because we cannot pop directly into lr without a wide instruction.

printf("%d", r1)

        adr     r0, printf_scanf_str
        bl      printf

Last, pop the return address from lr we pushed earlier directly into the program counter to return from main.

        pop     {pc}

JavaScript (ES6), 42 41 bytes


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

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

OCaml, 50 bytes

fun n->List.(init (n-1) succ|>map((mod)n)|>mem 0);;

and it's almost idiomatic and readable.

just sad that init begins at 0 and not 1, could have saved a lot on that :(


Knight, 24 bytes


Prints true for primes, false for composite numbers.

# print the output of the entire body
  # If the number's one, then `&` returns `false`. otherwise we execute the rhs.

    # `>` will coerce `i` to a number, and return `TRUE` unless `x` is one.
      = x (+ 0 PROMPT) # set `x` to the input value
      = i TRUE

    # We know `x` is prime if the first `i` that `%x i` is zero for is `x`.
        # evaluate the while loop then discard it.
        # note that `+ 1 i` will coerce the initial `TRUE` to a `1`.
        WHILE % x (= i + 1 i)
          NULL # ignore the body

        # the return value of `;` is `i` here. It'll be equal to `x` for primes.

///, 145 bytes


Try it online! Outputs 1 for composite numbers (not prime), and nothing for prime numbers. I am very happy I was able to post the first answer in my favorite language on a popular question, with a fairly good score too :)

Takes input in unary asterisks, ie. input = number of asterisks

/~/\/\///$/\\\\~%/+**~I/input here~>**/...
/~/\/\///$/\\\\~%/+**~I/*~>**/...    # 1
/~/\/\///$/\\\\~%/+**~I/**~>**/...   # 2
/~/\/\///$/\\\\~%/+*****~I/*~>**/... # 6

Ungolfed: Try it online!


/>**/.../ Repeats n/2 times, so we don't divide the input by itself

...+**... Starts counter at 2 so we don't divide by 1

If the input is divided evenly by any of the remaining numbers, it is not prime.

We need to "export" the current counter value to outside the loop, because there is no way to only target the counter in the current iteration, since all the iterations are copies of each other. We do this by writing it after the == at the end.

The ^ are escaped /'s in the loop, I unescaped the loop code below

/+\*/-\**/ /-\*/+\*/ Increment counter

/=\=/=\+**|\+\I/ This adds +counter|+input at the end

/+**|\+**/+**|\+ replaces +counter|+counter, which has the effect of repeatedly subtracting the counter from the input, or counter%input. Ex.


/+**|\+/+|/ deletes the +counter, just leaving +|remainder

/=\+/=\= / resets the printer, and deletes the + just leaving |remainder

After the loop, we are left with the remainders of each division, separated by | (in the ungolfed, there are also spaces).

/||/1/ 2 |'s next to each other means the remainder in between was 0

Everything else deletes garbage, or handles edge case stuff with 1 and 2.


tinylisp, 87 bytes

(load lib/math
(d f(q((n k)(i(e n k)1(i(mod n k)(f n(+ k 1))0
(d F(q((n)(f(s n(e 1 n))2

Try it online!

If anyone knows a way to use default arguments in tinylisp, I would very much appreciate it.

This answer only uses the math library and built-ins. It is shorter than the other tinylisp answer's pure version.


Defines f, a function taking in n (main number) and k (factor). Returns 1 if k is equal to n (we have gone through all factors up to n without stopping) and otherwise, we check if n is divisible by k. If so, we return 0, otherwise, we return f called with n and k plus 1.

Then, we define the main function F which takes in only the main number, and sets k to 2.

-10 bytes thanks to @Razetime. -7 bytes thanks to @DLosc. Added some bytes to account for n = 1 case.

  • \$\begingroup\$ lib/math has a prime? function which is still a valid answer. \$\endgroup\$
    – Razetime
    Feb 1, 2022 at 13:21
  • \$\begingroup\$ @Razetime yes, was already covered by another answer. \$\endgroup\$
    – ophact
    Feb 1, 2022 at 13:22
  • \$\begingroup\$ also you can remove all the end of line closing parens \$\endgroup\$
    – Razetime
    Feb 1, 2022 at 13:24
  • \$\begingroup\$ @Razetime Ah, thanks for that. \$\endgroup\$
    – ophact
    Feb 1, 2022 at 13:25
  • 1
    \$\begingroup\$ Sadly, there are no default arguments in tinylisp (unless you use a variadic function and check the number of arguments by hand, which almost certainly costs more bytes). You may be interested in the related language Appleseed, which does support default arguments. \$\endgroup\$
    – DLosc
    Feb 1, 2022 at 18:53

rSNBATWPL, 49 bytes

print{n=input{};(i~cond{n%i}{{i- 1}}$i*i<2)$n- 1}

Recursive solution, as a full program. As a function, it's 34:

n~(i~cond{n%i}{{i- 1}}$i*i<2)$n- 1

Shasta v0.0.8, 31 bytes



{                   ; function($):
  (all              ;   are all truthy (i.e. non-zero):
    (map            ;     map over
      (range 2 $)   ;       the range from 2 to $
      {|a| (% $ a)} ;       function(a): $ mod a
    )               ;     end map
  )                 ;   end all
}                   ; end function

No online interpreter yet, but installation instructions are at the GitHub link and I've run it against several test cases on my machine.


ARBLE, 5 bytes


Try it online!

Slightly more interesting solution, 45 25 bytes


Returns falsey for primes, truthy for non-primes.

Try it online!


TypeScript's Type System, 111 bytes

type P<N,B extends 1[]=[1,1],A=N>=N extends B?1:A extends[...B,...infer I]?P<N,B,I>:A extends[]?0:P<N,[...B,1]>

Try it at the TypeScript Playground!

This is a recursive generic type P taking unary number N as a list of 1s. Outputs 1 if the input is prime, and 0 otherwise. Exception-throws a recursion error for input 1, indicating falsey.

I thought primality test would be a lot longer than it ended up being so I'm pretty pleased.

type P<                    // recursive type P
  N,                       // takes unary number N
  B extends 1[]=[1,1],     // and unary number B which defaults to 2
  A=N                      // A is used to determine divisibility
  N extends B?1            // if B == N, N is prime; return 1
  :A extends[...B,         // else if B fits in A
    ...infer I             //   let I be the difference
  ]?P<N,B,I>               //   recurse with A = I
  :A extends[]?0           // else if A == 0, N isn't prime; return 0
  :P<N,[...B,1]>           // else recurse with B + 1

Uiua, 19 bytes



               ⧻&sc  # ‎⁡pushes n to the stack (read from STDIN in unary)
            =1.      # pushes 1 if n=1, otherwise 0
?¬(        )         # ‎⁢if ^^ = 1, invert the remaining 1 and finish, otherwise run the function in parentheses
      ◿↘2⇡.          # ‎⁣replace n with an array of all n mod k for 1 < k < n
   ¬∊0               # 1 if there is no 0 in that array
  • \$\begingroup\$ Welcome to CG&CC, and great first answer! You can cheat the input format a bit by taking unary input to golf parse to ⧻ for -2 bytes. \$\endgroup\$ Oct 19, 2023 at 5:56
  • 1
    \$\begingroup\$ "if there are any 0s in a list" can be done in two bytes: 0∊. Btw, this code incorrectly classifies 1 as a prime. \$\endgroup\$
    – Bubbler
    Oct 25, 2023 at 4:24

GolfScript, 15 bytes


This uses trial division:

  • stores the input in variable z
  • computes the remainder of dividing z by all numbers from 1 to z
  • expects to find a remainder of 0 exactly 2 times

Try it here.


K, 25 bytes

`0:$~x!1+*/1+!(x:. 0:`)-1
  • 1
    \$\begingroup\$ How should this be run? I tried kona/k program <<< input, but that doesn't seem to work. \$\endgroup\$
    – Dennis
    Sep 11, 2015 at 19:00

Fortran 90, 208 bytes

program a
if(n==2) then
else if(n<2 .or. mod(n,2)<1) then
do i=3,n-1,2
if(mod(n,i)<1) then

This uses trial division. Not a whole lot has been golfed here beyond removing spaces. Here it is with spaces for readability:

program primes
    integer :: n, i
    logical :: p

    ! Read n from STDIN
    read (*,*) n

    if (n == 2) then
        p = .true.
    else if (n < 2 .or. mod(n, 2) == 0) then
        p = .false.
        p = .true.
        do i = 3, n-1, 2
            if (mod(n, i) == 0) then
                p = .false.

    ! Write a logical to STDOUT
    write (*,*) p
end program
  • \$\begingroup\$ Surely need a space before then? \$\endgroup\$ Jul 17, 2016 at 15:49
  • \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Unfortunately yes. \$\endgroup\$
    – Alex A.
    Jul 17, 2016 at 16:13

APL, 13 bytes


Inefficient, but it works. A number is a prime if it is only evenly divisible by 1 and itself, so it just tests all of these. Output is 0 or 1.


          X←⎕  ⍝ read a number, store it in X
      X|⍨⍳      ⍝ X mod [1..X]
  0+.=          ⍝ count the 0s
2=              ⍝ are there 2? 

Lua, 71 67 bytes

n=io.read"*n"for i=2,n-1 do if n%i==0 then r=1 end end print(not r)


for i=2,n-1 do
    if n%i==0 then 
print(not r)

This program just uses trial division to find if a number is prime or not.

3 bytes saved thanks to @Ruth Franklin

  • \$\begingroup\$ You can save a couple of bytes by using r=1 instead of r=true (as not 1 is false anyway) \$\endgroup\$ Sep 13, 2015 at 13:24
  • \$\begingroup\$ Ah okay, thanks for the tip :) \$\endgroup\$
    – Nikolai97
    Sep 13, 2015 at 17:15
  • \$\begingroup\$ Inputs less than 2 (1, 0, and negative numbers) all return true. \$\endgroup\$
    – ECS
    Jan 25, 2016 at 8:33

Perl, 38 or 47 bytes

use ntheory":all";say is_prime(shift);

Prints 0 if composite, 2 if definitely prime, 1 if a probable prime. The results for all 64-bit inputs are deterministic. With 0.53+ this extends to 82-bit inputs. It's also sometimes done for up to 200-bit inputs (special form or very easy proof). The probable prime test is an extra-strong BPSW test followed by 1-5 random-base Miller-Rabin tests.

use ntheory":all";say is_provable_prime(shift);

Uses BLS75-T5 or ECPP to prove the result. Deterministic for all inputs. Very fast to ~500 digits, works pretty well to 1000 or so digits.

This is included in Strawberry Perl for Windows. Certainly using a module is iffy under the golfing loopholes, but this is a normal module and Perl is all about CPAN. It's also ridiculously faster and more useful than the clever but stupid regex.

  • \$\begingroup\$ What does "probably prime" mean? \$\endgroup\$ Sep 11, 2015 at 19:02
  • 2
    \$\begingroup\$ It means it passed some probabilistic prime test that, very rarely, might give a false positive, and you may optionally want to run a more thorough test. \$\endgroup\$
    – Lynn
    Sep 11, 2015 at 19:11
  • \$\begingroup\$ For ntheory, it means it passed an ES BPSW test (that has no counterexamples found in the 35 years since it was introduced) plus one or more extra random-base Miller-Rabin tests. I just added the new result for deterministic M-R testing out to ~82 bits. A bit stronger than Mathematica's PrimeQ function. Primality proofs can be done, but very few people care vs. good probable prime tests. Arguably the chance of failure is smaller than a software or hardware error in the proof code. Not to mention most people want the result for a 2000 digit number in 0.1 seconds instead of 1,5 hours. \$\endgroup\$
    – DanaJ
    Sep 12, 2015 at 5:05
  • \$\begingroup\$ The challenge explicitly asks for non-probabilistic solutions. \$\endgroup\$ Sep 14, 2015 at 10:19
  • \$\begingroup\$ @MartinBüttner Adjusted text and also asked the challenge to be more specific about what "deterministic" means. Thanks. \$\endgroup\$
    – DanaJ
    Sep 14, 2015 at 11:56
3 4
6 7

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.