222
\$\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 '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

327 Answers 327

1
\$\begingroup\$

17, 102

17 is a language I made a few days ago and am now trying out some challenges with.

A single ascii character is taken as input and 0 is returned for false, its lowest factor for true.

0{1 # 2 # 1 + : 2 @
% 0 == 2 * 2 # 1 # == 3 * + 0 @ }2{2 # $$ 0 @}5{0 $$ 0 @}777{0 0 @ I 1 @ 1 2 @}

Expanded:

0 {
  1 # 2 # 1 + : 2 @
  % 0 == 2 * 2 # 1 # == 3 * + 0 @
}
2 {
  2 # $$ 0 @
}
5 {
  0 $$ 0 @
}
777 {
  0 0 @ I 1 @ 1 2 @
}

17 starts at block 777 and runs blocks depending on value stored at 0.

Block 777: Set value 0 to 0, set value 1 to ascii code of input char, set value 2 to 1.

Block 0(first run after block 777): Increase 2 by 1, if 1 mod 2 == 0, go to block 2 unless value 1 is value 2, then goto block 5

Block 2: Load 2 and print, then exit

Block 5: Print 0 and exit

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

SmileBASIC, Forty Four 43 bytes

INPUT N
FOR D=1TO N
P=P+!(N MOD D)NEXT?P==2

Just checks if the number has exactly 2 divisors.

\$\endgroup\$
1
  • \$\begingroup\$ You could test if P<3 it's one byte shorter and it covers the 1 cornercase. \$\endgroup\$
    – steenbergh
    Feb 19 '17 at 9:01
1
\$\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\$
1
\$\begingroup\$

Forth (gforth), 73 61 57 bytes

: f { n } 0 n 1 > if 1 n 2 ?do n i mod 0> * loop then . ;

Try it online!

Stack-Only variant, 76 68 64 61 bytes

: f 0 over 1 > if 1+ over 2 ?do over i mod 0> * loop then . ;

Try it online!

Explanation

0 over             \ place a 0 on the stack then place a copy of the input on top
1 >                \ check if the top of the stack is greater than 1
if                 \ if true execute the if, otherwise skip it
   1+              \ add 1 to our tracking variable (so replace 0 with 1) 
   over 2          \ place n and 2 on the top of the stack, 
   ?do             \ loop from 2 to n, skip loop if n = 2
      over i mod   \ get the modulo of n and the loop index (so n % i) 
      0>           \ check if modulo is greater than 0 (not divisible)
      *            \ multiply bool (-1 or 0) by the top of the stack (shorter version of and)
   loop            \ end the loop 
then               \ end the if statement
.                  \ output the top of the stack
\$\endgroup\$
1
\$\begingroup\$

Pyt, 1 byte

Try it online!

Implicit input
ṗ   primality test
Implicit output
\$\endgroup\$
1
\$\begingroup\$

K, 23 bytes

x=&/(y*/:y:!x)?'x:0$0:`

yay for algorithmic improvements!

Explanation

No operator precedence kind of acts against us here, so we have to resort to paranthesis

x:0$0:`

reads the input and saves the result to the variable x

y:!x takes the list 0..(x-1) and saves it to the variable x

y*/:y applies * using /:, so every element in y is multiplied by y, creating a matrix

?'x searches every column of the matrix for x, returning the length if x is not found

x=&/ &/ takes the minimum of the list by folding it with the min operator, and then checks if it is equal to x. If not, there should exist a combination of two numbers smaller than x result in x, i.e it is not a prime

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

><>, 23 22 bytes

:1vn%$*:~<
@*>$1-:?!^:

Try it online!

Uses Wilson's theorem again, i.e. (n-1)!**2 %n returns 1 if n is prime, 0 if it is not. Takes input via the -v flag.

How it Works:

:1v Dupe the value and push a 1 as the total
  >$1-  Decrement the copy
      :?!^  If the copy is 0 go up to the first line
@*>       : Else Multiply the total by the copy and repeat the decrement
If we went up to the first line
        ~< Pop the excess 0
      *:   Square the total
  vn%$     Print the total modulo the original value and exit with an error
\$\endgroup\$
1
\$\begingroup\$

Forked, 57 54 bytes

$P11>p1+"Us'v
    |       |
1%& :-msU"p-:-
    |
  &%<

The dual-fork loop is really beautiful. Try it online! Alternate versions with identical bytecount:

Short explanation

This uses a trial division method, equivalent to this C code:

int isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}

Long, thorough explanation

Before we begin, let us define two values:

  • n: the inputted number, to be tested for primality
  • i: the loop counter for the trial division method

Here's the program's control flow:

---->-------v
    |       |
--- :-------:-
    |
  --<

The forks : compose one big loop. The rightmost fork exits the loop and prints 1 if n-i is zero, i.e. if n mod i is always positive, meaning n has no divisors other than 1 and itself.

The leftmost fork exits the loop and prints 0 if n mod i is zero, meaning n has a divisor other than 1 and itself.

The initial four bytes set up the stack. Let's say the input n is 11.

CODE  STACK    EXPLANATION
$     [n=11]   read integer input n
 P    []       pop n, stash in register
  1   [i=1]    push i (initially 1)
   1  [i=1, 1] push filler value for later popping

The code p1+"Us' between the redirects > and v pushes n-i.

CODE    STACK        EXPLANATION
p       [i=1]        pop top of stack (useless value or result of n%i)
 1+     [i=2]        add 1 to top of stack
   "    [i=2, 2]     duplicate top of stack
    U   [i=2, 2, 11] copy register onto stack
     s  [i=2, 11, 2] swap top two stack values
      ' [i=2, 9]     subtract top two stack values

Then the IP turns South and forks. If n-i is zero, it turns East and immediately wraps around to hit 1%& (push 1, print, exit), therefore returning a truthy value if If there are still values of i to check, the IP turns West, hitting the code that computes n mod i:

CODE  STACK        EXPLANATION
p     [i=2]        pop n-i
 "    [i=2, 2]     duplicate top of stack
  U   [i=2, 2, 11] copy register to stack
   s  [i=2, 11, 2] swap top two stack values
    m [i=2, 1]     compute n mod i

The IP is forked, turning South and returning 0 if n mod i is 0. Otherwise it turns North and immediately turns East, where i is incremented and the whole loop is done again.

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

Quarterstaff, 94

golfed 1!

10-?[-38a a a a a a a a a a>a10-?]a>b b[>b>d a>c c[1>c1d>d b d(.>e|>d1>e)c]e f>f1b]2-f(.|1)48!

Try it online!

How it works:

Quarterstaff has a register i call "value", and multiple other registers i call variables, which are referenced by name.

value starts as 0

10 add 10 to value

- multiply value by -1 (value now -10) (this is because it checks for the end of the integer by checking for newline, which has a charcode of 10)

? add an inputted characters charcode to the value (which will be 48 for "0", for example)


the first loop:

[ begin while loop. these work like brainf***'s while loops, but instead of a cell, it uses the value.

- multiply value by -1

38 add 38 to value

At this point, the program has 0 if the most recently input character was "0", -1 if it was "1", -2 if it was "2" etc.

a a a a a a a a a a this is a reference to the variable a 10 times. this means we add 10*a to the value. a starts of as zero

>a store this value in a. this means we have just done the following: a=10*a-int(inputted_char). a is always a negative number when using digits. when the loop is done, a will hold the inputted number *-1. this also happens to set the value to 0. assignment with > always sets the value to 0

10-? this is the same code as we executed before entering the loop. this means that we will input a new character, but if we got to the end of the number, we exit the loop.

] loop end. if the value is zero, we exit, otherwise returning to the start. this while loop executes until it has taken all the input into the variable a in negation (22 becomes -22)


a now holds the negative of the inputted number. why is it negative? well, because it's shorter. if we want to decrease the magnitude by 1, we only have to add 1, not use -, add 1, then use - again.

a>b the a adds a to the value (which is now exactly a because it was previously 0), and >b puts this value into b. in effect b=a, because the > sets the value back to 0. remember a and b are negative

b there is a space in between variable names, because otherwise they get parsed as one name. this just makes the value b, because the value was 0 before


another while loop

[ begin the loop

>b this puts the value inside b, and value now = 0. at the first execution of the loop, this has no effect apart from value = 0, but at subsequent executions, it will be adding 1 to b, which will decrease it in magnitude until reaches -1. we use b to represent divisors

>d value will always be 0 when executing this. this will set d to 0. this is necessary because it is set to other values later in the loop

a>c means c=a. remember a is negative, and so is c

c value += c (value =c because value was 0). c is negative,

[ nested while loop. tests for the value of c in first and subsequent executions because the value is set to c just before it checks. This loop performs modulus

1>c because we have c in the value, this means add 1 to c. remember c is never >0. this makes c a counter down to 0

1d>d add 1 to d (value was 0 before these commands). d is a non-negative integer

b d value += b + d. because b is negative and d is positive, this means that the value will now equal 0 iff abs(b)=abs(d).

(.>e|>d1>e) this is an if else expression/command thing. because it immediately follows the b d which is 0 iff the absolute values of b and d are equal, it means it will execute the else iff abs(b)=abs(d), otherwise the then part. so, the part that executes if the value isn't 0 is .>e. . sets the value to zero, >e puts that 0 in e. e is 0 by default. if b and d have equal magnitude though, >d1>e executes. this puts 0 in d (because the value was zero if we're executing this part) and then 1 in e. if this is the last execution of the loop, it means that we will exit the loop with 1 in e, which represents being divisible. otherwise we haven't finished the modulo process yet. if we executed the if not 0 part and this was the last execution, we exit with 0 in e, representing not divisible.

c value = c (because value was 0 before)

] close nested loop.

back to the not modulus part

e f>f value =0 prior to execution, and f += e (f = e + f)

1b this sets the value to b+1 (remember b is negative). this will get stored in b next execution of the loop, if there is one.

] close outer loop


tying up

2-f value (which equals 0) += f-2. prime numbers exited the modulus loop with e=1 precisely 2 times.

(.|1)48 if that isn't 0, set value to 0, but if it is 0, set to 1. then add 48, to the value, which is either 1 or 0.

! print character with the corresponding char code. thus, print "1" (49) for primes and "0" (48) for not primes

\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte by moving the >e out of the if expression: Try it online! \$\endgroup\$
    – wastl
    Apr 7 '19 at 12:04
1
\$\begingroup\$

Triangularity, 7 bytes

.).
IEp

Try it online!

Triangularity, 49 bytes

Much more interesting solution, without using built-ins for divisors / prime test. Outputs 1 if the input integer is a prime, 0 otherwise.

....)....
...If)...
..rF@)I..
.f/Df={L.
)2=......

Try it online!

How it works?

Removing the characters that make up for the triangular padding, here's what the program does:

)If)rF@)If/Df={L)2= || Full program. ToS = Top of the Stack
)I                  || Get the 0th input.
  f                 || And cast it to an integer.
   )r               || Create the integer range [0 ... ToS - 1).
     F        {     || Filter the elements of this list which satisfy this function:
      @)If/Df=      || Runs each (X) on a separate stack, keeps those that yield 1.
      @             || Increment X.
       )If/         || And divide the input by it.
           D        || Duplicate, push two copies of the ToS.
            f=      || Floor the second copy and compare it with the first one.
               L    || Length.
                2=  || Check if it equals 2. Implicitly output the result.
\$\endgroup\$
1
\$\begingroup\$

Whispers v2, 27 bytes

>>> ⊤ℙ
> Input
>> 1∘2

Try it online!

Whispers v1, 27 bytes

> Input
>> 1’
>> Output 2

Try it online!

Uses the builtin prime tester. Alternatively, instead of using a builtin, the following code uses Wilson's Theorem and weighs in at 54 bytes

> Input
> 1
> 2
>> 1-2
>> 4!
>> 5*3
>> 6%1
>> Output 7

Try it online!

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

Befunge 93, 33 bytes

&10p1 >1+:10g\`v
1.@.0_^#!%\g01:_

Also works by trial division, as the other befunge post, but is substantially shorter.

Interpreter here.

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

Forth, 82 65 bytes

: f 1 ?do i' i mod 0= + loop 0= ;
1 tib dup 9 accept evaluate f .

Ungolfed:

: f                        \ def f(counter, n):
  1 ?do                    \     for i in range(1, n):
    i' i mod 0= +          \         counter -= n % i == 0  # In Forth True == -1
  loop
  0=                       \     return counter == 0
;
1                          \ counter = 1
tib dup 9 accept evaluate  \ n = int(input()) # Forth version inputs 9 digits at most
f .                        \ print(f(counter, n))

It has at least one downside though: Forth echoes back what it accepted, because it is strongly terminal and/or REPL oriented, so feeding it 7 yields 7 -1

Run it!

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

Befunge-93, 28 bytes

&:0\1\1>-#1:__\#0:#*_$:*\%.@

Try it online!

Uses Wilson theorem, i.e. that ((n-1)!^2)%n returns 1 if n is prime else 0.

How It Works:

&:0\1\ Get input n and dupe it, putting a 0 and a 1 in-between
      1>-#1:_ Decrement and dupe until the number is empty
             _\#0:#*_$ Multiply until you reach the zero, yielding (n-1)!
                      :* Square it
                        \% Mod this value by the original value
                          .@ Print the mod and terminate 
\$\endgroup\$
0
1
\$\begingroup\$

Python 3, 42 55 bytes

n=int(input());print(sum(n%m<1 for m in range(1,n))==1)

Try it online!

The n%m<1 comparison is sufficient to check that n is a multiple of m. I start the range at 1 to correctly handle the case n == 1.

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

Go, 231 bytes

package main
import."fmt"
type c chan int
func main(){a,k:=0,make(c);Scan(&a);go func(d c){for i:=2;;i++{d<-i}}(k)
for{p:=<-k;if a==p||a<p{Print(a==p);break};j:=make(c)
go func(i,o c,p int){for{j:=<-i;if j%p!=0{o<-j}}}(k,j,p);k=j}}

This solution contains a sieve that generates primes, when the primes exceed the candidate, or there is a match it outputs true for primes and false for non-primes.

The main code is blatantly stolen from this playground example.

Since it is rather silly I probably wont be golfing this solution any further

Try it online!

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

Python 2, 51 bytes

p=input()
print all(p%i for i in range(2,p-1))==1<p

Try it online!

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

Procedural Footnote Language, 41 bytes

[1]
[PFL1.0]
[1] [PRIME:[INPUT]]
[PFLEND]

Explanation

This program is fairly straight-forward: The body of the document (above the [PFL1.0] tag) is the result/output, and is equivalent to the evaluated contents of footnote [1]. Footnote [1] evaluates to the result of the [PRIME] function on input from STDIN.

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

Reality, 1 byte

P

This takes input via stdinput and return true if it is a prime and false other wise


Alternate :

If taking input is not allowed then

p number

space is not required (replace number with your number)


Note : Reality is an under-development language and was created after this challenge

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

Racket, 67 42 bytes

(require math/number-theory)(prime?(read))

When run in DrRacket, this will prompt the user for an integer and return #f (false) if the number is not a prime and #t (true) if the number is a prime.

Previous (and much more complicated) version:

((λ(l)(or(= l 1)(ormap(λ(x)(=(modulo l x)0))(range 2 l))))(read))
\$\endgroup\$
1
\$\begingroup\$

Z80Golf, 30 bytes

00000000: 040c 0934 0c28 0d0a b720 f960 6909 38f4  ...4.(... .`i.8.
00000010: 2534 18f9 24cd 0380 6f7e cd00 8076       %4..$...o~...v

Try it online!

Takes a single-byte input. Outputs a zero byte for prime byte values, and some non-zero byte for composite values. (This value is actually the number of distinct prime divisors!)

Disassembly:

  inc b
  inc c
  add hl, bc  ; HL = BC = $0101.
              ; We use $0100~$ffff as a prime sieve array.
  inc (hl)    ; Mark 1 as composite.

next:
  inc c       ; Loop for C from 2 to 255.
  jr z, done
  ld a, (bc)
  or a
  jr nz, next ; If *BC is marked as composite, skip.

  ; sieve
  ld h, b     ; Mark *(BC), *(2*BC-256), *(3*BC-512) ... as composite.
              ; (So for BC = $0103, this is $0103 $0106 $0109 ...)
  ld l, c
clear:
  add hl, bc
  jr c, next  ; Run until HL overflows! This is more work than necessary, but shorter.
  dec h
  inc (hl)
  jr clear

done:          ; Now H = 0.
  inc h        ; Now H = 1.
  call $8003
  ld l, a      ; Now HL = $0100 + input.
  ld a, (hl)
  call $8000   ; putchar(*HL)
  halt
\$\endgroup\$
1
\$\begingroup\$

Elixir, 122 bytes

o=fn f,p,1->1
f,1,c->0
f,p,c->case rem(p,c)do
0->0
_->f.(f,p,c-1)end end
{i,_}=Integer.parse IO.gets""
IO.puts o.(o,i,i-1)

Try it online!

Can definitely be golfed. Outputs 1 for prime and 0 for composite

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This breaks on 1. Otherwise, replacing True by 0<1 and False by 1<0 shortens it a bit. \$\endgroup\$ Jun 21 '18 at 18:03
  • \$\begingroup\$ 1 has been fixed, and I just switched True / False out for the easier int equivalents \$\endgroup\$
    – Dave
    Jun 21 '18 at 18:49
1
\$\begingroup\$

Scala, 40 bytes

def f(n:Int)= !(2 to n-1).exists(n%_==0)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Unfortunately, this challenge doesn't allow functions. \$\endgroup\$
    – Dennis
    Jun 25 '18 at 13:49
1
\$\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\$
1
\$\begingroup\$

Foam, 9 bytes

;# #.% .#

Foam isn't on TIO yet, but it should be coming soon!

Outputs 1 for prime and 0 for nonprime.

Foam has a prime checking builtin.

;#   <- read number
#.%  <- is number prime?
.#   <- output number
\$\endgroup\$
1
\$\begingroup\$

Flobnar, 25 bytes

%\ @
:&|\<
-:1>
1*<
>>  *

Try it online!

Outputs 1 for prime, 0 for composite. Uses the -d flag to get numerical input. Be aware that the time it takes for each number doubles, where an input of 18 will take ~6 seconds, and 19 takes ~12 seconds. This is because the algorithm (based on Wilson's theorum) looks somewhat like:

def f(n):
    if n == 0:
        return 1
    else:
        return n*f(n-1)*f(n-1)
print f(input)*f(input)%input

So basically the function takes 2n+1 steps, doubling the time it takes for each step. If you want to test the code itself, you can use this (+2 bytes) which is merely 2n steps. It basically removes the surplus extra call of f(n-1) in the return of the function.

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

Elixir, 75 72 bytes

n=String.to_integer IO.gets""
IO.puts Enum.all?2..n-1,&rem(n,&1)>0||2==n

Try it online!

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

Pixiedust, 59 bytes

Takes input in the ++ register, and leaves output in the .. register.

*.+*.*+.
+.
.++*++
+*..
**+..+++*
*+++*+*.*+
+**
+..
.*...*

Explanation

* . +* .*+.       Set the +* register to 2 - this is the factor being checked
+.                Define a label whose name is the empty string
. + +* ++         Test whether +* has reached ++ yet
+* . .            If it has, go to the "." label
* *+ .. ++ +*     Set the branch register to ++ modulo +*
* ++ +* +* .*+    Increment the factor
+* *              If the branch register is not 0 (meaning it's not a factor) restart the loop
+. .              The "." label
. * .. .*         Invert the .. register
\$\endgroup\$
1
\$\begingroup\$

Cardinal, 24 21 bytes

Thanks to @Jo King for golfing off 3 bytes

Code:

%
:
=>-!.
v#~M!@
-
R^

Try it online!

Explanation:

%      //Start program
:      //Read input
=      //Copy input to inactive value
v#     //Loop around and pass copy of pointer up and to right after each loop
-      //Decrement active value by 1
R^     //End program if input=1

*>-!.     //If active value =1 print 0 (occurs just before line below ends program)
*#~M!@    //If inactive value divisible by active value end program
**
**
\$\endgroup\$
0
1
\$\begingroup\$

F#, 79 84 bytes

Fixed as per Dennis's suggestion.

stdin.ReadLine()|>int|>fun n->not(Seq.exists(fun i->n%i=0)[2..n-1]||n=1)|>printf"%b"

Now works for input = 1. Can be run same as before.


Original submission:

I didn't see an F# answer so...

stdin.ReadLine()|>int|>fun n->not(Seq.exists(fun i->n%i=0)[2..n-1])|>printf"%b"

Can be compiled with fsc or run directly in fsi. Takes a newline-terminated string from stdin and spits out a bool to stdout when run.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Unfortunately, that doesn't work for input 1. Try it online! \$\endgroup\$
    – Dennis
    Dec 27 '18 at 20:59
  • 1
    \$\begingroup\$ Remember, lambdas are allowed, so... 44? \$\endgroup\$
    – ASCII-only
    Jan 31 '19 at 8:38

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.