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

APL, 40 13 bytes

2=+/0=x|⍨⍳x←⎕

Trial division with the same algorithm as my R answer. We assign x to the input from STDIN (⎕) and get the remainder for x divided by each integer from 1 to x. Each remainder is compared against 0, which gives us a vector of ones and zeros indicating which integers divide x. This is summed using +/ to get the number of divisors. If this number is exactly 2, this means the only divisors are 1 and x, and thus x is prime.

Answer 2

Prolog (SWI), 42 40 39 bytes

+X:-X>1,2+X.
Y+X:-X=<Y;0<X mod Y,1+Y+X.

Try it online!

Tests primality by checking whether any of the numbers less than the number and greater than one divide the number.

---

Explanation

+X:-X>1,2+X

defines a new predicate +/1 that is true if X > 1 and 2+X is satisfied. Despite what it appears, this is not an arithmetical expression. It refers to the predicate defined on the next line.

Y+X:-X=<Y;0<X mod Y,1+Y+X.

This defines a new predicate +/2 that is true if X =< Y (Y will never be greater than X, but the =< operator is one byte shorter than the =:= operator which represents equality for arithmetic expressions). If it is not the case that X =< Y then the predicate is true if both X mod Y is not zero (since X mod Y can't be negative, checking that it is greater than zero is sufficient) and 1+Y+X is true. The trick with 1+Y+X is that the two pluses do not end up being used the same way. The + operator is left associative so 1+Y+X is equivalent to (1+Y)+X. Since the expression must be a call to a predicate and +/2 is a predicate that I defined, the interpreter then calls +/2 with arguments 1+Y and X. Thus recursively the program will check whether any Y from 2 to X-1 divides X (it stops at X since X=<Y would be true and so the truth value of the others becomes irrelevant).

Operators in SWI-Prolog

This program heavily abuses the way operators are handled in SWI-Prolog. SWI-Prolog does not define predicates for arithmetic operators such as +. This makes sense since the arithmetical + is not a predicate since the output of a predicate must be true or false. What SWI-Prolog does instead is it builds structures out of the operators and then the predicates that evaluate arithmetic expressions (such as =< and <) know how to evaluate those structures. For instance after the +/2 predicate in my program recurses three times with the initial Y=2 then Y=1+(1+(1+2)) not Y=5. The fact that + is not defined as a predicate means that I can define it as a predicate myself, and since it is an operator I can save the bytes that I would otherwise need to spend on parentheses and commas.

Answer 3

Swift 2.0, 70 100 98 82 77 75 bytes

A simple trial division loop, divided by 2 instead of sqrt() as it takes less bytes! Will default to using 64-bit ints.

let n=Int(Process.arguments[1])!;print(n<4||(2..<n).filter{n%$0<1}.count<1)

Answer 4

Mouse, 65 47 bytes

?N:0S:1I:(I.N.=0=^N.I.\0=[S.1+S:]I.1+I:)S.1=!$

This uses trial division.

Ungolfed:

? N:              ~ Read an integer from STDIN and store it in N
0 S:              ~ Start a summation variable at 0
1 I:              ~ Start an interator variable at 1
( I. N. = 0 = ^   ~ While I != N
  N. I. \ 0 = [   ~ Check whether I divides N
    S. 1 + S:     ~ If so, increment the sum
  ]
  I. 1 + I:       ~ Increment the iterator
)
S. 1 = !          ~ If the sum is 1, the only divisor encountered
                  ~ is 1 (we didn't go all the way to N in the
                  ~ loop) and thus N is prime
$

Answer 5

Dodos, 154 143 136 133 126 122 121 bytes

	N , , + > > D f f
D
	D ,
	N F > > M
M
	M m
	+ B m f
m
	F
	+ B
,
	dip F
	>
F
	+ B f
f
	+ >
	+
B
	N
N
	B dip
+
	dot
>
	dab

Try it online!

Builtins and aliases

+
	dot

This creates an alias + for the builtin function dot, which maps the vector (v₁, ..., v_n) to the vector (v₁ + ... + v_n), i.e.,

>
	dab

This creates an alias > for the builtin function dab, which maps the vector (v₁, ..., v_n) to the vector (v₂, ..., v_n).

dip

The remaining builtin, dip, maps the vector (v₁, ..., v_n) to the vector (|v₁ - 1|, ..., |v_n - 1|).

B and N

B
	N
N
	B dip

This defines a pair of mutually recursive functions. Recall that Dodos only divide or surrender.

B, if called from outside this function group, is meant to take a pair (x, y) as argument. B(x, y) simply calls N(x, y). This will always succeed, because all calls to N go through B.

N(x, y) attempts to call B(|x - 1|, |y - 1|). The tuple inequality (|x - 1|, |y - 1|) < (x, y) holds if an only if x > 0, so N(0, y) will return (0, y), since B(1, |y - 1|) surrenders.

Whenever x ≤ y, calling B(x, y) simply decrements both coordinates x times before surrendering, returning (0, y - x). If x > y, both coordinates will still be dipped x times. However, once the second coordinate reaches 0, it will cycle between 0 and 1, resulting in (0, (x - y) % 2).

N, if called from outside this function group, is meant to take a singleton (x) as argument. N(x) calls B(|x - 1|), which calls simply N(|x - 1|).

N(0) calls B(1), which attempts to call N(1). This surrenders, so B(1) returns 1, and so does N(0).

Whenever x > 0, N(x) will decrement x until reaching N(1) → B(0) → N(0) → B(1). Since B(1) surrenders, N(0)'s argument is the return value of N(x).

Thus, N(0) = 1, while N(x) = 0 whenever x > 0.

F and f

F
	+ B f
f
	+ >
	+

f returns the results of + > and + as a vector; + > takes the sum of the vector without its first coordinate, while + takes the sum f the whole vectors.

Thus, f(v₁, ..., v_n) = (v₂ + ... + v_n, v₁ + ... + v_n).

On occasions, we'll call f outside of F. Notably, f(x) = (0, x), f(0, x) = (x, x), and
f(x, y) = (y, x + y)

F simply calls three functions we've seen before. Since v₂ + ... + v_n ≤ v₁ + ... + v_n, B maps the result returned by f to (0, v₁). + takes the sum, returning (v₁).

Thus, calling F on a vector returns its first coordinate.

,

,
	dip F
	>

dip F dips the first coordinate of the argument vector, while > returns the remaining coordinates. Thus, , maps (v₁, ..., v_n) to (|v₁ - 1|, ..., v_n).

In particular, , maps (x) to (|x - 1|), so we can use it instead of dip for singleton vectors.

M and m

M
	M m
	+ B m f
m
	F
	+ B

m is always meant to be called on a pair. It simply combines a few functions we've seen before. Recall that B behaves differently if x ≤ y and if not.

We have m(x, y) = (x, y - x) if x ≤ y but m(x, y) = (x, (x - y) % 2) otherwise.

M is always meant to be called on a pair, whose first coordinate will be non-zero. M attempts to recursively call itself on the result of m. Since m doesn't change the first coordinate of its argument, we only need to examine the second one.

On the second line, B(m(f(x, y))) = B(m(y, x + y)) = B(y, x). After + takes the sum, we get x - y if x ≥ y, but (y - x) % 2 otherwise.

If y = qx, M(x, y) = M(x, qx) will successively call M(x, (q - 1)x), M(x, (q - 2)x), ..., M(x, x), M(x, 0). At the end, M(x, 0) attempts to recursively call itself, which surrenders. The return value is (x, 0), concatenated with all singletons returned by the second line. Since the second line maps (x, x) to 0, the result of M(x, y) will match the pattern (x, 0, 0, ...).

If y = qx + r, with 0 < r < x, we'll proceed in similar fashion, eventually reaching M(x, x + r), then M(x, r).

• If r = 1 and x is even, m(x, r) = (x, (x - r) % 2) = (x, 1), and the recursive call to M surrenders. In the previous call, the second line mapped (x, x + r) to (x + r - x) % 2 = 1, so the result of M(x, y) will match the pattern (x, 1, 1, ...).

• If r = 1 and x is odd, m(x, r) = (x, (x - r) % 2) = (x, 0), and the recursive call to M succeeds.

  Likewise, if r > 1, then m(x, r) = (x, (x - r) % 2) ≤ (x, 1) < (x, r), and the recursive call to M succeeds.

  In both cases, the second line will be evaluated for the last time with argument (x, t). Since we have t < r < x, the outcome is the non-zero vector (x - t), so the result of M(x, y) will match the pattern (x, ?, x - t, ...).

Thus, the third element of the vector returned by M(x, y) will be 0 if and only if x is a divisor of y.

D

D
	D ,
	N F > > M

D expects (n, n) as its initial argument.

The first line will recursively call D on the result of ,, so we'll call D(n, n) → D(n - 1, n) → ... → D(1, n) → D(0, n) → D(1, n), surrendering and returning (0, n).

The second line will be evaluated for every (k, n), with 0 < k ≤ n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns (k, ?, 1, ...) if k is a divisor of n, (k, ?, 0, ...) otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., n | n).

main

	N , , + > > D f f

Our entry point expects a singleton (n), with n > 0.

Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., n | n).

After discarding (0, n) with > >, a call to + takes the sum of the Booleans, counting the number of divisors of n.

, , dips the divisor count twice, resulting in a 0 only for zero or two divisors. Since n > 0, there is at least one divisor, so the result is 0 if and only if n has exactly two divisors.

Finally, N takes the logical NOT, returning 1 for primes and 0 for non-primes.

Answer 6

><>, 25 + 3 = 28 bytes

:1-:v
v!?:<-1$**:@:
>r%n;

Inputting as a byte with i is shorter, but ><> can handle numbers larger than 255, hence the need for command line input in order to follow the rules. The +3 is for the v flag, i.e. run like

py -3 fish.py primes.fish -v 101

Outputs (n-1)*((n-1)!)^2 mod n (the initial (n-1)* is unnecessary, but it makes the code shorter).

Answer 7

gs2, 2 bytes

Vk

Basically read-num is-prime.

Answer 8

C, trial division, 72 bytes

i=1;main(n){for(scanf("%d",&n);n%++i&&i*i<n;);printf("%d",n<3?n-1:n%i);}

Note special handling for n=1,2

We need to stop the loop before i gets to n-1, so i<n-1 would do, but i*i<n is more efficient.

Answer 9

Sesos, 50 49 bytes

Algorithm #3...

0000000: 16def7 f5991b 7441bf 3f0ebb eecfd8 b86b33 b7eb33  ......tA.?......k3..3
0000015: 37ecda bccdd8 b86b33 3ffcfe 8c7de8 797cfc f599c3  7......k3?...}.y|....
000002a: f973f5 8479c5 03                                  .s..y..

Try it online!

This is the very first working code I got, so I'm sure it's possible to shave off a few more bytes here. Here's the BF-code I wrote (with some rather sparse comments that are mostly meant for myself):

,
[>+>+>+<<<-]                ; triplicate input
>>[-                        ; i from n_1 down to 0
    <+[-<<<+>>>             ; j from n down to 0 copying n to the left
        [                   ; k from j down to 1
            >[<<+<+>>>-]    ; add i to the values on the left
            <<[>>+<<-]      ; move one copy of i back
            >>>>+<<<-       ; decrement k while copying j to the right
        ]
        >>[<<+<<->>>>-]     ; subtract n from i*j while copying it
        <<[>>+<<-]          ; move n back
        >>>[<<<+>>>-]       ; move j back
        <<<<<[              ; if not equal:
            ,               ; reset to zero
            >               ; move to zero left of j
        ]
        >
    ]
    <<<[>>>+<<<-]           ; move n back to j
    >[<]>>>                 ; if we didn't exit move back to i
                            ; otherwise remain on the zero left of j
]
>,+>-[<->,]<.

I then used this Retina script to convert that to Sesos ASM:

set numin
set numout

get
jmp
   fwd 1
   add 1
   fwd 1
   add 1
   fwd 1
   add 1
   rwd 3
   sub 1
jnz
fwd 2
jmp
   sub 1
   rwd 1
   add 1
   jmp
      sub 1
      rwd 3
      add 1
      fwd 3
      jmp
         fwd 1
         jmp
            rwd 2
            add 1
            rwd 1
            add 1
            fwd 3
            sub 1
         jnz
         rwd 2
         jmp
            fwd 2
            add 1
            rwd 2
            sub 1
         jnz
         fwd 4
         add 1
         rwd 3
         sub 1
      jnz
      fwd 2
      jmp
         rwd 2
         add 1
         rwd 2
         sub 1
         fwd 4
         sub 1
      jnz
      rwd 2
      jmp
         fwd 2
         add 1
         rwd 2
         sub 1
      jnz
      fwd 3
      jmp
         rwd 3
         add 1
         fwd 3
         sub 1
      jnz
      rwd 5
      jmp
         get
         fwd 1
      jnz
      fwd 1
   jnz
   rwd 3
   jmp
      fwd 3
      add 1
      rwd 3
      sub 1
   jnz
   fwd 1
   jmp
      rwd 1
   jnz
   fwd 3
jnz
fwd 1
get
add 1
fwd 1
sub 1
jmp
   rwd 1
   sub 1
   fwd 1
   get
jnz
rwd 1
put

And of course the final conversion to binary is done by Sesos itself.

I scrapped three earlier attempts for trial division, and ultimately really got tired of the modulo computation. So I started thinking about how I could avoid that altogether. I ended up coming up with a very simple primality test, that for some reason never occurred to me before and might be handy for a lot of other esolangs where doing a multiplication is fine but computing a modulo is a royal pain:

In essence, I just compute the full multiplication between [1, ..., n-1] and [1, ..., n] starting from the largest value. After each multiplication, I subtract n from the result. If that gives 0, I terminate. This is bound to terminate, because at the beginning of the final iteration of the outer loop, I'm computing 1 * n. If I get there, it's a prime. Otherwise, some earlier multiplication will have given n and the loop stops there instead. That means I can simply check after terminating whether the first iterator is equal to 1 or not in order to decide primality.

I'll probably post the Brainfuck-version of this as well, once I'm happy with the golfing.

Answer 10

Cheddar, 37 bytes

Looks like a full program is required which unfortunately means a lot of boilerplate:

print Math.prime(Number::IO.prompt())

This might not work on TIO so you'd have to put it into a file and call it that way

Function, 10 bytes

Math.prime

This returns a function which checks if input is prime using Math.prime. Example:

$ cheddar primechecker.cheddar -x "[1, 3, 4, 10, 13] => (print) + f"

Answer 11

Python 2, 46 bytes

m=n=input()
a=1
while~-m:m-=1;a*=m*m
print a%n

Answer 12

Fourier, 44 bytes

Guess who? :D

1~h2~xI~g<3{1}{5+g~g}g(g%x{0}{~hgv~x}x^~x)ho

Yes, it's my very own Fourier again, in a situation where it is actually in the running for a golfing competition.

The most bytes are spent on handling the input cases for 1 and 2.

Prints "1" for True and "0" for False.

Explanation

1~h                                            # Set h to 1
   2~x                                         # Set x to 2
      I~g                                      # Set g to user input      
         <3{1}{     }                          # If accumulator is less than three then
               5+g~g                           # Add 5 and g and set g to that value  
                     g(                  )     # Loop until the accumulator equals g
                       g%x{0}{      }          # If g%x equals 0, then
                              ~hgv~x           # Set h to 0 and set x to g-1
                                     x^~x      # Increment x and set x to that value
                                           ho  # Output the value of h

Answer 13

Matlab/Octave 24

It is just using a builtin function, using a sieve.

disp(isprime(input('')))

You could also use this:

isprime(input(''))

Which would print the output as the last result in the console, but I am not sure whether this is allowed.

Answer 14

Python 3, 52 bytes

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

Saved a byte thanks to xnor in chat.

Answer 15

ShapeScript, 53 25 23 bytes

_11?1-"@1?*@1-"1?*!?*@%

The program uses Wilson's theorem; it prints 1 for primes and 0 for non-primes. Input is in unary.

I created ShapeScript for this competition. The interpreter on GitHub has a slightly modified syntax and better I/O (none of which are required in this answer).

Try it online!

How it works

_        Take the length of the input to convert from unary to integer (N).
1        Push 1 (accumulator).
1?1-     Push a copy of N and subtract 1. Let's call the result I.
"        Push a string that, when evaluated, does the following:
  @        Swap I with the accumulator.
  1?       Push a copy of I.
  *        Multiply it with the accumulator.
  @        Swap the updated accumulator with I.
  1-       Decrement I.
"
1?       Push a copy of N-1.
*!       Repeat the string N-1 times and evaluate the result.
         This calculates (N-1)! and leaves I = 0 on the stack.
?        Use I to copy the factorial.
*        Multiply to calculate the factorial's square.
@%       Calculate N%((N-1)!*(N-1)!).

Answer 16

Reflections, 194 181 bytes

  _v@\
|* / (0    /\
   /;*      <
/0):\(1/# + /#+\
:  ; >~<   \ _ /
#|v\/ 1)
(0*    \#:(1 \
\\#  \(0__0) /
 _  / (0\
/^^: 0):/
\#+ _#_
/0):^\
:  / /
#
(0 >#* _#_
\ _<
   \        /

Test it!

Outputs 1 for prime, else 0.

Explanation

First we parse the number:

  _v@\
|* / (0
     *
     (1/ -> IP leaves here
     >~<
      1)
       \#:(1 \
     \(0__0) /

• _ reads a line from input
• v reflects the IP down
• / reflects the IP left
• * at (1|1) pushes 1×1=1
• | reflects the IP right
• * pushes another 1
• / reflects the IP up
• v pops a value off the stack and reflects the IP right as it's true
• @ at (4|0) converts all input to numbers
• \ reflects the IP down
• (0 moves the first digit to stack 0
• * at (5|2) pushes 5×2=10
• (1 moves the 10 to stack 1
• > reflects the IP right
• ~ pushes the number of left digits
• < pops that number and reflects the IP down if it's not 0:
  • 1) moves the 10 from stack 1 to the main stack
  • \ reflects the IP right
  • # redefines (0|0)
  • : doubles the 10
  • (1 moves the top 10 to stack 1 again
  • \ reflects the IP down
  • / reflects the IP left
  • 0) pulls the previous result from stack 0
  • _ at (1|1) multiplies the previous result and 10
  • _ at (0|1) adds the next digit
  • (0 pushes the result to stack 0
  • \ reflects the IP up
  • > enters the loop again
• if it's zero, reflect the IP up
  • / reflects the IP right

Now, we have the test number on stack 0.

Then, we initialise the loop:

            <
       /# + /

• / reflects the IP right
• # redefines (0|0)
• + at (2|0) pushes 2+0=2
• / reflects the IP up
• < reflects the IP left

Now, we have a 2 (the counter) on the main stack and the input number on stack 0.

Then we have the real loop:

           /\
   /;*      <
/0):\       /#+\
:  ;       \ _ /
#|v\/
(0*
\\#
 _  / (0\
/^^: 0):/
\#+ _#_
/0):^\
:  / /
#
(0 >#* _#_
\ _<
   \        /

• * pushes x×y
• ; pops that again
• / reflects the IP down
• : duplicates the counter
• ; discards the duplicate
• \ reflects the IP right
• / reflects the IP up
• \ reflects the IP left
• : duplicates the counter again
• 0) pulls the input number from stack 0
• / reflects the IP down
• : duplicates the input
• # redefines (0|0)
• (0 pushes the duplicated input to stack 0
• \ reflects the IP right
• \ reflects the IP down
• _ at (1|3) pops the counter and the input and pushes whether they're equal
• ^ pops the test and reflects the IP left if true (i.e. if we have tested all numbers less than the input and haven't found a factor → the number is prime):
  • / reflects the IP down
  • \ reflects the IP right
  • # redefines (0|0)
  • + at (1|0) pushes 1+0=1
  • _ at (3|0) converts to string
  • # redefines (0|0)
  • _ at (1|0) prints
  • then the IP leaves the grid and the program ends
• else the IP is reflected right:
• ^ reflects the IP up
• # redefines (0|0)
• * pushes 0×-1=0
• v pops the 0 and reflects the IP left
• | reflects the IP right
• v reflects the IP down
• * pushes 0×-1=0
• # redefines (0|0)
• ^ pops the zero and reflects the IP right
• : duplicates the counter
• 0) pulls the input from stack 0
• : duplicates it
• / reflects the IP up
• \ reflects the IP left
• (0 pushes the duplicated input to stack 0
• / reflects the IP down
• _ at (2|3) checks if the input is greater than the counter. Note that this is only false if the input is 1 as else the previous check applies before.
• ^ reflects the IP right if the check was false (i.e. input is < 2):
  • \ reflects the IP down
  • / reflects the IP left
  • / reflects the IP down
  • > enters the 'output zero' part, see below
• else the IP is reflected left:
• : duplicates the counter (once again)
• 0) pulls the input from stack 0 (once again)
• : duplicates the input (once again)
• # redefines (0|0)
• (0 pushes the input to stack 0 (once again)
• \ reflects the IP right
• _ at (2|2) pops input and counter and pushes input modulo counter
• < pops the result and reflects the IP up if 0 (it's a factor):
  • > reflects the IP right into the 'output zero' part, see below
• else (it's no factor) the IP is reflected down:
• \ reflects the IP right
• / reflects the IP up
• / reflects the IP right
• # redefines (0|0)
• + at (1|0) pushes 1+0=1
• \ reflects the IP down
• / reflects the IP left
• _ at (0|1) adds the 1 to the counter (counter++)
• \ reflects the IP up
• / reflects the IP right
• \ reflects the IP down
• < enters the loop again

Now for the 'output zero' part:

   >#* _#_

• > reflects the IP right
• # redefines (0|0)
• * at (1|0) pushes 1×0=0
• _ at (3|0) converts to string
• # redefines (0|0)
• _ at (1|0) prints '0'
• then the IP leaves the grid and the program ends

Answer 17

naz, 334 318 316 311 307 bytes

Original solution:

2x2v
1x0f0v1s2x0v1v1s2x1v2v3x1v0l
1x1f2v1o
1x4f0v1a2x0v1v1s2x1v2v3x1v4l
1x5f3v2x1v0f2v3x0v5l9v3x2v2g2v
1x3f5v2x0v8v2x9v3v1s2x3v5f0v3x2v1e2v2a3x3v3l8f
1x2f9v1s2x9v0v9a9a9a9a9a9a9a9a9a9a9a1a2x0v5f
1x6f1r8s8s8s8s8s8s
6f2x8v
6f5m2m2x0v
6f2x1v
2v3x1v4l0v2x5v2v2x0v    
1x7f5v2x3v1s3x2v1e1s3x2v8e3f
1x8f2v1a1o
1x9f2v9a9a9a9a2x3v8v1s3x2v7l3f
9f

Only works after the current bugfixes to naz so it doesn't work here yet. As I'm not a good golfer and naz is cryptic enough, I didn't try to reduce the number of bytes further. I'm convinced there are multiple bytes to be shaved off somewhere.

Input

This program takes any three-digit natural number (001 to 999) as a command line argument in decimal representation.

Output

This program writes output: 0 for non-primes and output: 1 for primes output: is a constant output by the naz-interpreter that cannot be suppressed.

Truthy and falsy values don't exist in naz, as naz does not have a construct like if(b), so I used 0 and 1 as common falsy / truthy values. One can easily change them to any other string / number by modifying 1f (for false) and 8f (for true)

How it works

naz's only datatype is a signed byte from +127 to -127. When this limit is exceeded, the interpreter halts the execution immediately. So in order to test all three digit natural numbers (including those > 127), I used 2 variables for a combined number, having the hundreds in one variable and the ones in another.

For example: The number +540 would be separated in two bytes, 5 and 40.

naz has 9 register / variables that will do all of the calculation in this program. I'll refer to them as [0] (value of variable 0) to [9] (value of variable 9). If I'm combining two variables to create a bigger number, i'll refer to it as [8]::[5] (the number generated by [8] * 100 + [5] that cannot be represented in naz's data format)

Line by Line

2x2v: initial Setup. Naz doesn't have the constant 0 anywhere, except for the accumulator at the start of each program. I decided for my whole program that [2] should be 0 to give me access to that constant.

1x0f0v1s2x0v1v1s2x1v2v3x1v0l: function f0: [0] -= [1], [1] := 0. This function assumes [1] > 0.

1x1f2v1o: f1: print 0. This is my false function. It can be modified to print any falsy value.

1x4f0v1a2x0v1v1s2x1v2v3x1v4l: f4: [0] += [1], [1] := 0. This function assumes [1] > 0

1x5f3v2x1v0f2v3x0v5l9v3x2v2g2v: f5: calculate the remainder of [9]::[0] divided by [3] by repeated subtraction. Note that there will always be the negative value of the remainder, for example 5 % 3 = -1. Also note that [9]::[0] will be destroyed in this process and [0] will contain the remainder afterwards. [3] will not be modified. Calls f0 for the subtraction and f2 to handle carry-bit arithmetic.

1x3f5v2x0v8v2x9v3v1s2x3v5f0v3x2v1e2v2a3x3v3l8f: f3: The main prime-testing function: copies [8]::[5] to [9]::[0] (as expected by f5), decrements [3] calls 5f to calculate the remainder, ends the whole loop if [0] == 0 (i.e. [8]::[5] is divisible by [3]) by calling f1, continues the loop if [3] > 2 (note that [3] is decremented before calling f5, so this will test divisible by 2 iff [3] == 3 at this point in time. Call f8 (true function) if no other conditional hit (i.e. `[0] != 0 && [3] <= 2)

1x2f9v1s2x9v0v9a9a9a9a9a9a9a9a9a9a9a1a2x0v5f: f2: The carry-bit function. reduces [9] by 1 and increments [0] by 100. Calls f5 again afterwards as conditionals in naz do not result in function calls, so there's no jump back into 5f without this.

1x6f1r8s8s8s8s8s8s: f6: The input function: as '0' is 48, subtract 48 from the character read to get its numerical value in the accumulator.

6f2x8v: Read the hundreds and write them to [8].

6f5m2m2x0v: Read the tens, multiply them by ten and write them to [0]

6f2x1v: Read the ones, write them to [1]

2v3x1v4l0v2x5v2v2x0v: Call f4 iff [1] > 0, move [0] to [5], reset [0] := 0

1x7f5v2x3v1s3x2v1e1s3x2v8e3f: f7: Handle special cases. The general idea in this program is that any 3 digit number that is not a prime has to have at least one divisor in (2, 100). However, even primes smaller than 100 will have one divisor in (2, 100), themselves. This function only gets called if [8] == 0, i.e. [8]::[5] < 100, so instead of starting at a predetermined divisor we start at [5] (note that f3 will decrement [3] before checking divisibility). If [8] == 1, we jump to f1 (FALSE), if [8] == 2 we jump to f8 (TRUE) otherwise we continue with the prime-check function 3f.

1x8f2v1a1o: f8: My true function. As with f1, can be easily modified to do whatever we want if this number is a prime.

1x9f2v9a9a9a9a2x3v8v1s3x2v7l3f: f9: Setup [3] := 36 (as 35**2 > 1000). Goto f7 iff [8] == 0 (special cases), else call f3

9f: Execute 9f.

Edits

-16 bytes by replacing 0v9a9a9a9a9a9a9a9a9a9a9a1a2x0v (30 bytes) with 2v5a4m5m2x1v4f (14 bytes) in 2f

-2 bytes by replacing 8v1s3x2v7l with 8v3x2v7e in 9f

-5 bytes by removing all unnecessary '\n' (I really, really do miss them). That is the newline after 2x2v(1 byte), all of the initializing calls to 6f (3 bytes) and after 2v3x1v4l0v2x5v2v2x0v (1 byte)

-4 bytes by replacing 9a9a9a9a with 9a4m in 9f

Final Version

2x2v1x0f0v1s2x0v1v1s2x1v2v3x1v0l
1x1f2v1o
1x4f0v1a2x0v1v1s2x1v2v3x1v4l
1x5f3v2x1v0f2v3x0v5l9v3x2v2g2v
1x3f5v2x0v8v2x9v3v1s2x3v5f0v3x2v1e2v2a3x3v3l8f
1x2f9v1s2x9v2v5a4m5m2x1v4f5f
1x6f1r8s8s8s8s8s8s
6f2x8v6f5m2m2x0v6f2x1v2v3x1v4l0v2x5v2v2x0v1x7f5v2x3v1s3x2v1e1s3x2v8e3f
1x8f2v1a1o
1x9f2v9a4m2x3v8v3x2v7e3f
9f

Answer 18

Minecraft 1.12.2 (expandable), 5446 bytes per bit (1-255 version: 49014 bytes)

6 wide x 16 high x 44 long structure composed of two files, pchk_v1_1_front.nbt (3705 bytes) and pchk_v1_1_back.nbt (1741 bytes).

pchk_v1_1_front.nbt

pchk_v1_1_back.nbt

Less golfed:

8 bit version:

Notes on setting up

• Each module can be pasted right next to the last one, with no gap in between. No extra work is needed, however sometimes it is easier to replace the granite blocks with glass before copying & pasting, then to replace them back to a solid block afterwards. This prevents certain key observers from firing on clone/paste/fill/etc..

• When making a machine larger than 8 bits, the default timings may not be long enough. For any delay that scales with the number of modules, a long delay circuit is used. Increasing the number of items in each hopper should fix the problem just fine.

Operating the machine

1. Input the number to be checked as a signed (two's complement) integer. Only strictly positive inputs are valid for the challenge, but internally the machine requires signed integers in the trial division process. Do not change the input while the machine is running.
2. Connect a button to the rightmost end of the SYNC wire (pictured above) and press it once to run the machine. There is a built-in delay right at the start, so there is no need to wait for the machine to finish updating from the input changing before starting.
3. When the left lamp turns on, the machine has finished running. The right lamp is on when the input is prime, and off when it is not. Don't worry if it takes a while-- at 500 TPS (using Carpet mod /tick rate), checking the primality of the number 127 took around 7 minutes.

Explanation

Each module is composed of a few components:

• Input / Number (magenta)
• Divisor (light blue)
• Divider (orange)
• Control logic / SYNC pipeline (pink)
• Output lamps, connections between components, etc.

The button pressed to start computation connects directly to the SYNC wire, which starts the control logic on all modules on the exact same tick. The control logic implements the following pseudocode:

<SYNC pulse>

reset output

Number == 1:
    light Done
    <end of path>

Number != 1:
    reset Divisor + lock Number into Divisor

loop:
    decrement Divisor

    ; Now, Number >= 2 and Divisor = Number - 1.
    ; We check if Divisor divides Number until it does (composite), or until
    ; Divisor is 1 (prime). We have to check the latter first each loop 
    ; iteration as when Number is 2, Divisor starts at 1.

Divisor == 1:
    light Prime
    light Done
    <end of path>

Divisor != 1:
    check if Divisor divides Number

Divides:
    light Done
    <end of path>

Does not divide:
    goto loop

The divider implements its own logic as follows (repeated subtraction with State storing the current state):

divloop:
    reset State + lock Number into State
    ; Divisor is hardcoded into the divider
    
    ; When State - Divisor results in State's bit flipping, the T flip flop is
    ; toggled. Otherwise, State remains the same.
    update State
    
    State < 0:
        ; negative -> does not divide
        return DND
    
    State > 0:
        ; Could still be zero, keep going
        ; (no extra work needed here)
    
    State == 0:
        ; zero -> divides, n is composite
        return DIVIDES
         
    State != 0:
        goto divloop

Notes

• The module could probably be golfed down quite a bit further, if anyone wants to try.
• An analog (comparator) version might be smaller and would definitely be much faster than the current binary version.

Answer 19

Foo, 40 bytes

&1@@@>>&>&1<(2-1@<<@>&%+1@>>%<)&2/@>+%$i

Probably not the best approach, but I wanted to give it a try. Thanks to the "wonders" of Foo's do-while loops, I had to special case 1 and 2, both of which output errors to STDERR (but STDOUT output is correct).

The input is hardcoded as the number after the first &.

Answer 20

Bubblegum, 98 bytes

from math import factorial as F#
try:n=int(i)-1;o=n*(F(n)%-~n==n)
except:o=sum(map(int,i.split()))

This prints p - 1 if p is prime and 0 otherwise.

It may not look like it, but this is the shortest known Bubblegum program that achieves this task.

There are probably shorter programs, but their discovery would require a cryptographic break of the SHA-256 hash.

Answer 21

Perl, 23 20 bytes

say/^(?!(..+)\1+$)/

using -n option.

say<>=~/^(?!(..+)\1+$)/

Using the regular expression+unary input approach, prints 11 (or whatever number you entered) or a blank line.

Bonus: decimal version, 31 bytes

(1x<>)=~/^1$|^(11+)\1+$/||say 1

Answer 22

FRACTRAN, 144 bytes

29/14 222/377 59/26 247/59 329/57 19/47 2/19 11/29 403/407 217/33 11/31 2/11 1/37 1/2 23/9 43/69 23/43 1/23 425/41 4823/85 17/53 41/25 2/119 1/5

This took me way longer than expected - special casing 1 was pretty annoying. Takes 5^n as input and outputs 3^0 = 1 (falsy) if composite, or 3^1 = 3 (truthy) if prime.

The approach is similar to Conway's prime generator, performing a divmod on descending divisors. This isn't as compact though, so there's still much to golf.

Answer 23

JavaScript (ES6), 47 bytes

alert(!/^(11+)\1+$/.test('1'.repeat(prompt())))

Answer 24

PowerShell, 35 Bytes

param($a)$a-match'^(?!(..+)\1+$)..'

Uses the same regex from Martin's Retina answer, as that's way shorter than anything that will wind up using the [math]:: libraries one would normally use. Expects input as command-line argument in unary format.

Corrected from initial version (which was apparently specific to the particular PowerShell implementation I coded it on) thanks to Jonathan Leech-Pepin. Grr undocumented version differences.

Examples:

PS C:\Tools\Scripts\golfing> .\is-this-number-a-prime.ps1 111111
False

PS C:\Tools\Scripts\golfing> .\is-this-number-a-prime.ps1 1111111
True

---

Bonus - PowerShell pipeline input, 29 Bytes

%{$_-match'^(?!(..+)\1+$)..'}

Same as the above, just called differently, which shaves bytes. For example,

PS C:\Tools\Scripts\golfing> 111111 | %{$_-match'^(?!(..+)\1+$)..'}
False

Answer 25

Sesos, 67 66 65 bytes

Edit: Saved a byte by using another get instead of a loop.

Edit: Saved a byte because I don't need this rwd 6 after I changed from sub 1 to add 1 before it.

Try it online

The hexdump:

0000000: 16f8be 76ca83 e653e3 b472f0 750ef0 af9f1f fcebbb  ...v...S..r.u........
0000015: 7f7ec6 77e13b bf41f7 2961f0 af9f1f fcebbb 7f6ec7  .~.w.;.A.)a........n.
000002a: 3fc013 ef9da3 a0fbbc 77ecc7 776e1b bf73b8 576a9c  ?........w..wn..s.Wj.
000003f: 663e                                              f>

This is the Sesos assembly code that I wrote, which is assembled into the above binary to be executed:

set numin
set numout
get

jmp     ; n += (n==2)
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz
add 2
fwd 1
jmp
sub 1
rwd 1
sub 1
fwd 1
jnz
add 1
rwd 1
jmp
fwd 1
sub 1
rwd 1
get
jnz
fwd 1
jmp
sub 1
fwd 1
add 1
rwd 1
jnz
fwd 1

jmp     ; list from n to 1
jmp
sub 1
fwd 3
add 1
rwd 3
jnz
fwd 3
jmp
sub 1
fwd 3
add 1
rwd 6
add 1
fwd 3
jnz
fwd 3
sub 1
jnz

rwd 6   ; List [n, n-1, ..., 2, 2]. We don't want n%1.
add 1
jmp
rwd 6
jnz
fwd 6

jmp     ; move n one cell to the left
sub 1
rwd 1
add 1
fwd 1
jnz

add 2   ; copy the n's
jmp
rwd 1
jmp
sub 1
fwd 3
add 1
rwd 3
jnz
fwd 3
jmp
sub 1
fwd 3
add 1
rwd 6
add 1
fwd 3
jnz
fwd 4
jnz
rwd 7

jmp     ; compute each divmod, only the n%d results will be used
jmp
sub 1
fwd 1
sub 1
jmp
fwd 1
add 1
fwd 2
jnz
fwd 1
jmp
add 1
jmp
sub 1
rwd 1
add 1
fwd 1
jnz
fwd 1
add 1
fwd 2
jnz
rwd 5
jnz
rwd 6
jnz
fwd 8

jmp     ; go to first modulus of zero, or past end of list
fwd 6
jnz

fwd 1   ; negate cell to the right
jmp
rwd 1
add 1
fwd 1
jmp
sub 1
jnz
jnz
add 1
rwd 1
jmp
fwd 1
sub 1
rwd 1
sub 1
jnz

fwd 1   ; output
put

---

Explanation (In BF, since I actually wrote it in BF first)

Sesos and BF are closely related, so I will write the explanation in BF to take less space (it won't be on as many lines):

>   fwd 1
<   rwd 1
+   add 1
-   sub 1
,   get
.   put
[   jmp
]   jnz

First, Sesos is basically BF, but there is some I/O help, using the assembler directives set numin and set numout. These allow me to take an unbounded integer as input, into a single cell, or output that cell as an integer. I decided this was the easiest way to write the program for all positive integers.

My explanation is of each section from the above code, with sub-explanations showing the manipulations of the tape, in an attempt to help you understand the process and algorithm. I put the tape in curly braces, and use > to denote the pointer's location on the tape.

Section 1, the bug-fix / edge case:

It should be noted that before I fixed this, my code was only 54 bytes. Because of how I determine if a number is prime later, I had to add one to n if n==2, so I do that first. I use a , here (get) to zero a cell instead of looping with [-].

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

    n += (n==2):
    goal 1: { 2 n n }
    goal 2: { 0 n==2 n }
    goal 3: { 0 0 n* }

    { n 0 0 }
    [->+>+<<]++>
    { 2 >n n }
    [-<->]+<[>-<,]>
    { 0 >n==2 n }
    [->+<]>
    { 0 0 >n* }

Section 2, the list and my ultimate goal:

The way I check if n is prime is to check n modulo every number from n-1 to 2, which I figured would be simplest. My main goal was to reach the following data structure:

0 >{n n-1 0 0 0 0, n n-2 0 0 0 0, ..., n 2 0 0 0 0}

This facilitates the DivMod algorithm I planned to use, which requires n d 0 0 0 0 on the tape.

So I create a list from n-1 to 0, with the necessary spacing. I copy the first marked cell to the second, then copy that temp cell back into the original and into the next. Then subtract one. This repeats until I hit zero.

0 { 0 >n }
[[->>>+<<<]>>>[->>>+<<<<<<+>>>]>>>-]

0 {0 n 0 0 0 0, 0 n-1 0 0 0 0, ..., 0 2 0 0 0 0, 0 1 0 0 0 0, 0 >0 0 0 0 0}
     ^     ^      ^

Then, make the last section find n%2, since n%1 would cause a result of 0 for every n. Changing it to a zero instead of a two produces the wrong answer for n=1. After that, move back to n.

<<<<<<+
[<<<<<<]>>>>>>

0 {0 >n 0 0 0 0, 0 n-1 0 0 0 0, ..., 0 2 0 0 0 0}

Move n left one cell, preparing to copy it across the list:

[-<+>]

0 {n >0 0 0 0 0, 0 n-1 0 0 0 0, ..., 0 2 0 0 0 0}

Section 3, copy the n's

I copy n to the correct position for each entry in the list, so that I'll be ready to use the DivMod algorithm for each entry. I first add two here, so that we find another n%2, rather than n%0. This is nearly the same code as in section 2, except that I compare to the cell on the right each time, in order to stop upon completing the length of the list.

++[<[->>>+<<<]>>>[->>>+<<<<<<+>>>]>>>>]

0 {n 2 0 0 0 0, n n-1 0 0 0 0, ..., n 2 0 0 0 0, n >0 ...}
   ^     ^      ^

Section 4, compute each DivMod

I go through the list, doing the algorithm for each, after which only the n%d results are used. Though the algorithm only lists 4 cells on the site, it relies on the 5th and 6th cells being zero for its magic to work. I used the version which does not preserve n, since I won't need it anymore.

The algorithm:

# >n d 0 0 0 0
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
# >0 d-n%d n%d n/d 0 0

As applied across the list (x marks stuff I don't really need, but do make use of later):

[
    [->-[>+>>]>[+[-<+>]>+>>]<<<<<]
    <<<<<<
]>>>>>>>>

0 {0 x >n%(n-1) x 0 0, 0 x n%(n-2) x 0 0, ..., 0 x n%2 x 0 0}

Section 5, if any n%d == 0

I check the list from left to right.

{0 x >n%(n-1) x 0 0, ...}

[>]

What? You expected more? Well it really is that simple. This stops at the first occurrence of 0, which is either in this list, meaning the number is not prime, since it has a divisor, or we went past the list, and the number is therefore prime.

Section 6, negate the cell to the right and output

Uses this algorithm:

temp0[-]
x[temp0+x[-]]+
temp0[x-temp0-]

I don't need the first line, since my temp is already zero. I also use get to zero a cell instead of a loop. The last line prints the resulting number, a one if prime, or a zero if not.

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

Concluding remarks

Overall, this was a fun challenge. I found the mapping to BF pretty quickly with trail and error using the interpreter and the documentation. I completed it with something like 8 hours of effort. Much of the writing occurred in Notepad++ in BF that I then converted to Sesos with a Python program, tested, and debugged.

Convert BF to Sesos

Answer 26

Although there are several other answers that use a regex, none of them discuss the history of matching primes in this way, or show alternative regexes that match primes, or examine the range of compatibility of the regex with various engines. So that is what this post is all about.

All of the answers shown here take their input in bijective unary, as a string of x characters whose length represents the number. Output is in the form of "match" (prime) or "no match" (non-prime).

First, the shortest form:

^(?!(xx+)\1+$)

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater.

Try it online!

This is the standard, well-known primality test for numbers expressed in unary. I first became aware of it when arriving upon this 14 byte form independently in the course of solving one of the levels of Regex Golf on 2014-02-12 (which kick-started my interest in regex code golf). But in there, the set of test cases only started at \$2\$ (xx), thus glossing over the fact that this regex matches the non-primes \$0\$ and \$1\$.

I later learned that this regex dates back to at least as early as a 1997-10-22 Perl post by Abigail, which then began being discussed on the next day, extending to the next two pages.

The first appearance of a regex primality test on CGCC was a 2012-01-16 answer by ChristopheD to "Finding Not-Quite-Prime Numbers".

Regex (ECMAScript or better), 16 bytes

^(?!(xx+)\1+$)xx

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater, and \$n \ge 2\$.

Try it online!

The earliest I'm aware of anybody patching the regex in this way to block the matching of \$0\$ and \$1\$ is teukon in 2014-03-13. (I had previously toyed with ^(?!(xx+|)\1+$) as a patch, but this only blocks the matching of \$0\$.) Currently all of the other answers to this CGCC question that use the standard primality-testing regex, other than the Perl one, use this patched form: Retina, PowerShell, JavaScript.

It works in any engine supporting negative lookahead, which includes JavaScript/ECMAScript, Perl, PCRE, .NET, Java, Boost, Python, Ruby, and more.

Some alternative ways of testing primality avoid matching \$0\$ and \$1\$ in a conceptually and typographically cleaner way, but are longer:

Regex (ECMAScript or better), 18 bytes

^(?!(xx+)\1+$|x?$)

Try it online!

Same logic as above, except that preventing \$n \le 1\$ from matching is done inside the negative lookahead. See also the last version below, under "Inverted logic".

Regex (ECMAScript or better), 18 bytes

^(?=(xx+?)\1*$)\1$

The smallest \$q \ge 2\$ that divides \$n\$ exists, and \$q=n\$.

Try it online!

I came up with this on 2018-12-07. This expression can be useful within a larger regex, as it automatically captures the prime in a backref, which a negative lookahead cannot do. So, (?=(xx+?)\1*$)\1$ saves 1 byte compared to (?!(xx+)\1+$)(xx+) or 2 bytes compared to (?!(xx+)\1+$)(xx+$), and uses one less capture group.

Regex (ECMAScript or better), 18 bytes

(?=(x(x*))\1+$)\2^

The largest \$q \ge 1\$ that divides \$n\$ with a quotient of \$2\$ or greater exists, and \$q-1=0\$.

Try it online!

This was arrived at first by Grimmy on 2019-04-21. I independently came up with it on 2021-03-06, basing it on my earlier finding of ^(?>(x(x*))\1+$)\2 (below).

Like the below, it captures \1=\$1\$ and \2=\$0\$. If it were to be used in a larger regex (to assert primality without consuming any characters) and its captures aren't of use, ^(?!(xx+)\1+$|x?$) would be better, being equal in length but faster in most regex engines due to evaluating the ^ first instead of last (and its ^ can be omitted to test numbers smaller than the input for primality).

Regex (Perl / Java / Boost / Python / Ruby / PCRE / .NET), 18 bytes

^(?>(x(x*))\1+$)\2

The largest \$q \ge 1\$ that divides \$n\$ with a quotient of \$2\$ or greater exists, and \$q-1=0\$.

Try it online! - PCRE

I came up with this on 2018-12-07. It could conceivably be useful within the context of a larger regex. It consumes the entire prime number, like ^(?=(xx+?)\1*$)\1$, but its captures seem less likely to be useful; they are just \1=\$1\$ and \2=\$0\$. However, there may be niche circumstances where this could be coupled with NPCG (non-participating capture group) behavior, such that \1 or \2 matches if the path including the primality expression was crossed, but doesn't match otherwise. This would be equal in length to ^(?!(xx+)\1+$)xx() but capture two potentially useful optionally-unset groups instead of just one.

Regex (Tcl ARE), 16 bytes

^((x(x*))\2+$)\3

Try it online!

Tcl ARE has both positive and negative lookaheads, but neither backreferences nor captures can be done inside one. So seemingly, it would be impossible to match primes instead of non-primes.

But as it so happens, in Tcl ARE it seems that any group anchored on both sides (^ at the beginning and $ at the end, either outside the group or inside as long as it's adjacent to the parentheses in all its alternatives), will be treated as atomic (preventing the engine from doing the equivalent of backtracking into that expression if the pattern fails to match at a later point), as if the entire expression up to and including the $ were enclosed in (?>...). This does not appear to be documented, but can be exploited to emulate a negative match.

This regex is based on the 18 byte PCRE regex above. Both capture groups are shifted forward by 1, so \2 is \$q\$ and \3 is \$q-1\$.

‍

\$\large{\text{Inverted logic}}\$

In the following answers, "no match" indicates a prime, and a match indicates a non-prime.

Regex (GNU ERE or better), 14 bytes

^(xx+)\1+$|^x$

Try it online! - GNU ERE (very slow)
Try it online! - Tcl ARE
Try it online! - ECMAScript

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater, and \$n \ne 1\$.

Gives a false positive for \$n=0\$. As explained below, this cannot be avoided.

Alternative form:

^((xx+)\2+|x)$

Regex (Tcl ARE or better), 15 bytes

^(xx+)\1+$|^x?$

Try it online! - Tcl ARE
Try it online! - ECMAScript

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater, and \$n \ge 2\$.

Gives a correct answer for all \$n\ge 0\$. Doesn't work under GNU ERE, nor does any variation of it such as ^((xx+)\2+|x|)$ or ^(xx+)\1+$|^x$|^$. The moment the ability to match an empty string is added, it falsely matches all primes greater than \$7\$. This appears to be a bug in GNU ERE.

This form of primality test, eliminating the false positives on \$0\$ and \$1\$, dates back to at least as early as Abigail's 1997-11-18 signature on Perl Users Digest. It was not golfed at this point, and used a lazy quantifier for performance reasons (a change that occurred on 1997-10-24). This got carried over into some early CGCC answers, making them at least 1 byte longer than necessary.

The form presented here puts ^x?$ in the second alternative for performance reasons, so that it won't slow down the testing of \$n‍≥2\$ with the slight overhead of always trying that match first.

Alternative form:

^((xx+)\2+|x?)$

Answer 27

dc, 27 bytes

?dd[d1-d1<f*]dsfxr/r2r|p

How it works (example stack for input 7):

?                             7               push input
 dd                           7 7 7           dup
   [d1-d1<f*]dsf              7 7 7 {fact}    f = factorial macro
                x             7 7 5040        execute
                 r            7 5040 7        swap
                  /           7 720           divide
                   r2r        720 2 7         swap, 2, swap
                      |       1               modular exp: 720^2 mod 7
                       p                      print output

The factorial macro breaks for input 1, or something, but it turns out not to matter, and the output is correct.

Answer 28

Julia, 46 bytes

n=int(ARGS[1]);show(sum([n%i==0for i=1:n])==2)

An integer is read as the first command line argument using int(ARGS[1]) and the result is printed to STDOUT using show. Primality is checked using trial division with the same formulation as my R answer.

Note that the builtin function isprime uses the Miller-Rabin algorithm, which is probabilistic and is thus unsuitable for this challenge. (Thanks to Martin Büttner for pointing that out.)

Saved 4 bytes thanks to kvill.

Answer 29

JavaScript (ES6), 43 bytes

This is the shortest solution so far that accepts decimal input. Also, it doesn't use regex like the other short solutions.

p=n=>--d-1?n%d&&p(n):1;alert(p(d=prompt()))

What it uses instead is a recursive function, something that wasn't very useful when you needed to write function and return , but is now very useful because of the => notation.

Ungolfed:

p=n=>                 // p=function(n){ return
--d-1?                // if --d is not 1 (decrement d)
    n%d&&p(n)         // if n divdes d, false, else rerun the function
                      // (d has already been decremented)
:1;                   // else (if d is 1) then true
alert(p(d=prompt()))  // Use the function on the input
                      // and assign this value to d

Answer 30

Excel, 41 bytes

=2=SUM(N(0=MOD(A1,ROW(OFFSET(A1,,,A1)))))

Takes input from A1.

4 bytes saved thanks to @Joffan!