192
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Can I take inputs as negative numbers, where abs(input) would be the number I am testing? \$\endgroup\$ – Stan Strum Sep 6 '17 at 3:40
  • \$\begingroup\$ No, the input is a strictly positive integer. \$\endgroup\$ – Dennis Sep 6 '17 at 3:44
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Dennis Dec 12 '17 at 12:51
  • 1
    \$\begingroup\$ @Shaggy Seems like a question for meta. \$\endgroup\$ – Dennis Jun 25 '18 at 13:44
  • 1
    \$\begingroup\$ Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. \$\endgroup\$ – Shaggy Jun 25 '18 at 13:45

287 Answers 287

0
\$\begingroup\$

AniRad, 30 29 bytes

Probably not the shortest program:

 #
 W
 I
 P
 v
 >~1=
 ~
 0
 =

Another possible program is, 30 bytes:

#WIP>v~0=
     ~
     1
     =

Information:

  • # = Starting point, pointer direction is to the right
  • W = User input, directly adds this to the stack
  • I = If-statement, or is equal to
  • P = If the stack is prime
  • v = If false, assign the pointer direction to the right
  • > = If true, assign the pointer direction to the bottom
  • ~ = Reset the stack
  • 0 / 1 = Assign the stack to 0 / 1
  • = = Print the result of the stack

The following paths are executed in this program:

  • If W = prime, path = WIP~1=
  • If W != prime, path = WIP~0=

This is a 2D esolang I created, which looks a bit like a magic square. This is a programming language in it's early stage, so a lot of functions aren't implemented yet. Also, a lot of bugs might occur, if you find a bug, please report it.

\$\endgroup\$
0
\$\begingroup\$

JavaScript function golf, 16 13 bytes

p(pr(iai()));

function golf has just got a primality test function, that you can try online in the console on the language page! The primality test function took me 3 commits on GitHub.

Returns 1 if prime, else 0.

The variant with the alert costs us 15 bytes.

p2a(pr(iai()));

And... the first ever explanation of a function golf program!

p(pr(iai()));
p( prints
  pr( if
     iai() an integer input into a prompt
          ) is prime
           ); into the console.
\$\endgroup\$
  • \$\begingroup\$ So, why does this have a negative score? \$\endgroup\$ – cat Mar 20 '16 at 2:18
  • \$\begingroup\$ @cat I assume it's because people think it's a function. The challenge calls for a complete program and this has function in the name. It looks like a full program to me though. \$\endgroup\$ – DanTheMan Jun 23 '16 at 22:40
0
\$\begingroup\$

Gogh, 1 byte

e

Run using:

$ ./gogh oi "e" <input>

The operator e pushes the primality of the TOS. Implicit input and output.

\$\endgroup\$
0
\$\begingroup\$

Pylongolf2, 4 bytes

cnz~

Explanations:

cnz~
c    read input
 n   convert to integer
  z  primality test (beta8+)
   ~ print it.
\$\endgroup\$
0
\$\begingroup\$

Racket, 31 bytes

(require math)(λ(n)(prime? n))

A standard library has a function for it. If we want to keep the import but write our own, we could do this for 51 bytes:

(require math)(λ(n)(equal?(list 1 n)(divisors n)))

On the other hand, if builtins were disallowed, for 64 55 bytes, thanks to @MatthewButterick, we can write our own:

(λ(n)(=(count(λ(i)(=(modulo n(+ i 1))0))(range n))2))

Old one, for 64:

(λ(n)(equal?'(1)(filter(λ(i)(zero?(modulo n i)))(range 1 n))))
\$\endgroup\$
  • \$\begingroup\$ 55 bytes: (λ(n)(=(count(λ(i)(=(modulo n(+ i 1))0))(range n))2)) \$\endgroup\$ – Matthew Butterick Apr 11 '16 at 5:49
  • \$\begingroup\$ @MatthewButterick Nice! I'll add that. \$\endgroup\$ – cat Apr 11 '16 at 10:47
  • \$\begingroup\$ @MatthewButterick from the docunentation, it seens like range needs two args, but I guess I was very tired when I was reading it. \$\endgroup\$ – cat Apr 11 '16 at 10:57
  • \$\begingroup\$ Also, (λ(n)(prime? n)) is the same as prime?, so if (require math)(λ(n)(prime? n)) is an acceptable 31-byte answer, then (require math)prime? ought to be an acceptable 20-byte answer \$\endgroup\$ – Matthew Butterick Apr 11 '16 at 17:29
  • \$\begingroup\$ @MatthewButterick I was very tired when I edited that in last night and I swore I read your name correctly... sorry about that :P \$\endgroup\$ – cat Apr 11 '16 at 19:20
0
\$\begingroup\$

Sage, 22 bytes

lambda N:N in Primes()

Try it online

\$\endgroup\$
  • \$\begingroup\$ (Super old but...) Submissions have to be full programs. \$\endgroup\$ – totallyhuman Sep 2 '17 at 2:17
0
\$\begingroup\$

UGL, 26 bytes

id?u:cuul^^/_c=?_=ocd$:_u:

Try it online!

How it works:

id?u:cuul^^/_c=?_=ocd$:_u:
id?u:                       int i = input(); if i==1: i=0;
     cuu                    int test = 2;
        l              _u:  while test != -1:
         ^^/_c=?                if i % test == 0:
                _=o                 print(i==test);
                   cd$              test = -1;
\$\endgroup\$
0
\$\begingroup\$

Fith, 30 bytes

*math* load line >int prime? .

This language isn't great for golfing...

This uses the prime? function in the *math* library. Here's a version using only builtins, which is pretty much what the library function does:

line >int -> x 2 x range { x swap mod } map all .

Explanation:

line           \ line of input
>int           \ cast to int
-> x           \ set x to the top of the stack
2 x            \ push 2, then x
range          \ range from [2, x)
{ x swap mod } \ anonymous function which calculates x mod its argument
map            \ map that function onto the generated range
all            \ return 1 if everything in the list is Boolean true, else 0
.              \ print the top of the stack

You may be able to tell that this language is just a little bit inspired by Forth. It also takes cues from PostScript, Python, and functional programming.

\$\endgroup\$
0
\$\begingroup\$

reticular, 6 bytes

in@pp;

A four-byte function:

[@p]

Explanation

in@pp;
i       take input
 n      convert to number
  @p    check for primality
    p   print
     ;  terminate
\$\endgroup\$
  • \$\begingroup\$ (non-competing) language is newer than the challenge. \$\endgroup\$ – mbomb007 Sep 22 '16 at 19:39
  • \$\begingroup\$ @mbomb007 is that really necessary? This is a catalog. \$\endgroup\$ – Conor O'Brien Sep 22 '16 at 20:24
  • \$\begingroup\$ Oh, idk. I guess not then \$\endgroup\$ – mbomb007 Sep 22 '16 at 20:29
0
\$\begingroup\$

R, 19 Bytes

 ->n;sum(!n%%1:n)==2

Starts with a right assign to n. i.e. precede the code with the desired n. then it merely checks primeness of n. Prints TRUE or FALSE implicitly

If you don't like right assign as an input method then for 24 bytes you get:

sum(!(n=scan())%%1:n)==2
or
n=scan();sum(!n%%1:n)==2

Which assigns within the operator.

If you want explicit answer printing, then for 28 bytes:

 p=function(n)sum(!n%%1:n)==2
\$\endgroup\$
0
\$\begingroup\$

RProgN, 102 Bytes

 'i' asoc true i 1 - ] 1 > while [ 'a' asoc i a / i a // = if [ [ false else [ end a 1 - ] 1 > end [ [

Explanation

 'i' asoc           # Associate the implicit input with i
true i              # Push true to the stack, push i to the stack
1 -                 # Subtact 1 from the top of the stack
] 1 >               # Duplicate the top value of the stack, compare that it's larger than 1
while               # While the top of the stack contains a truthy value
    [               # Pop the top of the stack (The conditional in this case)
    'a' asoc        # Associate the top of the stack with a
    i a /           # Push i divided by a to the top of the stack
    i a // =        # Push i integeral divided by a to the top of the stack, compare the top and underneith the top for equality
    if              # if i/a = floor(i/a), essentially
        [ [ false   # Pop the conditional, and the 'true' we slipped in earlier, push false in in place of it
    else            #
        [           # Pop the conditional anyway
    end             #
    a 1 - ] 1 >     # Subtract 1 from a, duplicate it, and compare that it's larger than 1
end                 #
[ [                 # Pop the conditional, the value of a, which leaves only the bottom value we previously inserted, which is implicitly printed

RProgN doesn't have any method of input as of yet, as such, Any input needs to be written in pure form at the very start of the code, such that 23 'i' asoc .... An Extra byte is added to the score, because a space is required in front of any command.

\$\endgroup\$
0
\$\begingroup\$

Pyret, 58 bytes

i=1
(i == 1) or any({(x):num-modulo(i,x) == 0},range(2,i))

You can try this online by copying the code into the online Pyret editor!

Pyret programs are designed to be run in the online editor, so there's no way to read from STDIN. Here, the variable i represents the input. The program returns true if i is not prime and false if i is prime.

\$\endgroup\$
  • 1
    \$\begingroup\$ If there's no input from STDIN, maybe its best to do a function instead \$\endgroup\$ – Jo King Jun 20 '18 at 0:14
  • 1
    \$\begingroup\$ @JoKing This challenge doesn't allow functions. \$\endgroup\$ – Ørjan Johansen Jun 20 '18 at 1:46
0
\$\begingroup\$

Yabasic, 43 bytes

Input""n
For d=2To n
p=p+!Mod(n,d)Next
?p=1

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pepe, 53 bytes

Uses trial-and-error modulus, so gets slower in larger integers.

REeEREErEEEEErREEeEeEReeREEEEeEeEReRererrEEreEErEeree

Try it online! Outputs 0 for truthy and none for falsy.

\$\endgroup\$
0
\$\begingroup\$

strict, 122 bytes

num t
num i 2
num r
get t
jen t 1 n
jen t 2
mrk m
set r t
mod r i
add i 1
jen t i
jgn r 0 m
mrk n
out: not 
mrk
out: prime

Reads input from stdin. Because the language doesn't have truthy/falsy values, it outputs either "prime" or "not prime".

Ungolfed:

num target
num i 2
num remainder
get target

# exceptions
jen target 1 not
jen target 2 prime

# loop from 2 to target
mrk main
    set remainder target
    mod remainder i
    add i 1
jen target i prime
jgn remainder 0 main

mrk not
    out: not\s

mrk prime
    out: prime\n
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Golf Stack Exchange! I'm not sure how best to test this; do you have a link to some sort of online interpreter? I can't access the link thanks to my stupid corporate network restrictions. \$\endgroup\$ – Giuseppe Jun 28 at 15:50
  • \$\begingroup\$ @Giuseppe Unfortunately, there is no online interpreter. How much are you restricted? Would a direct mega.nz download link work? \$\endgroup\$ – programical Jun 28 at 16:12
0
\$\begingroup\$

Rust, 124 bytes

fn main(){let s=&mut"".into();std::io::stdin().read_line(s);let n=s.parse().unwrap();print!("{}",n>1&&(2..n).all(|x|n%x>0))}

Try it online!

How complicated it has to be to read an integer from stdin...

\$\endgroup\$
-1
\$\begingroup\$

Python 3.7, 92 bytes

n=int(input());o=1
for i in range(1,n):
 if n/i==n//i and i!=1 or not n or n==1:o=0
print(o)
\$\endgroup\$
  • \$\begingroup\$ Welcome! Consider adding an explanation and/or a link to an online interpreter, such as TIO. Code-only answers tend to be automatically flagged as low quality. \$\endgroup\$ – mbomb007 Jul 26 at 1:20
  • \$\begingroup\$ This program gives wrong answers for 0 and 1, which are not prime. \$\endgroup\$ – mbomb007 Jul 26 at 1:24
  • \$\begingroup\$ It doesn't need to be correct for 0 (input is strictly positive), but 1 is a case that needs to be managed carefully \$\endgroup\$ – Jo King Jul 26 at 1:41
  • \$\begingroup\$ You can remove a lot of the extra conditions in the if statement. As a start, 63 bytes \$\endgroup\$ – Jo King Jul 26 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.