# Is this number a prime?

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.

Rosetta code features lists by language of idiomatic approaches to primality testing, one using the Miller-Rabin test specifically and another using trial division. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!" and Golf you a quine for great good!.

Furthermore, the capability of implementing a primality test is part of our definition of programming language, so this challenge will also serve as a directory of proven programming languages.

Write a full program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.

### Input

• If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).

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

In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

For scoring purposes, submit the program that corresponds to the input 1.

### Output

Output has to be written to STDOUT or closest alternative.

If possible, output should consist solely of a truthy or falsy value (or a string representation thereof), optionally followed by a single newline.

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

• This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

• Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

The language Piet, for example, will be scored in codels, which is the natural choice for this language.

Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

• Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

• If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

• Built-in functions for testing primality are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

• Unless they have been overruled earlier, all standard rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

### Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

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

• Is there a reason for the full program requirement, rather than allowing the full range of default input types? E.g. answering with a function that takes its input as an argument, is currently disallowed? codegolf.meta.stackexchange.com/questions/2447/… Dec 12, 2017 at 6:21
• @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. Dec 12, 2017 at 12:51
• Could a case be made for locking this challenge and posting a new, less restrictive one? Jun 25, 2018 at 12:59
• @Shaggy Seems like a question for meta. Jun 25, 2018 at 13:44
• Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. Jun 25, 2018 at 13:45

/^(1|(11+)\2+)$/c↲ (that last isn't a literal character; it stands for a final newline). Takes unary input on stdin. Anything that can be represented by two or more 1s, two or more times is a composite number and replaced by an empty line. Prime numbers are all truthy and left as-is. There's a slight catch in that this would classify 1 as a prime (it's actually neither prime nor composite), so there are an extra 4 bytes (1|) to handle that case. If you're willing to accept empty string as a false "output", then we could use d instead of c↲ for a further 1 byte saving. • I should have looked through the other answers before posting this - I thought I was being original and clever! Sep 15, 2015 at 14:40 # JavaScript (ES6), 28 bytes f=(n,i=n)=>n%--i?f(n,i):i==1 Try it online! Old, 33 bytes: f=(n,t=2)=>t<n?n%t?f(n,t+1):0:n>1 # Mathematica, 33 bytes Print[Mod[(#-1)!^2,#]>0&@Input[]] or Print[Length@Divisors@Input[]==2] Mathematica has a built-in PrimeQ as well, but I believe it uses a probabilistic test. • What is the measurable difference between having and not having "Print@" at the front of that expression? Sep 13, 2015 at 23:56 • @EricTowers without it, it will only print when run inside a notebook, i.e. in a REPL environment. I wouldn't consider that a full program. If you invoke the code from the command line, you need the Print@ to actually get any output. Sep 14, 2015 at 6:46 • According to the documentation, PrimeQ is a deterministic algorithm. I suspect the challenge text meant the other meaning (100% correct result). Sep 14, 2015 at 12:00 • You could save a byte with Echo. Nov 28, 2016 at 19:23 • @Pavel unfortunately, that also prints >> to STDOUT. Nov 28, 2016 at 19:33 # JavaScript, 5352 40 bytes alert(/^(?!(..+)\1+$)../.test(prompt()))

Just realized the question allows unary input, which cuts the size down to 40 bytes. Previous answer of 52 bytes is below (ES6):

alert(/^(?!(..+)\1+$)../.test('1'.repeat(prompt()))) Uses that cool unary regex to determine primality. I actually originally wrote this without seeing the Retina answer, and using a different regex, as seen here: !/^1?$|^(11+?)\1+$/. I moved to the Retina one since saves a character by avoiding the need for negation. • I think this (and the other JavaScript answers) should use alert or console.log. Otherwise it's assuming a REPL environment (like a browser console) whereas the challenge explicitly asks for a full program. That said, your own regex wouldn't have been longer than mine, because you only need ^1$ (zero is not a valid input). Sep 14, 2015 at 10:11
• @MartinBüttner I agree on it needing a print statement, but when doing so puts an otherwise shorter answer behind longer ones that don't follow that rule... I chose instead to mention why I didn't. If the other answers conform, I'll gladly adjust mine as well. Thanks! =) Good point, hadn't noticed the 0 part. It would be the same length in that case. Sep 14, 2015 at 15:05
• Well if the others think the same no one will change it. ;) You could just leave a comment (if I haven't done so already) and hope for Dennis to invalidate the answer (to remove it from the leaderboard) if the author doesn't fix it within a couple of days. Sep 14, 2015 at 15:07
• @MartinBüttner I left a comment on one of them a few days back, but fair enough haha. I suppose I could just edit them all for it as well and update the counts. Sep 14, 2015 at 15:21
• You can actually shorten the original regex by one character by making it !/^.?$|^(..+)\1+$/ Mar 27, 2016 at 13:05

# Turing Machine Code, 2043 bytes

As usual, I'm using the rule table syntax defined here. Requires unary input.

0 * * r 0
0 _ _ l c
a _ 1 r b
a 0 1 r b
a 1 0 l a
b * * r b
b _ _ r 0
c 1 _ l d
c _ _ * y
d * * l d
d _ _ l a
y _ _ l y
y * * l z
z * * l z
z _ _ r X
X 1 1 r Y
Y _ _ * f
Y * * l Z
X * * l 1
Z * * l 1
1 * a r 2
2 _ b l 3
2 * * r 2
3 a a r 4
3 x x r 4
3 y y r 4
3 * * l 3
4 0 x r 5
4 1 y r 5y
4 b b l 9
9 x 0 l 9
9 y 1 l 9
9 a a r A
5 b b r 6
5 * * r 5
5y b b r 6y
5y * * r 5y
6 _ 0 l 3
6 * * r 6
6y _ 1 l 3
6y * * r 6y
A _ c l 11
A * * r A
11 b b r 12
11 x x r 12
11 y y r 12
11 * * l 11
12 0 x r 13x
12 1 y r 13y
12 c c l B
13x _ 0 l 11
13x * * r 13x
13y _ 1 l 11
13y * * r 13y
B x 0 l B
B y 1 l B
B b b r 21
21 _ d l 22
21 * * r 21
22 1 0 r 23
22 0 1 l 22
23 d d r E
23 * * r 23
E c c r 51
E x x r 51
E y y r 51
E * * l E
51 0 x r Kx
51 1 y r Ky
51 d d l 53
Kx _ 0 l E
Kx * * r Kx
Ky _ 1 l E
Ky * * r Ky
53 x 0 l 53
53 y 1 l 53
53 c c r F
F _ _ l 61
F * * r F
61 1 0 l 62
61 0 1 l 61
61 d d r 70
62 c c l 63
62 * * l 62
63 1 0 r F
63 0 1 l 63
63 b b r 80
70 _ _ l 71
70 * * r 70
71 d d l 72
71 * _ l 71
72 c c * E
72 * * l 72
80 _ _ l Za
80 * * r 80
Za 0 1 r Zb
Za 1 0 l Za
Za d d r Zk
Zb _ _ l Zc
Zb * * r Zb
Zc x x l Zc
Zc y y l Zc
Zc d d r A0
Zc 0 x l $Zc 1 y l$y
$d d l Ze$ * * l y d d l @
$y * * l$y
Ze 0 x r Zf
Ze 1 1 r Zk
Ze x x l Ze
Ze y y l Ze
@ 1 y r Zf
@ 0 0 r Zk
@ x x l @
@ y y l @
Zf _ _ l Zc
Zf * * r Zf
Zk _ _ l Zm
Zk * * r Zk
Zm d d l Zn
Zm * _ l Zm
Zn x 0 l Zn
Zn y 1 l Zn
Zn 0 0 r Zo
Zn 1 1 r Zo
Zo d d l 82
Zo * * r Zo
82 1 0 l 83
82 0 1 l 82
83 c c l 84
83 * * l 83
84 b b l 85
84 * _ l 84
85 a a r 86
85 x x r 86
85 y y r 86
85 * * l 85
86 0 x r &x
86 1 y r &y
86 b b l 90
&x b b r Lx
&x * * r &x
&y b b r Ly
&y * * r &y
Lx _ 0 l 85
Lx * * r Lx
Ly _ 1 l 85
Ly * * r Ly
90 x 0 l 90
90 y 1 l 90
90 a a r 91
91 c c r 51
91 * * r 91
A0 _ _ l A1
A0 * * r A0
A1 d d l A2
A1 * _ l A1
A2 x 0 l A2
A2 y 1 l A2
A2 c c r A3
A3 d d l B0
A3 * * r A3
B0 1 0 r B1
B0 0 1 l B0
B1 d d l B2
B1 * * r B1
B2 1 0 r f
B2 0 1 l B2
B2 c c r t
t * * r t
t _ _ l t2
t2 * _ l t2
t2 _ 1 * halt
f * * r f
f _ _ l f2
f2 * _ l f2
f2 _ 0 * halt
• Nice! I imagine the state names could be golfed a bit more, though... Oct 27, 2015 at 23:23
• I'm still surprised this isn't actually the longest answer. (The Mornington Crescent answer is longer, which I guess makes some sense.) Oct 29, 2015 at 1:29

## Seriously 0.1, 2 bytes

,p

, reads a value from STDIN. p pops from the stack and pushes 1 if it is prime, else 0. At EOF, all values on the stack are popped and printed.

Currently, Seriously uses trial division to test primality, so for large inputs it may take a while. In a future version, I'll probably use ECPP or Miller-Rabin.

Try it online

• Seriously. Seriously? Nov 9, 2015 at 3:03

# 05AB1E, 1 byte

Code:

p

Explantation:

p     # Implicit input, check whether it is prime or not.

Try it online!

• @Okx Actually, that isn't necessary to state in this challenge, because this challenge explicitly states that newer languages are welcome here. Jan 26, 2017 at 17:34

## Sesos, 6362 58 bytes

0000000: 1651bc afcddc c4fbbe 3e739e c0f1be 3673c3 eecdf8  .Q.......>s....6s....
0000015: cc75b8 677ce2 b57bc6 78cddc 796de3 7eed33 b7c113  .u.g|..{.x..ym.~.3...
000002a: ef9da3 a0fbbc 77ece7 3adc2b 354e33 f9             ......w..:.+5N3.

The ASM code that I wrote, along with some comments can be run on Try it online:

set numin
set numout
get
sub 1
jmp ; if
jmp ; copy
fwd 1
fwd 1
rwd 2
sub 1
jnz ; end copy
fwd 2
sub 1
jmp ; triplicate loop
fwd 1
fwd 1
fwd 1
rwd 3
sub 1
jnz ; end triplicate
fwd 1
sub 1
fwd 1
sub 1
jmp ; factorial loop
jmp ; multiply loop
fwd 1
jmp ; forward add step of multiply loop
fwd 1
fwd 1
rwd 2
sub 1
jnz ; end forward add step of multiply loop
fwd 2
jmp ; after add step, reset tape
rwd 2
fwd 2
sub 1
jnz ; end reset tape
rwd 3
sub 1
jnz ; end multiply
fwd 1
get ; sets to 0
fwd 1
jmp ; transfer intermediate value
rwd 1
fwd 1
sub 1
jnz ; end transfer
rwd 3
sub 1
jmp ; reset loop counter
fwd 1
rwd 2
fwd 1
sub 1
jnz ; end reset
rwd 1
jmp ; fix memory location of header
fwd 1
rwd 1
sub 1
jnz ; end fix
fwd 2
jnz ; end factorial
fwd 1
rwd 4
jmp ; transfer input for mod
fwd 5
rwd 5
sub 1
jnz ; end transfer
fwd 4
jmp ; mod
sub 1
fwd 1
sub 1
jmp ; a
fwd 1
fwd 2
jnz ; a
fwd 1
jmp ; b
jmp ; c
sub 1
rwd 1
fwd 1
jnz ; b
fwd 1
fwd 2
jnz ; c
rwd 5
jnz ; end mod
fwd 1
get ; sets to zero
fwd 1
jmp ; invert a
rwd 1
fwd 1
get ; blanks
jnz ; end invert a
rwd 1
jmp ; invert b
fwd 1
sub 1
rwd 1
sub 1
jnz ; end invert b
jnz ; end if
fwd 1
put

I've never written any BF variant code before, outside of very simple tasks, so I'm sure some of this is not optimal. The divmod algorithm and the logical negation algorithm used were taken from the esolangs algorithms page.

This implements Wilson's theorem. We compute (n-1)! + 1 and then logically negate that value mod n. The factorial code hangs on input 1, so the code is wrapped in an if loop that totally skips running in that case. At the very end, the tape head is manipulated to be over where we would have left the mod value if we ran the code, or over some random zero if the input was 1. I'll add a more thorough explanation when I am done golfing.

# brainfuck, 62 bytes

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

This is a port of my Sesos answer. Input and output are character-based. For a character whose code point is prime, the program will print the character itself; otherwise, it will print NUL.

Try it online!

## Jellyfish, 13 bytes

p|&*!<
E   i

Try it online!

Uses the squared-factorial approach based on Wilson's theorem.

### Explanation

Jellyfish is Zgarb's language based on his 2D syntax challenge. The semantics are largely inspired by J, but the syntax is where it gets interesting. All functions are single characters and laid out on a grid. Functions take their arguments from the next token south and east of them and return the result north and west. This let's you create an interesting web of function calls where you reuse values by passing them into several functions from multiple directions. There are also higher-order functions called operators, which let you construct more complex functions from the built-in ones.

The only non-functions in the above code are E and &. The former redirects |'s search for its southern argument to the east, so that | actually takes i as that input.

& applied to a single unary function (in this case *) uses the binary definition by supplying the single argument twice. Since the binary definition of * is multiplication, this yields a squaring function.

Taking these things into account, we can write up a more conventional expression:

p(i | (&* ! < i))

Here, i is just the input we're testing for primality. < decrements it, ! computes its factorial, &* squares it. | is modulo although it divides its right-hand operator by its left to compute the remainder. Hence the stuff inside the p(...) computes (n-1)!^2 % n. The p just prints the result.

• I'm a little surprised how much you can do with my nonsensical collection of built-ins. :D But thanks for the praise! Aug 3, 2016 at 20:19
• This is a very genius and short code. But moving "<" to the 2nd line makes it 1B shorter such as; 1st line: p|&*! + 2nd line:  > <i Dec 19, 2022 at 14:10

# Mini-Flak, 202 bytes

Mini-Flak is a turing complete subset of the Brain-Flak language. (It is currently the smallest know turing complete subset of Brain-Flak) It works exactly like Brain-Flak except the <> and [] nilads and the <...> monad are forbidden.

(({})){(({}[()])(((({}({}))[({}[{}])]([()]()))({({}[()((({}()[({})])){{}((({}({})))[{}])}{})]{})}({}{}({})[{}]))[{}]))[{}])}{}{}({}({})[{}()()()]){({}[()((({})){(({}{}(({})))[{}])}{}({}({})[{}]))]{})}{}

Try it online

## Explanation

The reason <...> is banned in mini-flak is that it is equivalent to (...)[{}]. So to start this explanation I am going to use this translation in reverse to create an equivalent Brain-Flak program for increased readability for anyone who is already familiar with Brain-Flak.

(({}))
{
(({}[()])<
((({}({}))[({}[{}])]([()]()))<{({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)>)
>)
}{}{}({}<{}>[()()()])
{({}[()((({})){(<{}{}(({}))>)}{}({}<{}>))]{})}{}

This program has two main parts, performs the modulus on the input for every number smaller than than the input and leaves them in a stack.

(({}))
{
(({}[()])<
((({}({}))[({}[{}])]([()]()))<{({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)>)
>)
}{}{}

This uses a old version of modulo I wrote ({}(<()>)){({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)

The second part ands together all of the results of the last part

({}<{}>[()()()])
{({}[()((({})){(<{}{}(({}))>)}{}({}<{}>))]{})}{}

If any one of the results is zero the result of all the ands will be zero otherwise it will be truthy and the number will be prime.

• So you accepted my challenge, right? Nov 29, 2016 at 12:00

# Japt, 1 byte

j

Built-ins are useful for long challenges, but aren't fun in mini-challenges like this. So here's an alternate version without the built-in; still pretty short:

# Japt, 8 bytes

o2 e@U%X

Try it online!

### How it works

// Implicit: U = input number. Implicitly place a U at the beginning of the program
o2    // Create an array of all integers from 2 to U. (2o6 = [2,3,4,5])
// For numbers below 2, this returns n to 2. (2o-3 = [-3,-2,-1,0,1])
e@    // Check if every number X in this range returns truthily to:
U%X   //   the remainder of U divided by X.
//   In other words, if any of these remainders are 0, return false.
//   For numbers less than 2, the range contains 1,
//   so this always returns false for these cases.
// Implicit: output last expression

# J, 19 17 Bytes

echo(p:[:".1!:1)1

### Explanation:

echo(p:[:".1!:1)1  | Full program.
echo(          )   | Hook: (f g) y is evaluated as y f (g y)
[:".1!:1    | Right verb in the hook
1!:1    | With argument 1, reads a line of input
".        | Evaluate, converts valid string to int
[:          | Cap, treat these two verbs as one
p:            | With a left argument of 1, as supplied by the hook, tests primality of its right argument
echo               | Print
• I might be missing something, but 1 p: is shorter than 1=#q: (built-in primality testing isn't disallowed as far as I can tell).
– cole
Jan 16, 2018 at 22:25

# Pip, 10 8 bytes

1=0Na%,a

Try it online! (testing numbers 0 through 29)

Takes the number as a command-line argument (a) and uses the definition of prime number (has only 1 and itself for factors):

,a  Range of numbers from 0 through a-1
a%    Take a mod each number in range; this is 0 if the number is a divisor,
nil if the number is 0, and nonzero otherwise
0N      Count the number of zeros in that list
1=        True (1) if the count is exactly 1, false (0) otherwise
Print (implicit)

# Nibbles, 4 bytes

%^*<<,

Uses Wilson's theorem, which states that an integer $$\ n \$$ $$\ (n > 1) \$$ is prime iff $$\ (n-1)! + 1 \$$ is divisible by $$\ n \$$. To capitalize on Nibbles' implicit args feature, I slightly modified the formula to check for $$\ (n - 1)!^n \bmod n > 0 \$$, which also nicely handles the $$\ n = 1 \$$ edge case.

In Nibbles, an integer is Truthy if it is positive, and Falsy otherwise. Under this definition, checking whether the modulus is positive isn't necessary.

### Ungolfed

%         # Modulo of
^        #  power of
*      #   product of
<<,   #    [1..n-1] (implicit $) # n (implicit$)
#  n (implicit $) # Cubestack, 98 bytes M R2 M' b' M R M' r M R' M' U2 S S' y b' M R M' r S S' y2 U M R M' D x M R M' b f2 x' y' M R' M' b Try it Online! Brief explanation: M R2 M' b' M R M' r M R' M' U2 S S' # Set up the for loop M R2 M' # Push 2 to the stack b' # Get all inputs wrapped in a list M R M' r # Get the first item of the list pushed M R' M' # Push 1 to the stack U2 # Range (start, end, step) S S' # Push an empty string (the loop variable) y b' M R M' r S S' y2 U M R M' D # Check if n is divisible the loop variable y # Open a for loop b' M R M' r # Get the first (and only) input S S' y2 # Get the value of the loop variable U # Perform modulo operation on the top two items M R M' D # Check if the top item equals 0 x M R M' b f2 x' y' # If n is divisible be the loop variable, print 0 and exit x # Open an if statement (code runs if top item is truthy) M R M' # Push 0 to the stack b # Print f2 # Exit program x' # Finish if statement y' # End for loop M R' M' b # Provided that the program didn't exit in the loop, print 1 I won't explain Cubestack's syntax here, but you can see more information about this cursed language on the docs on GitHub. 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*$)\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). There may be circumstances in which this could be useful in the context of a larger regex. For example, if the very first thing a regex needs to do is assert that the input is prime, without consuming any characters, this would be 2 bytes shorter than ^(?=(?!(xx+)\1+$)xx).

## 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 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?)$

# floor, 105 bytes

F:x->floor x
r:x->1/(x-F x)
I:x->1+F(F x-x)
p:k->(F k*r k)+1/(r k-1)
f:n->(n-1)*I(F p^(n-2)(1+1/(n-1))/n)

returns nonzero for primes and zero for non-primes

## Explanation

Ungolfed version:

intPair: x y -> x + 1/y
left: x -> floor x
right: x -> 1/(x-floor x)

is_int: x -> 1+floor(floor x - x)

fakt_1: n_k -> intPair ((left n_k)*(right n_k)) (right n_k - 1)

f: n -> (n-1)*is_int( (left fakt_1^(n-2) intPair 1 (n-1))/n)

Uses Wilson's theorem to determine if the input is a prime number

fakt_1^(n-2) intPair 1 (n-1) computes (n-1)!+1 (abusing that storing one in the second component of a pair, will increase the first component by 1)

The rest of f checks if (n-1)!+1 is evenly divisible by n and returns 1 if yes and zero otherwise. The multiplication with (n-1) is to ensure that 1 is not falsely detected as prime

## Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>

# floor, 116 bytes

F:x->floor x
r:x->1/(x-F x)
I:x->-F(F x-x)
s:p->I(F p/r p)*F p+1/(1+r p)
f:n->-F((1-n)/((1-n)^2+1))*F s^(n-2)(n+1/2)

returns non-zero for primes and zero for composites

# Explanation:

Ungolfed version:

lt: x y -> -(floor((x-y)/((x-y)^2+1)))

intPair: x y -> x + 1/y
left: x -> floor x
right: x -> 1/(x-floor x)

not_int: x -> -floor(floor x - x)

prime_step: n_k -> intPair (not_int(left n_k / right n_k) * left n_k) (1+right n_k)
f: n -> (lt 1 n)*(left prime_step^(n-2)(intPair n 2))

prime_step takes a pair of integers (n,k) (encoded as a single rational number) as input an returns (0,k+1) if k is a divisor of n, and (n,k+1) otherwise.

f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0

# Lua, 56 bytes

for i=1,n-1 do
p=p*i*i%n
end
print(p%n)
• p=1 for i=1,...-1 do p=p*i*i%...end print(p%...>0) does the job in 50 bytes, by switching the input to command-line argument, and printing true and false instead of 0 and 1. Also, Be aware that 0 evaluates to true and is therefore a truthy value in lua, so your current answer technically always input true. Apr 11, 2016 at 12:31

# awk, 30 25 24 bytes

"factor "$0|getline~--NF Prints the number followed by a colon if it's is prime, prints nothing if it's not. I check for NF, because the output line from factor has exactly two fields if the input number is prime. The pipe command changes$0, and returns 1 on successful execution. So if NF-1=1 I know we had a prime.

You can use the ~ operator to compare two numbers, if you know that the second number would always be equal or greater.

Example usage:

echo 12347 | awk '"factor "$0|getline~--NF' My previous idea didn't involve using system commands and is 29 bytes long: {for(++d;$0%++d&&$0>1;);}d~$0

Prints the number if it's prime and nothing if it's not.

Example usage:

echo 12347 | awk '{for(++d;$0%++d&&$0>1;);}d~$0' • And not only because I touched the ZX81 too: if you should have only 2 fields, it has not to be the 3rd. awk '"factor "$0|getline~!$3', one character less, but it answers prime number for 1 too (that it should be excluded), so I don't know if useful. Jul 19, 2016 at 17:53 # APL, 21 {∧/0≠⍵|⍨(⍵≠1)+⍳|⍵-2}⎕ Trial division. It would incorrectly state that ¯1 (minus one) is a prime but it's outside the domain so it's all right. • Welcome to Programming Puzzles & Code Golf! Because APL has its own legacy code page, we usually count APL as one byte per character here. Sep 13, 2015 at 5:28 # XSLT 3.0, 178 bytes <transform xmlns="http://www.w3.org/1999/XSL/Transform" xmlns:x="x" version="3.0"><template match="d" expand-text="yes">{.>1 and empty((2 to .-1)[current() mod .=0])}</template></transform> Posted as an alternative, because it uses a significantly different approach than my previous post. In expanded form, with the usual prefixes: <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="3.0"> <xsl:template match="d" expand-text="yes">{ . > 1 and empty((2 to . - 1)[current() mod . = 0]) }</xsl:template> </xsl:stylesheet> This method also uses a variant of my XPath solution for primality testing, which is explained there. Since the default in XSLT is to process all nodes in the input document, this is what happens here as well. For input, you need to hand it a proper, validated XML document with a root element <d>: <d>101</d> The result will be output as true or false. It utilizes an XSLT 3.0 feature that allows inline XPath expressions in text nodes. It uses the XSLT 2.0 feature of schema-aware processing. If you don't have such a processor, add the XSD namespace and replace the XPath expression with the following: . > 1 and empty((2 to . cast as xs:integer - 1)[current() mod . = 0]) For a non schema-aware processor, it would make the code at least 62 bytes larger. # Prelude, 12580755955 52 bytes 1-^ (1-v#0)#)#1+1-))(0 ?(1- ^ ^1-( 0#v+^-( 0##10)! For convenience, I'd suggest using my modified interpreter which reads input and prints output as decimal integers. (Otherwise, I/O would be via a single character's ASCII value.) It turns out that simple trial division is shorter in Prelude than the squared-factorial approach, because multiplication is fairly expensive. I also found new shortest solutions to compute a modulo and a logical NOT while working on this. ## Explanation The basic algorithm is trial division: check how many numbers in [0,n-1] divide the input n via modulo (where my modulo implementation happens to return i for i%0, such that 0 is never a divisor, but doesn't crash the program either). If there was exactly one divisor (1) we have a have a prime, otherwise we don't. So the print the logical NOT of the number of divisors minus 1. Let's go through the voices: 1. This voice counts the number of divisors, and is also used for the outer loop of the modulo. 2. This voice merely reads the input and then performs the main loop from n-1 down to 0. 3. This voice does the main work of the modulo computation and computes and prints the logical NOT of the number of divisors. Finally, we can look at some parts of the code in detail: ^ (1-v#0)#)# ^1-( 0#v+^- This is the modulo. The top voice starts by copying n from the bottom voice and the bottom voice copies the current (potential) divisor from the middle voice. The idea is to decrement both values until n is zero, but whenever the divisor hits zero we restore it. The restoring works like this: we always copy the divisor into the top voice with v. But while the bottom voice is non-zero, we immediately discard it and push a zero instead. This value is then shifted to the bottom voice and added to the current value there. Finally, the modulo is how far we are into the current cycle, so we subtract the divisor from the result with ^- (which is actually minus the modulo, but we only want to know if it's zero or not, so this doesn't matter). 1- mod 1+1-)) ?(1- ^ mod ( 0## This is then the main loop. The top voice is initialised to -1 (to account for the fact that 1 is always a divisor), the middle voice reads the input and the bottom voice receives a copy. Before computing the modulo, the middle voice decrements the current divisor. After the modulo is computed we increment the counter, but decrement it again if the modulo was non-zero. Finally, we compute the logical not, by pushing a 1 onto the bottom voice but putting a 0 on top if the divisor counter was non-zero, before printing it: (0 10)! # Fortran 2003, 51 bytes Here is a solution using Fortran's array capabilities. Fortran 2003 is really only required for the shorter array constructor [ ] instead of the old (/ /). read*,n print*,count([(mod(n,i),i=1,n)]==0)==2 end # MATLAB, 2431 36 bytes 1. Changed to 31 bytes in order to add in the case of n=1 2. Changed to 36 bytes to make a full program and to incorporate the 1 byte saving from a suggestion by pawel.boczarski (thanks!) Since isprime is already taken, an alternative is to take a look at the greatest common divisor of the number in question n with every number from 2 up to n-1. If the GCD of every number in the output is 1, then the number is prime. However, we need to check for the case of n=1, and so by definition, this shouldn't be prime: n=input('');n-1&all(gcd(n,2:n-1)==1) This creates an anonymous function that checks if the number is prime and assigns it to the variable f. To call the function, simply do f(n) once it's created with n being a positive integer. # Sample Runs >> n=input('');n-1&all(gcd(n,2:n-1)==1) 1 ans = 0 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 2 ans = 1 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 3 ans = 1 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 4 ans = 0 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 5 ans = 1 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 7 ans = 1 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 10 ans = 0 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 13 ans = 1 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 15 ans = 0 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 20 ans = 0 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 23 ans = 1 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 33 ans = 0 >> n=input('');n-1&all(gcd(n,2:n-1)==1) 37 ans = 1 • Two tips: you can omit f= - the anonymous handle is a perfect solution (2 bytes saved), moreover in case of positive integer n~=1 can be replaced by n-1 (1 byte saved) - I tried in Octave and it worked, should work in Matlab as well. Sep 12, 2015 at 8:59 • @pawel.boczarski thanks! I had the anonymous handle but thought it conflicted with the definition of a "full program". Could you perhaps clarify on what this means? Sep 12, 2015 at 9:02 • Uhm, you're right. This is clarified in the task spec that a full program is demanded, I didn't notice that. But the tip with n-1 instead of n~=1 will still work. Sep 12, 2015 at 9:10 • @pawel.boczarski that'll shave one byte off. Thanks! Also thanks for the clarification Sep 12, 2015 at 9:19 ## HPR, 1217 bytes 393 bytes with macros HPR is an unusable language I created for a challenge here. It has only five commands, and it's not Turing complete; I was actually surprised that a primality test could be programmed in HPR. This answer stretches the conditions of input formats a bit, since the input has to be provided as a descending list of integers from n to 1, encoded in unary and separated by 0s. There has to be a trailing 0, so the number 4 would be encoded as 11110111011010. The program prints 1 if the input is a prime, and an empty line if not. Here's the source code:$!($)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(--))(*#(!(-)(#(-)()))())))!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))())!(#(*#(!(-)(#(-)()))())(!(-)(#(-)()))-!(-)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(#(#(!($)(#(*)()#(!(-)(#(-)()))())!(-)(#(-)())*)()#(!(-)(#(-)()))())(!(-)(#(-)())))(-#(!(-)(#(-)()))())#(!(-)(#(-)()))())))(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())($!($)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())(#(*)()#(!(-)(#(-)()))()))!(-)(#(-)())#(*)(!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))#(!(-)(#(-)()))())!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(*)(!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))#(!(-)(#(-)()))())))-#(!(-)(#(-)()))())-#(!(-)(#(-)()))())!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(--))(*#(!(-)(#(-)()))()))!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(-)

This was not written by hand, but generated from this 393-byte source by TheNumberOne's macro system:

def d 0 !(-)(#(-)())
def l 0 #(<d>)()
def f 1 !({0})(#({0})())
def n 1 !(<d><l>)({0})
def o 2 <n>(<n>({0})){1}
def m 0 <d><f>(-#(!(*)(#(*)())<l>)(<d>))#(-)(<l>)
def x 0 <d>#(*)(<m>)<l>
def z 1 <d>*<l>!(-)(-{0})
def i 0 <d>#(<z>(-))(*<l>)
$!($)(<o>(<i>,<m>!(#(*<l>)(<d>)-!(-)(<n>(!(#(#(!($)(#(*)()<l>)<d>*)()<l>)(<d>))(-<l>)<l>)))(<o>($!(\$)(<o>(#(*)()<l>,<x>))<n>(<x>),-<l>))-<l>))<n>(<i>)<z>()

## Explanation

An HPR program is run in an environment, which is a set containing nonnegative integers and lists. Initially, it contains the input list, and the five commands modify the environment in different ways. However, it's not possible to obtain larger numbers than the maximum of the list, and it's not possible to add new elements to lists. Thus, trial division is the way to go. I'm not going to completely explain the code in this post, but an expanded version with comments can be found here.

# Lambda Calculus, 615 bytes

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))

Inspired by the turing machine solution, here is a Lambda Calculus solution! You can test this code in this lambda evaluator, or in this one. The second one stops every 400 reductions so its more stable on big inputs (>11), but the first one is by far the nicest. Just paste the code in the text box and type a number behind it.

For example

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))
4

gives

\x y. y  ;false

And

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))
5

gives

\x y. x ;true

# Sesos, 28 24 bytes

0000000: 1651b8 77cd1c 345e33 c67bbe c673b8 676c38 67fe98  .Q.w..4^3.{..s.gl8g..
0000015: 70e201

Uses trial division. Try it online! Check Debug to see the generated binary code.

### How it works

The binary file above has been generated by assembling the following SASM code.

set numin     ; Switch to numeric input.
set numout    ; Switch to numeric output.

get, sub 1    ; Read an integer n from STDIN and decrement it.
; If n is 1, this will leave a 0 in cell 0.
jmp           ; While loop entry point; if the cell is 0, skip the loop body.
add 1     ; Add 1 to restore n.

; The following is the actual primality test. To see how it works, consult the
; corresponding section of this answer.

jmp, rwd 1, add 1, fwd 2, add 1, rwd 1, sub 1, jnz
fwd 1
jmp
sub 1, rwd 1
jmp, fwd 1, add 1, rwd 1, sub 1, jnz
rwd 1
jmp
fwd 1, add 1, fwd 1, sub 1, fwd 1, add 1, rwd 1
jmp, fwd 1, jnz
fwd 1
jmp, rwd 1, add 1, fwd 1, sub 1, jnz
rwd 2
jmp, rwd 1, jnz
fwd 1, sub 1
jnz
fwd 3
jnz
rwd 1, sub 1
jmp, rwd 1, jnz

jnz           ; While loop exit marker; since the previous instruction also sets
; an exit marker, the current cell will be 0 and we exit the loop.
rwd 1, put    ; Retrocede to the previous cell and print its content to STDOUT.
; If n > 1, this will print the result from the primality test.
; If n = 1, it will simply print 0.

### Modulus computation

The core of this answer is its modulus algorithm, which is based on the divmod algorithm from Esolangs. Unlike the latter, it doesn't compute a quotient and works if the divisor is 1.

Suppose the tape in in the following state, where n and d are positive integers.

v
n     0     d     0     0     0

To compute n % d, we will decrement the third cell n times. Each time we decrement it, we also increment the fourth cell (so their sum is d at all times), and swap their contents every time the third cell reaches 0.

We have to decrement the first cell once for each iteration, and stop once it reaches 0. Since this will destroy the content of the first cell, we'll also increment the second cell once for each iteration, effectively copying n to the second cell.

Once the first cell reaches 0, the tape will be in the following state.

v
0     n   d-n%d  n%d    0     0

We achieve this as follows.

jmp           ; While the first cell is non-zero:
fwd 1     ;     Advance to the second cell.
add 1     ;     Increment it.
fwd 1     ;     Advance to the third cell.
sub 1     ;     Decrement it.
fwd 1     ;     Advance to the fourth cell.
add 1     ;     Increment it.
rwd 1     ;     Retrocede to the third cell.
jmp       ;     While the current cell in non-zero.
fwd 1 ;         Advance to the next cell.
jnz       ;     This will advance to the fifth cell if the third is non-zero
;     and stay on the third cell otherwise.
fwd 1     ;     Advance either to the fourth or sixth cell.
jmp       ;     While the fourth/sixth cell is non-zero:
rwd 1 ;         Retrocede to the third/fifth cell.
add 1 ;         Increment it.
fwd 1 ;         Advance to the fourth/sixth cell.
sub 1 ;         Decrement it.
jnz       ;     This will add the fourth/sixth cell to the third/fifth cell,
;     zeroing the former in the process. Since the sixth cell has a
;     value of 0, this loop is a no-op if the third cell in 0; other-
;     wise, it sets the third cell to d and the fourth cell to 0.
rwd 2     ;     Retrocede to the second/fourth cell.
jmp       ;     While the current cell is non-zero:
rwd 1 ;         Retrocede to the previos cell.
jnz       ;     This places the head to the left of the first cell.
fwd 1     ;     Advance to the first cell.
sub 1     ;     Decrement it.
jnz           ;

### Primality test (WIP)

For input n > 1, we can use the modulus algorithm from the previous section to implement a primality test by trial division.

If n is already on the tape, we procede as follows.

1. Create a copy of n and decrement it to leave the tape as

v
n     0     d     0     0     0

where d = n - 1.

2. Retrocede to n and use the modulus algorithm to compute n % d, leaving the tape as follows.

v
0     n   d-n%d  n%d    0     0

3. Advance to the cell containing n % d.

1. If n % d > 0, add d - n % d to n % d to restore d, decrement it, and go back to step 2.

2. If n % d = 0, we found the first divisor of n (1 for primes); go to step 4.

4. Since n % d = 0, d - n % d = d.

We retrocede to that cell, decrement it to leave d - 1 in it (0 if and only if n is prime), and retrocede until finding the first 0 cell. This leaves the tape as

v            V
0      0     n     d-1   0    0     0

where v marks the location of the tape head if d - 1 > 0, and V the location if **d - 1 = 0.

Note that the value of the cell under the tape head will be 0 in either case. The cell to the left will contain n if n is prime, and 0 if n is composite.

• You should add the BF version of your modulus algorithm to the Esolangs page. Jul 25, 2016 at 15:35
• Done. Jul 25, 2016 at 17:09

## CASIO-BASIC, 28 bytes

?->A:For 2->B To A:A Rmdr B=0=>B->A:Next

This prompts for a number, then outputs the number if it is prime, else zero.

I'm not really sure how this works. I originally thought it would output the value from the last assignment (stored in Ans), but then it would output the lowest factor of the number, not zero.

Note: -> and => are ASCII representations of one symbol each (the assign-to and conditional operators).

The size was calculated as the size of this program (60 bytes) minus the size of an empty program (32 bytes).

# WolframAlpha, 10 bytes

isprime(n)
• haha, this is interesting... Aug 31, 2016 at 9:56
• Save some bytes with 'n prime'. Dec 29, 2016 at 22:40