215
\$\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\$
8
  • 2
    \$\begingroup\$ 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/… \$\endgroup\$ – Lyndon White Dec 12 '17 at 6:21
  • 2
    \$\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\$ Could a case be made for locking this challenge and posting a new, less restrictive one? \$\endgroup\$ – Shaggy Jun 25 '18 at 12:59
  • 2
    \$\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

310 Answers 310

1
7 8 9 10
11
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\$
0
\$\begingroup\$

Wren, 48 43 bytes

I feel surprised that I think better when using W instead of Wren. Also, the 1-primalty problem is fixed.

Fn.new{|i|(1..i).where{|x|i%x==0}.count==2}

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Fails for 1, just like your previous answer. \$\endgroup\$ – Jo King Dec 21 '19 at 22:23
0
\$\begingroup\$

Spice, 93 bytes

;i;m;t;c;r@REA i;ADD 0 1 c;SUB i 1 m;ADD c 1 c;MOD i c t;SWI t 1 9;SWI c m 3;ADD 0 1 r;OUT r;

This outputs [1] for a prime, and [] for a non-prime.

Un-golfed explanation:

;i;m;t;c;r@ - Declare vars (@ marks end of declarations)
(line 0) REA i;      - Read input into i
(line 1) ADD 0 1 c;  - Set counter c = 1
(line 2) SUB i 1 m;  - Set store input-1 as m
(line 3) ADD c 1 c;  - Start of loop, c+=1
(line 4) MOD i c t;  - Store mod of  t=i%c
(line 5) SWI t 1 8;  - if t < 1 (if non-prime, leave loop) to line 8
(line 6) SWI c m 3;  - if c < m continue loop (go to line 3)
(line 7) ADD 0 1 r;  - set result as truthy value - r = 1
(line 8) OUT r;      - output result, r
\$\endgroup\$
0
\$\begingroup\$

tq, 10 bytes

?-1!xp*p%?

Explanation

Uses Wilson's theorem to do the prime-checking.

?-1!        # Generate all numbers from 2 to input - 1
    x,      # Preserve this value, prevent it from being printed
      p*p   # Generate all possible combinations of those numbers
         %? # Does the product of any combination equal to the input?
\$\endgroup\$
0
0
\$\begingroup\$

Symbolic Raku, 17 bytes

$_=?($_%%[^] ^$_)

Try it online!

Suprisingly, this is shorter than the my previous Raku answer, though one byte longer than using the built-in

Explanation:

$_=                # Set the output to
   ?(           )  # The boolean of
     $_            # If the input is
       %%          # Divisible by
         [^]       # Only one of
             ^$_   # The range from 0 to input-1
\$\endgroup\$
0
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 62 bytes

int n=int.Parse(ReadLine()),i=2;while(n%i>0&i++<n);Write(n<i);

Try it online!

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

LCGFuck inputNumeric=true, 138 bytes

(Will turn this into a GitHub repository soon)

1 1im1-1
1 1om2-1
1 1om1 1
<{>>>o+1 1m0<<om
<}>>1-1om0>+om
<<<++1 1 1 32
1 4 12 69 4
1 1 7 78 2
{>>>+++++c+c+++++c+++<<c<{+}}>>>c++c<c+c+c

Try it online through this TIO JS interpreter

A brainfuck variant invented by me but uses a list of linear congruential generators (LCGs) instead of cells.

The \$N=1\$ case took too much more bytes to deal with.

Ungolfed and Explanation

1 1 im 1 -1                    # Storage for the input, since the input can only be retrieved once
1 1 om 2 -1                    # Used to prevent wrapping. Necessary for handling N = 1 case
1 1 om 1 1                     # Counts up from 2 to N
<{                             # While N % counter == 0 (If N == 1 the loop is skipped)
 >>>o+                         #  Gets and increments the counter value
 1 1 m 0 <<om                  #  Use a new LCG to check N % counter
<}                             # Loop
>>
1 -1 om 0 >+om                 # The output of this LCG will be 2 if N is prime
<<<++                          # Move two states forward (2 - 2 = 0 if prime)
1 1 1 32                       # LCG for space
1 4 12 69 4                    # LCG for E, I, M
1 1 7 78 2                     # LCG for N, O, P, R, T
{>>>+++++c+c+++++c+++<<c<{+}}  # Output "NOT " if this LCG is not at state 0
>>>c++c<c+c+c                  # Output "PRIME"

Technical Details

(Copied from my obsolete challenge proposal on an LCGFuck interpreter)

An LCG is defined with 5 numbers, like 12345 678 90 -123 45. The last two numbers are optional and default to 0.

LCGFuck has 3 storage variables, the LCG list, the number list and the number memory. The functions are as follows:

  • LCG list: Cyclic list that stores all LCGs created. Every entry is in turn a list of 5 numbers in the order [a, b, c, d, e] as notated in the introduction. It has a pointer that controls which LCG is chosen at the moment, and moves in a cycle through the list.
  • Number list: Ordinary list that stores the numbers for LCG definition. It can store at most 5 numbers.
  • Number memory: A single variable that can be read and written with an input or an LCG output.

LCGFuck has 14 operators, namely:

  • \n (newline): Creates an LCG with the numbers in the order of [a, b, c(, d(, e))] and clears the list if the number list contains 3 or more numbers. No-op if the number list contains no more than 2 numbers.
  • <: Shifts to the previous LCG circularly (back to the last when moving from the first).
  • >: Shifts to the next LCG circularly (back to the first when moving from the last).
  • +: Moves the current LCG to the next state (calculates x' = (a * x + b) mod c)
  • c: Prints the output of the current LCG as a character (with the output as the codepoint).
  • n: Prints the output of the current LCG as a number (with a trailing space)
  • o: Writes the output of the current LCG to number memory
  • i: Reads a value from the input and writes it to number memory. There is two input mode, one reading a character one time (inputNumeric=false), and one reading a number one time (inputNumeric=true)
  • s: Reads the value from number memory and seeds the current LCG with it
  • m: Reads the value from number memory and pushes it to the number list
  • []: Output loop. Executes the loop if the current LCG is non-zero
  • {}: State loop. Executes the loop if the state of the current LCG is non-zero

An integer, optionally with a negative sign at the front, pushes the number to the number list. Any characters other than the newline \n and any of -0123456789[]{}<>+cimnos are no-ops.

The code runs linearly from the first characters, except when loop ends are encountered. Loops can be nested but must be paired accordingly from the innermost loop to the outermost loop.

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

Help, WarDoq!, 1 byte

p

Outputs 1 if the input is prime (positive or negative, differs from the other solution), 0 otherwise.

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

GolfScript, 14 bytes

~.,{*.!+}*.*\%

Try it online!

This outputs this version of Wilson's theorem, used in other answers to this question:

(n-1)!² (mod n)

This outputs 1 if it is a prime and 0 if it is not.

~                 # Push n
 .,               # Range from 0 to (n-1)
   {*.!+}         # Push block without executing
         *        # Fold
          .*      # Square, it could also be 2?, but for large values of n there would be an error message
            \%    # Mod n

What the block does:

    *             # Multiply
     .!           # Is it 0?
       +          # Add 1 if it was 0 and 0 if it wasn't

This uses 3 bytes to avoid the 0, there are ways of removing it from the array using 2:

~.,(;{*}*.*\%

Try it online!

The problem here is when the input is 1, in this case after removing the 0 we wouldn't have any number to multiply.

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

ArnoldC, 707 bytes

IT'S SHOWTIME
HEY CHRISTMAS TREE n
YOU SET US UP 0
GET YOUR ASS TO MARS n
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
HEY CHRISTMAS TREE k
YOU SET US UP 2
HEY CHRISTMAS TREE l
YOU SET US UP 1
HEY CHRISTMAS TREE p
YOU SET US UP 1
GET TO THE CHOPPER l
HERE IS MY INVITATION n
LET OFF SOME STEAM BENNET k
ENOUGH TALK
STICK AROUND l
GET TO THE CHOPPER p
HERE IS MY INVITATION n
I LET HIM GO k
LET OFF SOME STEAM BENNET 0
KNOCK KNOCK p
ENOUGH TALK
GET TO THE CHOPPER k
HERE IS MY INVITATION k
GET UP 1
ENOUGH TALK
GET TO THE CHOPPER l
HERE IS MY INVITATION n
LET OFF SOME STEAM BENNET k
KNOCK KNOCK p
ENOUGH TALK
CHILL
TALK TO THE HAND p
YOU HAVE BEEN TERMINATED

Try it online!

Doesn't look like anyone's posted an ArnoldC answer here yet, and I thought the best way to respect the Terminator would be by writing an answer in his language.

Explanation with pseudocode:

Begin main
  Declare n
  Set to 0

  Assign result of method call to n
    Call method
      Read integer (the method to be called)

  Declare k
  Set to 2

  Declare l (boolean)
  Set to 1/true

  Declare p (boolean)
  Set to 1/true

  Assign l:
    Push n to the stack
    Greater than k
  End assign

  While l
    Assign p:
      Push n to the stack
      k mod that
      Greater than 0
      And p
    End assign
    
    Assign k:
      Push k to the stack
      Add 1
    End assign
    
    Assign l:
      Push n to the stack
      Greater than k
      And p
    End assign
  End while

  Print p
End main
```
\$\endgroup\$
1
7 8 9 10
11

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.