# Is this number a prime?

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

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

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

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

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

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

### Input

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

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

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

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

### Output

Output has to be written to STDOUT or closest alternative.

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

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

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

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

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

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

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

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

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

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

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

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

### Catalog

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

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

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

## Logy, 82 bytes

f[X]->X<2&1|X*f[X-1];p[&1]->0<0;p[X]->f[X-1]%X==X-1;main[A]->print[p[atoi[A(1)]]];

I have no idea what I am doing.

Use Wilson's theorem.

Ungolfed code:

factorial[X] -> X < 2 & 1 | X*factorial[X - 1];
prime[&1] -> FALSE;
prime[X] -> factorial[X - 1]%X == X - 1;
main[Args] -> print[prime[atoi[Args(1)]]];

# Batch, 121 bytes

set i=2
if %1%==2 exit /b
if %1%==1 echo 0
:b
set /a a=%1%%%i%
set /a i=%i%+1
if %i%==%1% exit /b
if %a%==0 echo 0
goto b

Outputs 0 if it's no prime. This works only for inputs input > 0.

# Dip, 1 byte

P

Pretty self-explanatory...

## Unary, 165192711826249169871716905363504385377479408598339493836 bytes

Well, basically 165192711826249169871716905363504385377479408598339493836 zeros. Here is a Java program that prints the actual program:

public class Main{
public static void main(String[]args){
for(BigInteger i = new BigInteger("165192711826249169871716905363504385377479408598339493836"),BigInteger j = BigInteger.ZERO;j.compareTo(i)!=0;j = j.add(BigInteger.ONE)){
System.out.println("0");
}
}
}

This a port of this Brainfuck answer.

## memes, 2 bytes

I decided to hop on the language train. Code:

}"

Explanation:

} //Takes next input.
" //Returns True or False, representing if the input is prime.

# Ceylon, 107 112

That was my first try:

This is a simple trial division of all numbers between 2 and c - 1, using the range operator : and the any method for iterating.

But this will also note 1 as prime. So here the corrected version:

That works for numbers up to 2^63-1 ... and takes quite long for larger primes (or composite numbers with large factors) – I think it took about half a minute to confirm 2147483647 (=2^31-1) as prime.

The formatted version:

shared void p() {
exists c = parseInteger(a)) {
print(1 < c && !(2 : c - 2).any((d) => c % d < 1));
}
}

I originally wrote the check as d.divides(c), but the modulo operator is so much shorter.

As a bonus, here is a variant for arbitrary size integers, though there is not really a point in using this due to the slowness.

import ceylon.math.whole {
w=parseWhole,
t=two,
o=one
}
shared void q() {
exists c = w(a)) {
print(c == t || !(t .. c - t).any((d) => c % d < o));
}
}

The : range operator needs an Integer (the number of elements) as a second argument, so we use the .. operator, which takes the same type as the first argument, i.e. here a Whole, as second argument (the upper limit). 2..c-1 is the same as 2:c-2 for large c, but this becomes an empty list for two (and a non-empty list for one), so we need a different exception here than in the Integer version. It becomes mainly longer due to the imports.

The space-reduced version has length 153:

import ceylon.math.whole{w=parseWhole,t=two,o=one}shared void q(){if(exists a=process.readLine(),exists c=w(a)){print(c==t||!(t..c-o).any((d)=>c%d<o));}}

# Maverick, 25 bytes

(1:(<>@-1)//$*)%<>@=<>@-1 Try it online! This is a pretty fun language IMO. Infix and esoteric. (1:(<>@-1)//$*)%<>@=<>@-1
1:                         range from 1 to
(<>@                     first command line arg (<> called with no args)
-1)                  minus 1
//$* folded over multiplication ( )% modulus <>@ the input = does the above equal <>@-1 the input minus 1? If so, yields prime # Valyrio, 14 bytes s∫main [ipo] Outputs 1 if the input is prime. Otherwise outputs 0. ### Explanation s∫ tells the interpreter to enter stack mode main [ starts the main code block i takes an input and evaluates it p pushes 1 or 0 to the stack depending on primality o outputs the top item on the stack ] ends the main code block ## Racket 75 bytes (let p((c 2))(cond[(> c(sqrt n))#t][(= 0(modulo n c))#f][else(p(+ 1 c))])) Ungolfed: (define (f n) ; COMMENTS: (let loop ((c 2)) (cond [(> c (sqrt n)) #t] ; if no divisor found till sq root of number, it must be a prime [(= 0 (modulo n c)) #f] ; if divisor found, it is not a prime [else (loop (add1 c))] ; try with next number ))) Following version is longer but more efficient for checking larger numbers since it keeps & uses previously found prime numbers: (λ(N)(define(p n(o'(2))(c 2))(cond[(> c n)o][(ormap(λ(x)(= 0(modulo c x)))o) (p n o(+ 1 c))][else(p n(cons c o)(+ 1 c))]))(= N(car(p N)))) Ungolfed version: (p=subfunction to build prime number list till n; o= list of prime numbers found; c=current number being checked) (define f (λ (N) (define (p n (o '(2)) (c 2)) (cond [(> c n) o] [(ormap (lambda(x) (= 0 (modulo c x))) o) (p n o (add1 c)) ] [else (p n (cons c o) (add1 c))])) (= N (first (p N))))) Testing: (f 109) (f 10) (f 11) (f 12) (f 13) (f 49) (f 43) (f 57) (f 47) Output: #t #f #t #f #t #f #t #f #t • If I understand correctly, the solution given is a snippet, not a full program, because it inputs from the variable n. – Esolanging Fruit Apr 24 '17 at 6:43 # PHP, 43 39 54 44 43 bytes improved my answer from stackoverflow: for($i=$n=$argv[1];--$i&&$n%$i;);echo$i==1;

Run with -r. prints 1 if argument is prime, empty string else.

loops $i down from$n-1 until it finds a divisor of $n;$n is prime if that divisor is 1.

6 bytes extra for the 1 case. almost happy.

# √ å ı ¥ ® Ï Ø ¿ , 3 bytes

Ipo

p is the primality test.

# NO!, 34 bytes

This was taken from the NO! GitHub page. It isn't mine

NOOOOOOO?NOOOOOOOOOOO
NOOOOOOOO?no
• This should be marked as community wiki if you didn't write it. – Esolanging Fruit May 11 '17 at 14:09

Ruby 16+15 bytes

require 'prime';p->e{e.prime?}

## QBIC, 2120 3 bytes (nc)

Since the purpose of the challenge is to build a catalog, I feel it's important to keep the QBIC post up-to-date with the current state of the language:

­?µ:

Explanation:

?    PRINT
µ   QBIC's prime test, returns -1 for primes, 0 otherwise
:  Read a number from the command line, insert that here
The function is closed automatically because of EOF.

Previously, at 20 bytes:

:[a|~a%b|\p=p+1}?p<3

Simple trial divider. Every time b (the loop counter) cleanly divides a (our prime-candidate), p is increased. Primes will end with p at 2 (or p=1 for a=1). This then prints -1 for primes, and 0 for non-primes, which are QBasic default values for true and false resp.

Original entry, 21 bytes. This prints 1 for primes, and 0 for others. This feels more 'natural' to me than QBasic's default -1/0. Also, this only does slightly less than a/2 divisions for primes (and quits when it detects a non-prime), instead of doing a divisions regardlessly.

:[2,a/2|~a%b=0|_Xp}?q

Explanation:

:       Get the input number, 'a'
[2,a/2| FOR(b=2, b<=(a/2), b++)
~a%b=0  IF a MOD b == 0     --> Clean division == no prime
|_Xp    THEN exit program, printing 'p' (which never gets set and is 0 by default)
}       Close all language constructs: IF/END IF, FOR/NEXT
?q      We've made it through the FOR loop without division, N is prime.
In QBIC, 'q' is auto-initialised to 1, '?' prints it.

D,f,@,P
+?
$f,x O Try it online! 10 bytes are boilerplate for the full program requirement. ## Function, 7 bytes D,f,@,P Fairly basic, just defines a function that performs a primality test ## Built-in, 1 byte P As functions and main code use both different memory models and different commands, this only works in function mode and so would be invalid. # cQuents, 3 bytes ?pz Try it online! ### Explanation ? Mode ? (query) p Builtin: next prime after parameter z Previous item in sequence ) Implicit closing parenthesis Query mode returns true if the input is in the sequence, and false if it is not. • Note current version uses Z instead of z – Stephen Feb 1 '19 at 4:53 # TI-BASIC, 37 bytes Prompt N N=1 For(A,2,√(N Ans+not(fPart(N/A End not(Ans Prompts for N and displays 1 if N is prime or 0 otherwise. Also in TI-BASIC: • I rewrote it. This would have done better as a comment as well. – Zenohm Sep 13 '15 at 20:19 • Nice. I modified my answer. Incidentally, I would have commented on your post but I created this account just to contribute this and didn't have enough reputation to comment. – Jakob Sep 13 '15 at 21:40 # TI-BASIC (nspire), 15 bytes f(n):=isPrime(n Uses the CAS isPrime() builtin. The environment by default adds an extra parenthesis on the end of the input, making it f(n):=isPrime(n) when the function is defined in the interpreter. • I'm assuming nspire doesn't allow unclosed parentheses? – Adalynn Aug 24 '17 at 0:24 • Yeah, it autocloses them. – user50198 Aug 24 '17 at 0:36 • I don't think that the TI-Nspire runs TI-BASIC. I was under the impression that it used a variant of Lua... – Scott Milner Aug 24 '17 at 0:38 • It also uses a form of lua for code in documents, but it does use basic for on-calculator programming (without an interpreter page) – user50198 Aug 24 '17 at 0:39 • If it autocloses them, then isPrime(n should work. – Adalynn Aug 24 '17 at 0:44 # Pyth, 3 2 bytes I can't see a simpler way of doing this. My ignorance continues to amaze me. P_ Explanation (if it needs one): P Prime function: factorization if positive, isPrime if negative _ Negate the implicit input Test suite • No need to subtract from zero, as _ performs negation. – Dennis Sep 6 '17 at 3:53 • @Dennis I tried that earlier, it didn't seem to work... – Stan Strum Sep 6 '17 at 3:54 # Python 3, 57 bytes k=int(input());print(all(k%j for j in range(2,k))and k>1) I think it's pretty self-explanatory. • @JonathanFrech No. – 0WJYxW9FMN Sep 22 '17 at 21:15 • @JonathanFrech The author of this problem asked for a full program. – 0WJYxW9FMN Sep 23 '17 at 17:47 # Funky, 39 bytes n=>{o=1for(i=2;i<n;i++)o=o&0<n%i o&n>1} Try it online! # Common Lisp, 64 bytes (print(=(loop as x from 1 to(setq n(read))count(=(rem n x)0))2)) Try it online! 57 bytes in Common Lisp REPL: (=(loop as x from 1 to(setq n(read))count(=(rem n x)0))2) # Groovy, 92 91 i=System.in.newReader().readLine()as int print i==2||i>1&&!(true in(2..i-1).collect{i%it<1}) Such a verbose way to read from stdin... • Welcome to Programming Puzzles & Code Golf! – Dennis Sep 26 '15 at 1:44 • Can you remove the space between ) and as? – hyper-neutrino Nov 10 '17 at 1:11 • @HyperNeutrino Good catch! – Kleyguerth Nov 10 '17 at 18:54 # ><>, 46 Bytes i> :1\/ln; ~\?:-/^?(2l~ %$}:{<;n0/?
l1- ?/1n;\

Takes input as an ascii character, prints 1 for primes, 0 for non-primes, including 1. Loops forever if input is 0 or negative.

## How it works:

> :1\
\?:-/

Fills the stack with integers between 0 and input, inclusive.

/ln;
~    /^?(2l~

Removes the top two values on the stack, 0 and 1. Tests if the length of the stack is <2; if it is, the value is either 1 or 2. In either case, its truthy/falsy value is the length of the stack; print it. If the length is greater than 2, it continues to the next loop.

%$}:{<;n0/? l1- ?/1n;\ Duplicates the value being tested from the bottom of the stack. Test if it's divisible by the value at the top. If it is, print 0. Otherwise, check that the stack length is not 1. If it is, the value being tested is prime; print 1. ### Edit: Added on to this program a bit, as a part in my attempt to conquer as much of project euler as possible in ><>. This is for Project Euler 7: Calculating the 10001st prime a:::***31[\>?!/l1-?\]r1-:?!/r:nao1+70. \/{*::+1<0<\%$}:{  <~~
\:}(?!\/-1l  \         ;nr\
\!?:-1:<\ ?!\~^.38
\] 1+70.

Comes in at 130 Bytes, although I didn't try very hard to golf it. Pushes 10000 to the stack (since we start at 3), makes a new stack, runs the primality test on the number, starting at 3. If it's prime, decrement the counter and increase the value being tested. If its not prime, just increment the value.

The go-fish interpreter was a life saver for this--it ran orders of magnitude faster than fish.py.

# Julia, 15 7 bytes

isprime

knocked down 8 bytes thanks to caird coinheringaahing

• Can you just submit isprime as a function submission? – caird coinheringaahing Dec 9 '17 at 18:07
• i suppose so? good point – EricShermanCS Dec 10 '17 at 4:32
• This doesn't work in julia 0.6+, (isprime was deprecated in 0.5 and moved to the Primes.jl package). I guess retitle this as Julia 0.5? – Lyndon White Dec 12 '17 at 6:56
• The challenge spec requires a full program. Also, isprime uses a probabilistic primality test and is thus cannot be used for this challenge. – Dennis Dec 12 '17 at 12:56

## AnyDice, 68 bytes

function: p A {loop N over {2..A/2}{if A/N*N=A {result:0}}result: 1}

I was wondering if AnyDice counted as a language for PCG.se purposes, and it turns out it does,

This is trial division, making use of the fact that AnyDice only supports integer (truncating) division.

### usage:

TryIt

output [p 333332]

outputs 0(100%)

output [p 333331]

outputs 1(100%)

# SNOBOL4 (CSNOBOL4), 105 bytes

N =INPUT
X =1
GT(N,1)	:F(C)
I	X =X + 1
OUTPUT =EQ(X,N) 1	:S(END)
C	OUTPUT =EQ(REMDR(N,X)) 0	:F(I)
END

Try it online!

I thought about putting my explanation in all caps, but that would just look silly.

This is the brute force approach: Test if N==1, and output 0 on success, then increment X. If we reach a point where X==N, then we have found a prime number and we output 1 and terminate. If we reach a point where N %% X == 0, then we output 0.

I am still learning to golf in SNOBOL, so I think it should be possible to make this shorter.

# Broccoli, 107 bytes

(fn p ($a) (:=$d 0) (for $i in (range 2$a) (if (= $a (*$i (int (/ $a$i)))) (:= $d (+$d 1)))) (= $d 1)) With whitespace added: (fn p ($a)
(:= $d 0) (for$i in (range 2 $a) (if (=$a (* $i (int (/$a $i)))) (:=$d (+ $d 1)) ) ) (=$d 1)
)
(map p (range 1 20))

This language is a bit of a pain to work with:

• You can't take input.

• You can't define a function from within a function.

• You can't pass a lambda to a map or reduce or a filter.

• There is no modulo function.

I'm sure this could be shorter somehow, but I'm just not seeing it.

# Implicit, 3029 21 bytes

<2è;:(-1>1?{;|_ñè};).

Try it online!

Whew, another 10 bugs uncovered during the writing of this program. This uses trial division.

While SimpleStack uses a ... stack, I'm going to call two stack values variables. The input will be variable i and the trial-division loop counter will be variable m. Note I might've messed up this explanation somewhere along the road of golfing.

<2è;:(-1>1?{;|_ñè};).
implicit input i
<2                     push i < 2
è                    exit without implicit output if truthy
;                   pop i < 2
:                   set m to input
(.............)    do
-1                 decrement m
>1               push m > 1
?{.....}       if true
;             pop m > 1
|            duplicate stack (stack: i, m -> i, m, i, m)
_           push i % m
ñ          compute logical NOT on i % m (truthy if i % m falsy)
è         exit without implicit output if truthy
;      pop top of stack (NOT(i % m) or m > 1)
)    while m > 0
.   increment

If the input is 0 or 1, it will print nothing, so the output will be falsy. If the input is not prime, the second è exits without implicit output (making hte output empty and therefore falsy). If the input is prime, it will reach the end of the program, and the top of stack will always be 0. . increments it, turning it to 1 (truthy). Implicit output.

## 095, 35 bytes

1Xid1.=(DD,,{d_.%(yX]D}dYs]D1.=[1s]

Returns 0 for composite and 1 for prime.

Explanation:

1X                                  ~ Set True to X
id                                ~ Take input and duplicate
1.=                             ~ Check if equal to 2
(DD                          ~ If not, delete last two items
,,                        ~ Subtract 2
{                       ~ For that many times,
d_.%                   ~ see if iterator divides into input
(yX]               ~ If it does, set False to X
D}             ~ Delete last item, close loop
dYs]         ~ Duplicate input, print X
D1.=[1s] ~ If input = 2, say True