235
\$\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\$ Dec 12, 2017 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, 2017 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, 2018 at 12:59
  • 2
    \$\begingroup\$ @Shaggy Seems like a question for meta. \$\endgroup\$
    – Dennis
    Jun 25, 2018 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, 2018 at 13:45

368 Answers 368

1
5 6
7
8 9
13
2
\$\begingroup\$

Stax, 2 bytes

|p

Run and debug online!

Added for completeness. An internal.

\$\endgroup\$
2
\$\begingroup\$

COBOL (GNU), 305 bytes ( +5 for compiler flags)

ID DIVISION.PROGRAM-ID.A.DATA DIVISION.WORKING-STORAGE SECTION. 1 I PIC 9(9). 1 V PIC 9(9). 1 R PIC 9(9). 1 Q PIC 9(9). 1 P PIC 9 VALUE 1.PROCEDURE DIVISION.ACCEPT V PERFORM VARYING I FROM 2 BY 1 UNTIL I=V DIVIDE I INTO V GIVING Q REMAINDER R IF R=0 THEN MOVE 0 TO P END-IF END-PERFORM DISPLAY P STOP RUN.

Compile with -free flag. (This allows ignoring formatting.)

Try it online!

Ungolfed version:

IDENTIFICATION DIVISION.    *> Required in every program header.
PROGRAM-ID. A.

DATA DIVISION.
WORKING-STORAGE SECTION.
    01 I PIC 9(9).          *> Loop index
    01 V PIC 9(9).          *> Value to test
    01 R PIC 9(9).          *> Remainder
    01 Q PIC 9(9).          *> Quotient
    01 P PIC 9 VALUE 1.     *> Is prime?

PROCEDURE DIVISION.
    ACCEPT V                                    *> Get value from input
    PERFORM VARYING I FROM 2 BY 1 UNTIL I>V/2   *> for (i = 2; i <= v/2; i++)
        DIVIDE I INTO V GIVING Q REMAINDER R    *>     Q = V/I; R = remainder(V/I)
        IF R=0 THEN MOVE 0 TO P END-IF          *>     If remainder is zero, not prime
    END-PERFORM
    DISPLAY P               *> Output result (1 or 0)
    STOP RUN.
\$\endgroup\$
2
\$\begingroup\$

Zephyr, 88 bytes

input n as Integer
set f to 0
for i from 1to n
if(n mod i)=0
inc f
end if
next
print f=2

Try it online!

Uses the "n must have exactly two perfect divisors in the inclusive range [1, n]" approach. Run a for loop over that range, count the numbers i for which n mod i is zero, and output at the end whether the count equals 2.

\$\endgroup\$
2
\$\begingroup\$

Julia 0.6, 44 bytes

n=parse(Int,ARGS[]);show(sum(n%(1:n).<1)==2)

Try it online!

Since the existing answers are invalid for the challenge and/or outdated by newer Julia versions, I'm adding a Julia answer that works in Julia 0.6.

For Julia 0.7 (and to avoid deprecation warnings in 0.6), this needs just one more byte (% becomes .%):

45 bytes

n=parse(Int,ARGS[]);show(sum(n.%(1:n).<1)==2)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 20 bytes

say get~~$_%%one ^$_

Try it online!

There's also the built-in is-prime, but I thought it would be more interesting to do it without it. Surprisingly, this is only 4 bytes longer.

Explanation:

    get                # Get a line of input
       ~~              # Smartmatch it by setting $_ to input
         $_%%          # Is input divisible by
             one       # Only one of
                 ^$_   # The range 0 to input-1?
say                    # And print

Note that this works because n%%0 is boolified to False.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 3 bytes

fнQ

find all factors and see if last one equals input.

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Built-ins are allowed, so just p is enough. \$\endgroup\$
    – Grimmy
    Mar 29, 2019 at 13:32
2
\$\begingroup\$

Gol><>, 4 bytes

ISPh

Thanks to ASCII-only for letting me now I didn't need 2 bytes, since it was redundant.

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ The ?1 is needed?????? \$\endgroup\$
    – ASCII-only
    Feb 20, 2019 at 16:07
  • \$\begingroup\$ @ASCII-only Thank you for pointing that out, I didn't even think of that. Fixing it now! \$\endgroup\$ Feb 20, 2019 at 17:23
  • 2
    \$\begingroup\$ At least in this particular implementation of Gol><>, P is implemented by the` is_probably_prime` function. Unfortunately, this challenge requires a deterministic primality test. \$\endgroup\$
    – Dennis
    Feb 20, 2019 at 19:37
  • \$\begingroup\$ @Dennis The is_probably_prime function is a wrapper for the sympy isprime function, which is deterministic up to \$2^{64}\$. If the sympy library is not available, then it does a non-deterministic check. \$\endgroup\$
    – Jo King
    Mar 15, 2019 at 1:58
2
\$\begingroup\$

dc, 17 22 bytes

?d*5+v[dz%rdz<M*]dsMxp

Try it online!

I've been on a bit of a dc kick lately and although there's already a dc solution here, this is 10 5 bytes shorter. It follows the I/O request of the original question, which does add two bytes for the explicit input and output (rather than the usual rules these days that allow implicit stack I/O), but okay.

This outputs zero for composite numbers and non-zero for primes.

How it works: this program builds a stack consisting of the modulo of the input with the current stack size (so the stack looks like, from bottom to top, i%2, i%3, i%4, ...), then when it decides it's gone far enough (stack size = input) it multiplies the stack as it unwinds the recursion.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ This fails for 1 and 2. \$\endgroup\$ Mar 16, 2019 at 0:22
  • \$\begingroup\$ Oof, you're right. Not sure how I missed that. It took me five bytes to fix (by precomposing with d*5+v, i.e., x -> int(sqrt(x^2+5)), i.e., 1->2, 2->3, n->n for n>2) \$\endgroup\$ Mar 18, 2019 at 18:09
2
\$\begingroup\$

K (oK), 14 19 bytes

Solution:

2=+/d=_d:x%!x:. 0:`

Try it online!

Example:

root@c957fa0dccbd:/ok# echo 1 | node repl.js examples/prime.k
0
root@c957fa0dccbd:/ok# echo 2 | node repl.js examples/prime.k
1
root@c957fa0dccbd:/ok# echo 5 | node repl.js examples/prime.k
1
root@c957fa0dccbd:/ok# echo 97 | node repl.js examples/prime.k
1

Explanation:

Calculate number of factors for input, if equal to 2, then it's prime.

2=+/d=_d:x%!x:. 0:` / the solution
                0:` / read from stdin
              .     / value (ie convert "123" > 123)
            x:      / store input as x
           !        / range 0..x
         x%         / x divided by ...
       d:           / store as d
      _             / floor
    d=              / d equal to ...
  +/                / sum
2=                  / 2 equals?
\$\endgroup\$
2
\$\begingroup\$

tinylisp, 23 bytes

There's a library function.

(load library
(prime? 1

(Since tinylisp is incapable of taking user input, "For scoring purposes, submit the program that corresponds to the input 1.")

Try it online!


Here's a 112-byte solution using only the base language, no library functions:

(d D(q((F A N)(i(l A N)(D F(a F A)N)(e N A
(d _(q((F N)(i(D F 0 N)(e F N)(_(a 1 F)N
((q((N)(i(e N 1)0(_ 2 N))))1

The first line defines a function D that takes a factor F, an accumulator A (initially 0), and a number N; it returns 1 if N is divisible by F, 0 otherwise.

The second line defines a function _ that takes a minimum factor F and a number N; it returns 1 if N is coprime to all numbers from F to N-1, 0 otherwise.

The third line constructs an anonymous function that takes a number N; it returns 0 if N is 1, and otherwise calls _ with number N and minimum factor 2. As above, the scored code calls the anonymous function with an argument of 1.

\$\endgroup\$
2
\$\begingroup\$

DIVCON, 8 bytes

Prequisities: Enter 1 into the INPUT_MAX prompt.

i*[;-=o]

Explanation

"Partition" by * here means solving x * y = a - a is the original accumulator value. x and y needs to be as close as possible. In addition, the following equality must be satisfied: x>=y

         Description     | Example(0) | Example(1)
         ----------------+------------+-----------
i        Take an input   |  12        | 13
 *       Partition by *  | 4, 3       | 13, 1
         ----------------+------------+-----------
  [      Left branch     |   4        | 13
         Do nothing      | *discarded*| *discarded*
         ----------------+------------+------------
   ;     Right branch    | 3          | 1
    -    x - 1           | 2          | 0
     =   x == 0?         | 0          | 1
      o  Print this value| OUT: 0     | OUT: 1
         ----------------+------------+------------
       ] End both branches

Actually, there is another implicit reverse computation. But, since INPUT_MAX is 1, the extra prompting from i is disabled.

\$\endgroup\$
2
\$\begingroup\$

MAWP, 48 46 54 bytes

@1A<:.>{1A<1:.>2M}!1A[/!!\!/P\!/WA<:.>{%}\2A?0{1M}]1:.

-2 bytes from Dion's suggestion.

+8 bytes after fixing the problem with 1 as input.

Prints 1 for prime and 0 for non-prime. Can probably be golfed by a few more bytes, since it checks for 2 at the beginning first.

Try it!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Should work as expected now. \$\endgroup\$
    – Razetime
    Aug 26, 2020 at 9:10
  • \$\begingroup\$ Looks good now. Can you explain how it works? \$\endgroup\$
    – Dingus
    Aug 26, 2020 at 9:16
  • 1
    \$\begingroup\$ checks for 1 first, then 2, then moves on with a loop till it finds any divisor. \$\endgroup\$
    – Razetime
    Aug 26, 2020 at 9:17
2
\$\begingroup\$

ArnoldC, 707 636 618 bytes

Saved 71 89 bytes thanks to pppery!

LISTEN TO ME VERY CAREFULLY f
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE n
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
HASTA LA VISTA, BABY

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.

\$\endgroup\$
4
  • \$\begingroup\$ Only 636 bytes as a function. \$\endgroup\$ Mar 19, 2021 at 21:15
  • \$\begingroup\$ @pppery THANKS. ENOUGH TALK. HASTA LA VISTA, BABY. \$\endgroup\$
    – user
    Mar 19, 2021 at 21:59
  • \$\begingroup\$ Can be further reduced to 618 bytes by using the nonstandard output technique of a function outputting to STDOUT, which is allowed since functions may output via the same methods as full programs \$\endgroup\$ Mar 22, 2021 at 22:45
  • \$\begingroup\$ @pppery Thanks again, I never thought anyone could golf in ArnoldC! \$\endgroup\$
    – user
    Mar 22, 2021 at 23:05
2
\$\begingroup\$

CSASM v2.1.2.2, 207 235 bytes

Prints a 1 (truthy) if the input is a prime integer, 0 (falsy) otherwise.
Truthy values in CSASM are non-zero numbers, non-\0 chars and non-null strings/arrays/objects.
Falsy values in CSASM are zero, the \0 character or null strings/arrays/objects.

func main:
in ""
conv i32
pop $a
push $a
push 2
comp.gte
push $f.o
brtrue a
br b
.lbl a
push 2
dup
pop $1
push $a
sub
brfalse d
.lbl c
clf.o
push $a
push $1
rem
brfalse b
inc $1
push $1
push $a
comp.lt
push $f.o
brtrue c
.lbl d
push 1
print
ret
.lbl b
push 0
print
ret
end

Commented and ungolfed:

func main:
    ; Get the input, convert it to an integer and store it in the accumulator
    in ""
    conv i32
    pop $a

    ; if $a < 2, then $a is not prime
    push $a
    push 2
    comp.gte
    push $f.o
    brtrue initLoop
    br notPrime

    .lbl initLoop
    ; Initialize the loop counter and check if $a == 2
    ; If $a is 2, return truthy early
    push 2
    dup
    pop $1
    push $a
    sub
    brfalse prime

    .lbl loop
        ; Clear the comparison flag
        clf.o

        ; If $a % $1 == 0, then $a is not prime
        push $a
        push $1
        rem
        brfalse notPrime

        ; Loop until $1 >= $a
        inc $1
        push $1
        push $a
        comp.lt
        push $f.o
        brtrue loop

    .lbl prime
    ; $a is prime
    push 1
    print
    ret

    .lbl notPrime
    ; $a is not prime
    push 0
    print
    ret
end
\$\endgroup\$
2
\$\begingroup\$

Arduino, 146 143 bytes

#define S Serial
int p=0,d=1;void setup(){S.begin(300);}void loop(){while(S.available())p=p*256+S.read();if(p&&!(p%++d%p)){S.print(p==d);p=0;}}

Based on the current top answer for C++. I'm not convinced my adaptation is optimal.

Reading in a number from the Serial input is actually pretty annoying in Arduino. Serial.available() gives the number of unread bytes, but unfortunately it caps out at 64, which is too small for me to use unary for this challenge. Instead, I opted to interpret the input as a byte array.
Bitshift is lower precedence than addition, and (p<<8) is longer than p*256 (note the parentheses needed).
In this case, a while loop is actually shorter than a for loop, by 1 character.

Explanation:

#define S Serial /* This macro is worth it in the end, but not by much */

int p = 0, // the case p = 0 is also taken to mean not to even attempt this anyways
    d = 1;

void setup() {
  S.begin(300); // standard is 9600 but 300 is shorter
}

void loop() {
  while (S.available()) // truthy while there are unread bytes
    p = p * 256 + S.read();

  if (p && !(p % ++d % p)) { // second condition from the C++ answer
    S.print(p == d); // method from the C++ answer
    p = 0; // reset this to stop trying
  }
}

I suppose this technically comes with the caveat that no byte of the number can be 0 (so 256 wouldn't work; it's 0x0100), as the serial port takes in null-terminated strings. That said, it's only two more characters to make a version that accepts numbers written in decimal -- just replace p*256+S.read() with p*10+S.read()-48.

Original:

int p=0,d=1;void setup(){Serial.begin(300);}void loop(){while(Serial.available())p=p*256+S.read();if(p&&!(p%++d%p)){Serial.print(p==d);p=0;}}
\$\endgroup\$
2
\$\begingroup\$

Rust (full program), 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
  • 2
    \$\begingroup\$ using args is shorter 105 bytes \$\endgroup\$
    – Hydrazer
    Nov 1, 2021 at 15:11
2
\$\begingroup\$

K (ngn/k), 18 bytes

1=+/1>(!x)!'x:.1:0

Try it online!

\$\endgroup\$
2
\$\begingroup\$

WTFstack, 13 bytes

1g{?(!)?/x<{;

WTFstack is my new programming language in which mathematical operations work on the entire stack at once.

Returns a stack of [1] if prime, and an empty stack if composite.

Interpreter

Explanation

1g            # is the input > 1?
  {           # if so, continue. else, print the stack and exit
   ?          # push the user input
    (         # -1
     !        # factorial
      )       # +1
       ?      # push the input again
        /     # divide all values on the stack by the input
         x    # push if the number is an integer or not (0 or 1)
          <   # swap the top two values on the stack
           {  # is the top of the stack truthy? if so, continue, else exit
            ; # discard the top of the stack
\$\endgroup\$
2
\$\begingroup\$

minigolf, 29 bytes

iT+:,:ns,:n*;s,_;*i=+0=s0=0=*

Attempt This Online!

Explanation

Generate a multiplication table of (input-1)x(input-1):

iT+                input - 1
:                  duplicate
,                  map in [1..i-1]:
  :                  duplicate i-1 so that it's preserved across iterations of map
  ns                 swap current iteration item underneath
  ,                  map in [1..i-1]:
    :                  dup curr. iter. item of outer loop (so that it's preserved)
    n*                 multiply by curr. iter. item of this map loop
  ;                  end map
  s,_                swap up & drop our preserved curr. map value
;                  end map

Aftermath of the multiplication table:
*                  flatten
i=                 Set by equality w/ input
+                  sum that
0=                 = 0? (i.e. no items in that table that equals input)
                   Note: at this point we have i-1 underneath our top value
s                  Swap i-1 upwards
0=0=               Set all >0 values to 1
*                  Multiply (i.e. if i-1 is zero, our prime checking output is 0.)
\$\endgroup\$
2
\$\begingroup\$

LiveCode, 128 bytes

on mouseUp
   ask ""
   put it div 2 into i
   repeat with j=2 to it-1
      put it mod j*i into i
   end repeat
   put i>0
end mouseUp

Put in a button and press the button. Asks for a number, puts true or false reporting primality into the message box. LiveCode does support stdin and stdout, but other answers here used this method so I am as well.

A function would make more sense to me, but that doesn't seem to be the accepted method here.

Explanation

Should be pretty clear:

Starts with 0 if the input is 1, or 1 or more if input > 1.

Then for every number from 2 to the input - 1, multiplies the running total by the input modulo the number. If any of the numbers evenly divide the number, the running total will change to (and remain for the rest of the loop) zero.

At the end, report whether the running total is greater than 0. If it is, the input is prime, if it has been zero-ified at any point, the input is not prime.

\$\endgroup\$
2
\$\begingroup\$

GAIA, 1 byte

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice answer \$\endgroup\$
    – The Thonnu
    Apr 18, 2023 at 19:03
2
\$\begingroup\$

Tabloid, 358 293 bytes

DISCOVER HOW TO x WITH a, b WHAT IF b BEATS 1 WHAT IF ((a DIVIDED BY b) MODULO 1) BEATS 0 SHOCKING DEVELOPMENT x OF a, b MINUS 1 LIES! SHOCKING DEVELOPMENT 0 LIES! SHOCKING DEVELOPMENT 1 EXPERTS CLAIM y TO BE LATEST NEWS ON "" YOU WON'T WANT TO MISS x OF y, y MINUS 1 PLEASE LIKE AND SUBSCRIBE

Input through a JavaScript prompt(), and output 1! if the input is prime and 0! otherwise (exclamation point due to language restrictions)

-65 bytes by using BEATS (greater than) instead of SMALLER THAN (less than) and IS ACTUALLY (equal to), inverting some if conditions on the way

Readable version

DISCOVER HOW TO x WITH a, b
    WHAT IF b BEATS 1
        WHAT IF ((a DIVIDED BY b) MODULO 1) BEATS 0
            SHOCKING DEVELOPMENT x OF a, b MINUS 1
        LIES!
            SHOCKING DEVELOPMENT 0
    LIES!
        SHOCKING DEVELOPMENT 1
EXPERTS CLAIM y TO BE LATEST NEWS ON ""
YOU WON'T WANT TO MISS x OF y, y MINUS 1
PLEASE LIKE AND SUBSCRIBE

Original (358 bytes)

DISCOVER HOW TO x WITH a, b RUMOR HAS IT WHAT IF b SMALLER THAN 2 SHOCKING DEVELOPMENT 1 LIES! RUMOR HAS IT WHAT IF ((a DIVIDED BY b) MODULO 1) IS ACTUALLY 0 SHOCKING DEVELOPMENT 0 LIES! SHOCKING DEVELOPMENT x OF a, b MINUS 1 END OF STORY END OF STORY EXPERTS CLAIM y TO BE LATEST NEWS ON "" YOU WON'T WANT TO MISS x OF y, y MINUS 1 PLEASE LIKE AND SUBSCRIBE

Readable version

DISCOVER HOW TO x WITH a, b RUMOR HAS IT
    WHAT IF b SMALLER THAN 2
        SHOCKING DEVELOPMENT 1
    LIES! RUMOR HAS IT
        WHAT IF ((a DIVIDED BY b) MODULO 1) IS ACTUALLY 0
            SHOCKING DEVELOPMENT 0
        LIES!
            SHOCKING DEVELOPMENT x OF a, b MINUS 1
        END OF STORY
    END OF STORY
EXPERTS CLAIM y TO BE LATEST NEWS ON ""
YOU WON'T WANT TO MISS x OF y, y MINUS 1
PLEASE LIKE AND SUBSCRIBE
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Apr 21, 2023 at 1:09
  • \$\begingroup\$ This language should be called “BREAKING NEWS” \$\endgroup\$ May 13, 2023 at 13:14
2
\$\begingroup\$

Thunno 2, 1 byte

P

Attenpt This Online!

\$\endgroup\$
1
2
\$\begingroup\$

Rockstar, 119 117 107 bytes

Outputs -0.5 for primes and 0 for composites.

listen to N
let D be N
let P be N-1
while P and D-2
let D be-1
let M be N/D
turn M up
let P be N/D-M

say P

Try it here (Code will need to be pasted in)

listen to N         :Read input string into variable N
let D be N          :Initialise D as N
let P be N-1        :Initialise P as N-1, which will be 0 (falsey) if N=1
while P and D-2     :While P and D-2 are not zero
let D be-1          :  Decrement D
let M be N/D        :  Assign N/D to variable M
turn M up           :  Round M up
let P be N/D-M      :  Reassign N/D-M to P
                    :End while loop
say P               :Output P
\$\endgroup\$
2
\$\begingroup\$

ForWhile, 24 bytes

9:`[_48=';+')1;[1+;;%)=#

Takes unary number less than 99 as input, prints 0x01 if prime and 0x00 otherwise

online Interpreter

Explanation

The first half of the code is just number-parsing (ForWhile does not have a built-in for that). The actual prime checking code is 1;[1+;;%)=.

9:`[        )            \ repeat up to 9^9 times
    _48=                 \ read one byte, check if it is equal to 48 (char code of 0)
        ';+              \ if yes, increment second value on stack
           ')            \ if no, break from loop
             1           \ push one
              ;[         \ repeat up to n (input number) times
                1+       \ increment value on stack
                  ;;%)   \ break loop if top stack value is divisor of input -> smallest divisor of number that is greater than 1
                      =  \ check if number is equal to its smallest divisor greater than 1
                       # \ print the result to standard output

binary input (36 bytes)

99[_48-:0<!:[.'2*+1]).1;[1+;;%)=48+#

prints 1 for prime and 0 for non-prime

decimal input (37 bytes)

99[_48-:0<!:[.'10*+1]).1;[1+;;%)=48+#

prints 1 for prime and 0 for non-prime

\$\endgroup\$
2
\$\begingroup\$

MaybeLater, 52 bytes

wheni is*ifi<n{if1>n%i o=0i++}n=read()o=1i=2write(o)

Ungolfed

when (i is *){
    if (i<n){
        if (1>n%i){
            o=0
        }
        i++
    }
}
n=read()
o=1
i=2
write(o)

Naïve approach.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Uiua, 13 bytes

=1/+=0◿⇡.⧻&sc

Try it online! (uses a 9 byte function instead)

Couldn't find a 8-byte primality test that works for 1 yet. Correctly gives 0 (false) for the input of 0.

=1/+=0◿⇡.    input: positive integer n
      ◿⇡.    n modulo each of 0..n-1
    =0        equals 0? gives 1 for zeros and 0 for others
  /+          sum (= number of divisors minus 1)
=1            equals 1?
\$\endgroup\$
1
  • \$\begingroup\$ Now this can be 12 bytes (different SBCS link), and 8 bytes for a function, with the prime factors builtin, and parse being one character: =1⧻°/×↥1⋕&sc \$\endgroup\$
    – noodle man
    Mar 30 at 15:45
2
\$\begingroup\$

GolfScript, 14 bytes

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

Try it online!

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

\$(n-1)!^2 \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\$
1
  • \$\begingroup\$ Oops sorry I made that mistake in the LaTeX \$\endgroup\$
    – noodle man
    Nov 8, 2023 at 1:49
1
\$\begingroup\$

Pyth, 8 bytes

&>Q1!tPQ

Alternative that doesn't support values less than 2:

!tPQ
\$\endgroup\$
0
1
\$\begingroup\$

Perl, 35 bytes

Uses regular expressions...

$_=1x$_;s/^(11+?)\g1+$//;print$_>1

That's 34 bytes of code, plus one byte for the -n switch needed to fetch a line from stdin. Outputs 1 if the number is prime, or nothing otherwise

\$\endgroup\$
1
5 6
7
8 9
13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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