# 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/… Dec 12, 2017 at 6:21
• @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. Dec 12, 2017 at 12:51
• Could a case be made for locking this challenge and posting a new, less restrictive one? Jun 25, 2018 at 12:59
• @Shaggy Seems like a question for meta. Jun 25, 2018 at 13:44
• Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. Jun 25, 2018 at 13:45

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

Zp


Try it online!

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

# Scratch, 17 blocks (currently glitchy)

demo

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

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

# JavaScript (ES6), 54 bytes

for((x=prompt(a=i=1))>1||a--;++i<x;x%i?0:a=0);alert(a)


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

# Turtlèd, 490 487 451 bytes

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

golfed some bytes for not needing to support 0

Golfed some bytes removing useless code, and some other tricks

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


Try it online!

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

## General explanation:

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

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

### Explanation

code is executed right-to-left

"I"$read0 0 reads STDIN, and then casts it to an integer {..} denotes an anonymous function with x as an implicit variable, applied to the integer til x returns a range 0..(x-1) 2_ drops 0 and 1, which are not needed for prime checking 1,x mod/: then takes mod of x with every element of the list and prepends a 1 to the list due to 1 and 2 returning empty list 0<min takes the minimum of the mods, and checks if it is bigger than zero. If it is, then it must be a prime! • Welcome to PPCG! Mar 7, 2018 at 22:24 # Whitespace, 145137 134 bytes [S S S N _Push_0][S N S _Duplicate][T N T T _Read_STDIN_as_integer_in_heap_0][T T T _Retrieve][S S S T S N _Push_2][T S S T _Subtract][N T T T T N _Jump_to_Label_FALSE_if_negative][S S S T N _Push_1][S N S _Duplicate_1][N S S N _Create_Label_LOOP][S N N _Discard_top_stack][S S S T N _Push_1][T S S S _Add][S N S _Duplicate][S N S _Duplicate][S S S N _Push_0][T T T _Retrieve_heap_at_0][T S S T _subtract][N T S T N _Jump_to_Label_TRUE_if_0][S S S N _Push_0][T T T _Retrieve_heap_0][S N T _Swap_top_two][T S T T _Modulo][S N S _Duplicate][N T S T T N _Jump_to_Label_FALSE_if_0][N S N N _Jump_to_Label_LOOP][N S S T N _Create_Label_TRUE][S S S T N _Push_1][T N S T _Output_1][N N N _Exit][N S S T T N _Create_Label_FALSE][S S S N _Push_0][T N S T _Output_0]  Letters S (space), T (tab), and N (new-line) added as highlighting only. [..._some_action] added as explanation only. Outputs 1 if a prime, 0 otherwise. Try it online (with raw spaces, tabs, and new-lines only). General explanation: 1. Read input 2. Is it less than 2: Return 0 3. Integer i=1 4. Start loop • 5) Increase i by 1 • 6) If the input and i are equal: Return 1 (last iteration of the loop) • 7a) Is the input modulo i 0: Return 0 • 7b) Else: Go back to step 5 Example run (with 5 as input): Command Explanation Stack Heap STDIN STDOUT SSSN Push 0 [0] {} SNS Duplicate (0) [0,0] {} TNTT Read STDIN as number [0] {0:5} 5 TTT Retrieve heap at 0 [5] {0:5} SSSTSN Push 2 [5,2] {0:5} TSST Subtract (5-2) [3] {0:5} NTTTTN Jump to Label_FALSE if neg. [] {0:5} SSSTN Push 1 [1] {0:5} SNS Duplicate (1) [1,1] {0:5} NSSN Create Label_LOOP [1,1] {0:5} SNN Discard top [1] {0:5} SSSTN Push 1 [1,1] {0:5} TSSS Add (1+1) [2] {0:5} SNS Duplicate (2) [2,2] {0:5} SNS Duplicate (2) [2,2,2] {0:5} SSSN Push 0 [2,2,2,0] {0:5} TTT Retrieve heap at 0 [2,2,2,5] {0:5} TSST Subtract (2-5) [2,2,-3] {0:5} NTSTN Jump to LABEL_TRUE if 0 [2,2] {0:5} SSSN Push 0 [2,2,0] {0:5} TTT Retrieve heap at 0 [2,2,5] {0:5} SNT Swap top two (2,5] -> 5,2]) [2,5,2] {0:5} TSTT Modulo (5%2) [2,1] {0:5} SNS Duplicate (1) [2,1,1] {0:5} NTSTTN Jump to Label_FALSE if 0 [2,1] {0:5} NSNN Jump to Label_LOOP [2,1] {0:5} SNN Discard top [2] {0:5} SSSTN Push 1 [2,1] {0:5} TSSS Add (2+1) [3] {0:5} SNS Duplicate (3) [3,3] {0:5} SNS Duplicate (3) [3,3,3] {0:5} SSSN Push 0 [3,3,3,0] {0:5} TTT Retrieve heap at 0 [3,3,3,5] {0:5} TSST Subtract (3-5) [3,3,-2] {0:5} NTSTN Jump to LABEL_TRUE if 0 [3,3] {0:5} SSSN Push 0 [3,3,0] {0:5} TTT Retrieve heap at 0 [3,3,5] {0:5} SNT Swap top two (3,5] -> 5,3]) [3,5,3] {0:5} TSTT Modulo (5%3) [3,2] {0:5} SNS Duplicate (2) [3,2,2] {0:5} NTSTTN Jump to Label_FALSE if 0 [3,2] {0:5} NSNN Jump to Label_LOOP [3,2] {0:5} SNN Discard top [3] {0:5} SSSTN Push 1 [3,1] {0:5} TSSS Add (3+1) [4] {0:5} SNS Duplicate (4) [4,4] {0:5} SNS Duplicate (4) [4,4,4] {0:5} SSSN Push 0 [4,4,4,0] {0:5} TTT Retrieve heap at 0 [4,4,4,5] {0:5} TSST Subtract (4-5) [4,4,-1] {0:5} NTSTN Jump to LABEL_TRUE if 0 [4,4] {0:5} SSSN Push 0 [4,4,0] {0:5} TTT Retrieve heap at 0 [4,4,5] {0:5} SNT Swap top two (4,5] -> 5,4]) [4,5,4] {0:5} TSTT Modulo (5%4) [4,1] {0:5} SNS Duplicate (1) [4,1,1] {0:5} NTSTTN Jump to Label_FALSE if 0 [4,1] {0:5} NSNN Jump to Label_LOOP [4,1] {0:5} SNN Discard top [4] {0:5} SSSTN Push 1 [4,1] {0:5} TSSS Add (4+1) [5] {0:5} SNS Duplicate (5) [5,5] {0:5} SNS Duplicate (5) [5,5,5] {0:5} SSSN Push 0 [5,5,5,0] {0:5} TTT Retrieve heap at 0 [5,5,5,5] {0:5} TSST Subtract (5-5) [5,5,0] {0:5} NTSTN Jump to LABEL_TRUE if 0 [5,5] {0:5} NSSTN Create Label_TRUE [5,5] {0:5} SSSTN Push 1 [5,5,1] {0:5} TNST Output top as number [5,5] {0:5} 1 NNN Stop program [5,5] {0:5}  # APL, 9 chars/bytes 2≡≢∪∨∘⍳⍨⎕  get the input ⎕  compute least common divisor between n and all integers from 1 to n ∨∘⍳⍨  count of unique values ≢∪  if it's exactly 2, then it's prime 2≡  # 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 “sƥNm(┤  Previous versions: ï_C3<│ì♦3(  ├¦&┼6k┐ÇŠq""  {•Õ╝_¸”b¦¤º!E  Try it! # Explained Unpacked: !(1+fact-1)%. I may add a builtin for checking primality, but until then I made use of Wilson's Theorem; that is, $$((n - 1)! + 1)\mod n\equiv 0$$ will yield true iff n is a prime number. ! Boolean Not ( Begin expression 1 Literal one + Addition fact factorial function _ Variable initialized to STDIN; implied - Subtraction 1 Literal one ) End expression % Modulo _ Implied  Thank goodness I finally fixed operator precedence. • Finally! You proved that Arn is a programming language. – user96495 Aug 24, 2020 at 1:44 • Idea: Add stuff that translates to (( or (((. – user96495 Aug 24, 2020 at 1:46 • I do plan on adding a lot more builtins the future, so for the sake of more space I probably won't do anything like that (at least for now). That is a good idea though, Arn's opinionated fix chaining can be very annoying at times :p Aug 24, 2020 at 1:50 • Unfortunately that would evaluate to <s>!(( _.fact / (_ + 1)) % _</s>!((_.(fact / _) + 1) % _). curse you fix chains! Aug 24, 2020 at 1:54 • Although, that did reveal another bug in my interpreter (naturally). Guess it's time to fix it! 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 .thumb .thumb_func main: push {r0, r1, lr} mov r1, sp adr r0, printf_scanf_str bl scanf pop {r0, r1} cmp r0, #2 bls .Ltrue movs r2, #2 .Lloop1: movs r1, r0 .Ldivloop: subs r1, r2 beq .Lfalse bhi .Ldivloop .Ldivloop_end: adds r2, #1 cmp r2, r0 bne .Lloop1 .Ltrue: @ movs r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value .Lfalse: adr r0, printf_scanf_str bl printf pop {pc} printf_scanf_str: .asciz "%d"  Accepts a number from stdin, and prints nonzero if it is a prime, or zero if it isn't. ### Walkthrough Behold, a prime searcher that is so slow you'd swear it was Python. It is a brute force modulo check using a subtraction loop with zero shortcuts. Here, we use a trick with push to make space for the scanf output and save the link register. push will subtract from sp and store the registers in ascending order in memory. So for example, push {r0, r1, lr} will end up like this: | sp + 0 | sp + 4 | sp + 8 | | argc | argv | return |  We don't actually care about argc - we care about the space on sp. We can then just pass the stack pointer directly to scanf. We do sorta care about argv. Not about what it points to, but that it is a valid (non-zero) pointer. scanf("%d", &r0) main: push {r0, r1, lr} mov r1, sp adr r0, printf_scanf_str bl scanf  Then, we can pop the result from scanf we stored into r0, and argv into r1 as a "non-zero" value.  pop {r0, r1}  Immediately return true for values <= 2. This is exactly why we pushed and popped r1.  cmp r0, #2 bls .Ltrue  Begin factorizing against 2.  movs r2, #2  Use a subtraction loop on a copy of r0 to check if r0 % r2 == 0. Specifically, the subs will reach zero on an even multiple and set the zero flag (which corresponds to the eq condition). Otherwise, we loop until it underflows (not hi) .Lloop1: movs r1, r0 .Ldivloop: subs r1, r2 beq .Lfalse bhi .Ldivloop  Increment the number we factor against and loop if it is not equal to r0. .Ldivloop_end: adds r2, #1 cmp r2, r0 bne .Lloop1  Optionally, with the true condition, we set r1 to 1 if it is a prime. But non-zero is "truthy" enough for us even if it is a little ugly. It will either be the last inverted modulo we tested, or the address of argv, all of which will be non-zero. Due to how our subtraction loop works, by the time we jump to .Lfalse, r1 will already be zero. .Ltrue: @ movs r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value .Lfalse:  r1 is already conveniently (and intentionally) in the right place to forward directly to printf, and all we need to do is reload the printf/scanf string to r0 (no easy way around this) and call printf. Note that due to how pop works in Thumb, it isn't really that useful to do tail calls because we cannot pop directly into lr without a wide instruction. printf("%d", r1)  adr r0, printf_scanf_str bl printf  Last, pop the return address from lr we pushed earlier directly into the program counter to return from main.  pop {pc}  ## JavaScript (ES6), 42 41 bytes !/^(.|(.+.)\2+)$/.test(Array(-~prompt()))


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

• Nice! Array(-~prompt()) is a full 3 bytes shorter than 'x'.repeat(prompt()). Did you come up with this? Apr 11, 2021 at 8:20
• Well I see it was used before. Apr 11, 2021 at 8:59
• @Deadcode I came up with it myself but I did not doubt that someone had done it before 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

O&-=x+0P=iT?x;W%x=i+1iNi


Prints true for primes, false for composite numbers.

# print the output of the entire body
OUTPUT
# 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.
?
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.
i


# ///, 145 bytes

/~/\/\///$/\\\\~%/+**~I/*~>**/^=$=^=$%|$+$I^^%|$%^%|$+^^%|$+^+|^^=$+^=$=^^+$*^-$**^^-$*^+$*^>~^/\~/>*~/>~>I/||/1~=\=1~/=\=|=/1~=~/*~/|~/11/1/==|=


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!

Explanation:

/>**/.../ 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.

/+**|+**/+**|+/
+**|+********
gives:
+**|+********
+**|+******
+**|+****
+**|+**
+**|+


/+**|\+/+|/ 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.

## Explanation

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.

• lib/math has a prime? function which is still a valid answer. Feb 1, 2022 at 13:21
• @Razetime yes, was already covered by another answer. Feb 1, 2022 at 13:22
• also you can remove all the end of line closing parens Feb 1, 2022 at 13:24
• @Razetime Ah, thanks for that. Feb 1, 2022 at 13:25
• 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. 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

{(all(map(range2$){|a|(%$a)}))}


Explanation:

{                   ; 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 prime  Try it online! Slightly more interesting solution, 45 25 bytes sum(range(2,n-1)|nt(n%x))  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 ?¬(¬∊0◿↘2⇡.)=1.⧻&sc  Explanation: ?¬(¬∊0◿↘2⇡.)=1.⧻&sc­⁡​‎‎⁪⁡⁪⁠⁪⁤⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁣⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁢⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌­ ⧻&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  • 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. Oct 19, 2023 at 5:56 • "if there are any 0s in a list" can be done in two bytes: 0∊. Btw, this code incorrectly classifies 1 as a prime. Oct 25, 2023 at 4:24 # GolfScript, 15 bytes ~:z,{)z\%!},,2=  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

• How should this be run? I tried kona/k program <<< input, but that doesn't seem to work. Sep 11, 2015 at 19:00

# Fortran 90, 208 bytes

program a
integer::n,i
logical::p
if(n==2) then
p=.true.
else if(n<2 .or. mod(n,2)<1) then
p=.false.
else
p=.true.
do i=3,n-1,2
if(mod(n,i)<1) then
p=.false.
exit
endif
enddo
endif
write(*,*)p
end


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

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

! Write a logical to STDOUT
write (*,*) p
end program

• Surely need a space before then? Jul 17, 2016 at 15:49
• @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Unfortunately yes. Jul 17, 2016 at 16:13

# APL, 13 bytes

2=0+.=X|⍨⍳X←⎕


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.

Explanation:

          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)


Ungolfed:

n=io.read"*n"
for i=2,n-1 do
if n%i==0 then
r=1
end
end
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

• You can save a couple of bytes by using r=1 instead of r=true (as not 1 is false anyway) Sep 13, 2015 at 13:24
• Ah okay, thanks for the tip :) Sep 13, 2015 at 17:15
• Inputs less than 2 (1, 0, and negative numbers) all return true.
– 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.

• What does "probably prime" mean? Sep 11, 2015 at 19:02
• 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.
– lynn
Sep 11, 2015 at 19:11
• 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. Sep 12, 2015 at 5:05
• The challenge explicitly asks for non-probabilistic solutions. Sep 14, 2015 at 10:19
• @MartinBüttner Adjusted text and also asked the challenge to be more specific about what "deterministic" means. Thanks. Sep 14, 2015 at 11:56