Is this number a prime?

Question

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.

Task

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.

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 code-golf 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.

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>

Answer 1

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.

Answer 2

Scratch, 17 blocks (currently glitchy)

demo

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

Answer 3

WolframAlpha, 10 bytes

isprime(n)

Answer 4

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.

Answer 5

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

Answer 6

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!

Answer 7

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:

▌;\│Σ2=

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

Answer 8

Alice, 12 11 bytes

/o|\ntdc
@i

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:

/o|\tzt.
@i

Try it online!

Explanation

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

Answer 9

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

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!

Answer 10

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

Answer 11

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≡

Answer 12

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.

Answer 13

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.

Answer 14

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}

Answer 15

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.

Answer 16

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 :(

Answer 17

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

Answer 18

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

Answer 19

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.

Answer 20

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

Answer 21

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.

Answer 22

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!

Answer 23

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

Answer 24

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

Answer 25

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.

Answer 26

K, 25 bytes

`0:$~x!1+*/1+!(x:. 0:`)-1

Answer 27

Fortran 90, 208 bytes

program a
integer::n,i
logical::p
read(*,*)n
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

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

    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

Answer 28

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? 

Answer 29

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

Answer 30

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.