227
\$\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

339 Answers 339

1 2
3
4 5
12
5
\$\begingroup\$

JavaScript, 53 52 40 bytes

alert(/^(?!(..+)\1+$)../.test(prompt()))

Just realized the question allows unary input, which cuts the size down to 40 bytes. Previous answer of 52 bytes is below (ES6):

alert(/^(?!(..+)\1+$)../.test('1'.repeat(prompt())))

Uses that cool unary regex to determine primality.

I actually originally wrote this without seeing the Retina answer, and using a different regex, as seen here: !/^1?$|^(11+?)\1+$/. I moved to the Retina one since saves a character by avoiding the need for negation.

\$\endgroup\$
5
  • \$\begingroup\$ I think this (and the other JavaScript answers) should use alert or console.log. Otherwise it's assuming a REPL environment (like a browser console) whereas the challenge explicitly asks for a full program. That said, your own regex wouldn't have been longer than mine, because you only need ^1$ (zero is not a valid input). \$\endgroup\$ Sep 14, 2015 at 10:11
  • \$\begingroup\$ @MartinBüttner I agree on it needing a print statement, but when doing so puts an otherwise shorter answer behind longer ones that don't follow that rule... I chose instead to mention why I didn't. If the other answers conform, I'll gladly adjust mine as well. Thanks! =) Good point, hadn't noticed the 0 part. It would be the same length in that case. \$\endgroup\$
    – Mwr247
    Sep 14, 2015 at 15:05
  • \$\begingroup\$ Well if the others think the same no one will change it. ;) You could just leave a comment (if I haven't done so already) and hope for Dennis to invalidate the answer (to remove it from the leaderboard) if the author doesn't fix it within a couple of days. \$\endgroup\$ Sep 14, 2015 at 15:07
  • \$\begingroup\$ @MartinBüttner I left a comment on one of them a few days back, but fair enough haha. I suppose I could just edit them all for it as well and update the counts. \$\endgroup\$
    – Mwr247
    Sep 14, 2015 at 15:21
  • 1
    \$\begingroup\$ You can actually shorten the original regex by one character by making it !/^.?$|^(..+)\1+$/ \$\endgroup\$
    – Aplet123
    Mar 27, 2016 at 13:05
5
\$\begingroup\$

Turing Machine Code, 2043 bytes

As usual, I'm using the rule table syntax defined here. Requires unary input.

0 * * r 0
0 _ _ l c
a _ 1 r b
a 0 1 r b
a 1 0 l a
b * * r b
b _ _ r 0
c 1 _ l d
c _ _ * y
d * * l d
d _ _ l a
y _ _ l y
y * * l z
z * * l z
z _ _ r X
X 1 1 r Y
Y _ _ * f
Y * * l Z
X * * l 1
Z * * l 1
1 * a r 2
2 _ b l 3
2 * * r 2
3 a a r 4
3 x x r 4
3 y y r 4
3 * * l 3
4 0 x r 5
4 1 y r 5y
4 b b l 9
9 x 0 l 9
9 y 1 l 9
9 a a r A
5 b b r 6
5 * * r 5
5y b b r 6y
5y * * r 5y
6 _ 0 l 3
6 * * r 6
6y _ 1 l 3
6y * * r 6y
A _ c l 11
A * * r A
11 b b r 12
11 x x r 12
11 y y r 12
11 * * l 11
12 0 x r 13x
12 1 y r 13y
12 c c l B
13x _ 0 l 11
13x * * r 13x
13y _ 1 l 11
13y * * r 13y
B x 0 l B
B y 1 l B
B b b r 21
21 _ d l 22
21 * * r 21
22 1 0 r 23
22 0 1 l 22
23 d d r E
23 * * r 23
E c c r 51
E x x r 51
E y y r 51
E * * l E
51 0 x r Kx
51 1 y r Ky
51 d d l 53
Kx _ 0 l E
Kx * * r Kx
Ky _ 1 l E
Ky * * r Ky
53 x 0 l 53
53 y 1 l 53
53 c c r F
F _ _ l 61
F * * r F
61 1 0 l 62
61 0 1 l 61
61 d d r 70
62 c c l 63
62 * * l 62
63 1 0 r F
63 0 1 l 63
63 b b r 80
70 _ _ l 71
70 * * r 70
71 d d l 72
71 * _ l 71
72 c c * E
72 * * l 72
80 _ _ l Za
80 * * r 80
Za 0 1 r Zb
Za 1 0 l Za
Za d d r Zk
Zb _ _ l Zc
Zb * * r Zb
Zc x x l Zc
Zc y y l Zc
Zc d d r A0
Zc 0 x l $
Zc 1 y l $y
$ d d l Ze
$ * * l $
$y d d l @
$y * * l $y
Ze 0 x r Zf
Ze 1 1 r Zk
Ze x x l Ze
Ze y y l Ze
@ 1 y r Zf
@ 0 0 r Zk
@ x x l @
@ y y l @
Zf _ _ l Zc
Zf * * r Zf
Zk _ _ l Zm
Zk * * r Zk
Zm d d l Zn
Zm * _ l Zm
Zn x 0 l Zn
Zn y 1 l Zn
Zn 0 0 r Zo
Zn 1 1 r Zo
Zo d d l 82
Zo * * r Zo
82 1 0 l 83
82 0 1 l 82
83 c c l 84
83 * * l 83
84 b b l 85
84 * _ l 84
85 a a r 86
85 x x r 86
85 y y r 86
85 * * l 85
86 0 x r &x
86 1 y r &y
86 b b l 90
&x b b r Lx
&x * * r &x
&y b b r Ly
&y * * r &y
Lx _ 0 l 85
Lx * * r Lx
Ly _ 1 l 85
Ly * * r Ly
90 x 0 l 90
90 y 1 l 90
90 a a r 91
91 c c r 51
91 * * r 91
A0 _ _ l A1
A0 * * r A0
A1 d d l A2
A1 * _ l A1
A2 x 0 l A2
A2 y 1 l A2
A2 c c r A3
A3 d d l B0
A3 * * r A3
B0 1 0 r B1
B0 0 1 l B0
B1 d d l B2
B1 * * r B1
B2 1 0 r f
B2 0 1 l B2
B2 c c r t
t * * r t
t _ _ l t2
t2 * _ l t2
t2 _ 1 * halt
f * * r f
f _ _ l f2
f2 * _ l f2
f2 _ 0 * halt
\$\endgroup\$
2
  • \$\begingroup\$ Nice! I imagine the state names could be golfed a bit more, though... \$\endgroup\$
    – DLosc
    Oct 27, 2015 at 23:23
  • \$\begingroup\$ I'm still surprised this isn't actually the longest answer. (The Mornington Crescent answer is longer, which I guess makes some sense.) \$\endgroup\$ Oct 29, 2015 at 1:29
5
\$\begingroup\$

Seriously 0.1, 2 bytes

,p

, reads a value from STDIN. p pops from the stack and pushes 1 if it is prime, else 0. At EOF, all values on the stack are popped and printed.

Currently, Seriously uses trial division to test primality, so for large inputs it may take a while. In a future version, I'll probably use ECPP or Miller-Rabin.

Try it online

\$\endgroup\$
1
  • 9
    \$\begingroup\$ Seriously. Seriously? \$\endgroup\$
    – Dennis
    Nov 9, 2015 at 3:03
5
\$\begingroup\$

05AB1E, 1 byte

Code:

p

Explantation:

p     # Implicit input, check whether it is prime or not.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ @Okx Actually, that isn't necessary to state in this challenge, because this challenge explicitly states that newer languages are welcome here. \$\endgroup\$
    – Adnan
    Jan 26, 2017 at 17:34
5
\$\begingroup\$

Sesos, 63 62 58 bytes

0000000: 1651bc afcddc c4fbbe 3e739e c0f1be 3673c3 eecdf8  .Q.......>s....6s....
0000015: cc75b8 677ce2 b57bc6 78cddc 796de3 7eed33 b7c113  .u.g|..{.x..ym.~.3...
000002a: ef9da3 a0fbbc 77ece7 3adc2b 354e33 f9             ......w..:.+5N3.

The ASM code that I wrote, along with some comments can be run on Try it online:

set numin
set numout
get
sub 1
jmp ; if
    add 1
    jmp ; copy
        fwd 1
        add 1
        fwd 1
        add 1
        rwd 2
        sub 1
    jnz ; end copy
    fwd 2
    sub 1
    jmp ; triplicate loop
        fwd 1
        add 1
        fwd 1
        add 1
        fwd 1
        add 1
        rwd 3
        sub 1
    jnz ; end triplicate
    fwd 1
    sub 1
    fwd 1
    sub 1
    jmp ; factorial loop
        jmp ; multiply loop
            fwd 1
            jmp ; forward add step of multiply loop
                fwd 1
                add 1
                fwd 1
                add 1
                rwd 2
                sub 1
            jnz ; end forward add step of multiply loop
            fwd 2
            jmp ; after add step, reset tape
                rwd 2
                add 1
                fwd 2
                sub 1
            jnz ; end reset tape
            rwd 3
            sub 1
        jnz ; end multiply
        fwd 1
        get ; sets to 0
        fwd 1
        jmp ; transfer intermediate value
            rwd 1
            add 1
            fwd 1
            sub 1
        jnz ; end transfer
        rwd 3
        sub 1
        jmp ; reset loop counter
            fwd 1
            add 1
            rwd 2
            add 1
            fwd 1
            sub 1
        jnz ; end reset
        rwd 1
        jmp ; fix memory location of header
            fwd 1
            add 1
            rwd 1
            sub 1
        jnz ; end fix
        fwd 2
    jnz ; end factorial
    fwd 1
    add 1
    rwd 4
    jmp ; transfer input for mod
        fwd 5
        add 1
        rwd 5
        sub 1
    jnz ; end transfer
    fwd 4
    jmp ; mod
        sub 1
        fwd 1
        sub 1
        jmp ; a
        fwd 1
        add 1
        fwd 2
        jnz ; a
        fwd 1
        jmp ; b
        add 1
        jmp ; c
        sub 1
        rwd 1
        add 1
        fwd 1
        jnz ; b
        fwd 1
        add 1
        fwd 2
        jnz ; c
        rwd 5
    jnz ; end mod
    fwd 1
    get ; sets to zero
    fwd 1
    jmp ; invert a
        rwd 1
        add 1
        fwd 1
        get ; blanks
    jnz ; end invert a
    add 1
    rwd 1
    jmp ; invert b
        fwd 1
        sub 1
        rwd 1
        sub 1
    jnz ; end invert b
jnz ; end if
fwd 1
put

I've never written any BF variant code before, outside of very simple tasks, so I'm sure some of this is not optimal. The divmod algorithm and the logical negation algorithm used were taken from the esolangs algorithms page.

This implements Wilson's theorem. We compute (n-1)! + 1 and then logically negate that value mod n. The factorial code hangs on input 1, so the code is wrapped in an if loop that totally skips running in that case. At the very end, the tape head is manipulated to be over where we would have left the mod value if we ran the code, or over some random zero if the input was 1. I'll add a more thorough explanation when I am done golfing.

\$\endgroup\$
5
\$\begingroup\$

brainfuck, 62 bytes

,-[+[<+>>+<-]>[-<[>+<-]<[>+>->+<[>]>[<+>-]<<[<]>-]>>>]<-[<]]<.

This is a port of my Sesos answer. Input and output are character-based. For a character whose code point is prime, the program will print the character itself; otherwise, it will print NUL.

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Mini-Flak, 202 bytes

Mini-Flak is a turing complete subset of the Brain-Flak language. (It is currently the smallest know turing complete subset of Brain-Flak) It works exactly like Brain-Flak except the <> and [] nilads and the <...> monad are forbidden.

(({})){(({}[()])(((({}({}))[({}[{}])]([()]()))({({}[()((({}()[({})])){{}((({}({})))[{}])}{})]{})}({}{}({})[{}]))[{}]))[{}])}{}{}({}({})[{}()()()]){({}[()((({})){(({}{}(({})))[{}])}{}({}({})[{}]))]{})}{}

Try it online

Explanation

The reason <...> is banned in mini-flak is that it is equivalent to (...)[{}]. So to start this explanation I am going to use this translation in reverse to create an equivalent Brain-Flak program for increased readability for anyone who is already familiar with Brain-Flak.

(({}))
{
 (({}[()])<
  ((({}({}))[({}[{}])]([()]()))<{({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)>)
 >)
}{}{}({}<{}>[()()()])
{({}[()((({})){(<{}{}(({}))>)}{}({}<{}>))]{})}{}

This program has two main parts, performs the modulus on the input for every number smaller than than the input and leaves them in a stack.

(({}))
{
 (({}[()])<
  ((({}({}))[({}[{}])]([()]()))<{({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)>)
 >)
}{}{}

This uses a old version of modulo I wrote ({}(<()>)){({}[()((({}()[({})])){{}(<({}({}))>)}{})]{})}({}{}<{}>)

The second part ands together all of the results of the last part

({}<{}>[()()()])
{({}[()((({})){(<{}{}(({}))>)}{}({}<{}>))]{})}{}

If any one of the results is zero the result of all the ands will be zero otherwise it will be truthy and the number will be prime.

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

Japt, 1 byte

j

Built-ins are useful for long challenges, but aren't fun in mini-challenges like this. So here's an alternate version without the built-in; still pretty short:

Japt, 8 bytes

o2 e@U%X

Try it online!

How it works

      // Implicit: U = input number. Implicitly place a U at the beginning of the program
o2    // Create an array of all integers from 2 to U. (2o6 = [2,3,4,5])
      // For numbers below 2, this returns n to 2. (2o-3 = [-3,-2,-1,0,1])
e@    // Check if every number X in this range returns truthily to:
U%X   //   the remainder of U divided by X.
      //   In other words, if any of these remainders are 0, return false.
      //   For numbers less than 2, the range contains 1,
      //   so this always returns false for these cases.
      // Implicit: output last expression
\$\endgroup\$
5
\$\begingroup\$

J, 19 17 Bytes

echo(p:[:".1!:1)1

Explanation:

echo(p:[:".1!:1)1  | Full program.
echo(          )   | Hook: (f g) y is evaluated as y f (g y)
       [:".1!:1    | Right verb in the hook
           1!:1    | With argument 1, reads a line of input
         ".        | Evaluate, converts valid string to int
       [:          | Cap, treat these two verbs as one
     p:            | With a left argument of 1, as supplied by the hook, tests primality of its right argument
echo               | Print
\$\endgroup\$
1
  • \$\begingroup\$ I might be missing something, but 1 p: is shorter than 1=#q: (built-in primality testing isn't disallowed as far as I can tell). \$\endgroup\$
    – cole
    Jan 16, 2018 at 22:25
5
\$\begingroup\$

Pip, 10 8 bytes

1=0Na%,a

Try it online! (testing numbers 0 through 29)

Takes the number as a command-line argument (a) and uses the definition of prime number (has only 1 and itself for factors):

      ,a  Range of numbers from 0 through a-1
    a%    Take a mod each number in range; this is 0 if the number is a divisor,
            nil if the number is 0, and nonzero otherwise
  0N      Count the number of zeros in that list
1=        True (1) if the count is exactly 1, false (0) otherwise
          Print (implicit)
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 28 bytes

f=(n,i=n)=>n%--i?f(n,i):i==1

Try it online!

Old, 33 bytes:

f=(n,t=2)=>t<n?n%t?f(n,t+1):0:n>1
\$\endgroup\$
0
4
\$\begingroup\$

Lua, 56 bytes

n=io.read"*n"p=1
for i=1,n-1 do
p=p*i*i%n
end
print(p%n)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ p=1 for i=1,...-1 do p=p*i*i%...end print(p%...>0) does the job in 50 bytes, by switching the input to command-line argument, and printing true and false instead of 0 and 1. Also, Be aware that 0 evaluates to true and is therefore a truthy value in lua, so your current answer technically always input true. \$\endgroup\$
    – Katenkyo
    Apr 11, 2016 at 12:31
4
\$\begingroup\$

APL, 21

{∧/0≠⍵|⍨(⍵≠1)+⍳|⍵-2}⎕

Trial division. It would incorrectly state that ¯1 (minus one) is a prime but it's outside the domain so it's all right.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! Because APL has its own legacy code page, we usually count APL as one byte per character here. \$\endgroup\$
    – Dennis
    Sep 13, 2015 at 5:28
4
\$\begingroup\$

XSLT 3.0, 178 bytes

<transform xmlns="http://www.w3.org/1999/XSL/Transform" xmlns:x="x" version="3.0"><template match="d" expand-text="yes">{.>1 and empty((2 to .-1)[current() mod .=0])}</template></transform>

Posted as an alternative, because it uses a significantly different approach than my previous post. In expanded form, with the usual prefixes:

<xsl:stylesheet
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    version="3.0">

    <xsl:template match="d" expand-text="yes">{
        . > 1 and empty((2 to . - 1)[current() mod . = 0])
    }</xsl:template>

</xsl:stylesheet>

This method also uses a variant of my XPath solution for primality testing, which is explained there.

Since the default in XSLT is to process all nodes in the input document, this is what happens here as well. For input, you need to hand it a proper, validated XML document with a root element <d>:

<d>101</d>

The result will be output as true or false. It utilizes an XSLT 3.0 feature that allows inline XPath expressions in text nodes. It uses the XSLT 2.0 feature of schema-aware processing. If you don't have such a processor, add the XSD namespace and replace the XPath expression with the following:

. > 1 and empty((2 to . cast as xs:integer - 1)[current() mod . = 0])

For a non schema-aware processor, it would make the code at least 62 bytes larger.

\$\endgroup\$
4
\$\begingroup\$

Prelude, 125 80 75 59 55 52 bytes

1-^ (1-v#0)#)#1+1-))(0
?(1-
 ^  ^1-( 0#v+^-( 0##10)!

For convenience, I'd suggest using my modified interpreter which reads input and prints output as decimal integers. (Otherwise, I/O would be via a single character's ASCII value.)

It turns out that simple trial division is shorter in Prelude than the squared-factorial approach, because multiplication is fairly expensive. I also found new shortest solutions to compute a modulo and a logical NOT while working on this.

Explanation

The basic algorithm is trial division: check how many numbers in [0,n-1] divide the input n via modulo (where my modulo implementation happens to return i for i%0, such that 0 is never a divisor, but doesn't crash the program either). If there was exactly one divisor (1) we have a have a prime, otherwise we don't. So the print the logical NOT of the number of divisors minus 1.

Let's go through the voices:

  1. This voice counts the number of divisors, and is also used for the outer loop of the modulo.
  2. This voice merely reads the input and then performs the main loop from n-1 down to 0.
  3. This voice does the main work of the modulo computation and computes and prints the logical NOT of the number of divisors.

Finally, we can look at some parts of the code in detail:

  ^ (1-v#0)#)#

    ^1-( 0#v+^-

This is the modulo. The top voice starts by copying n from the bottom voice and the bottom voice copies the current (potential) divisor from the middle voice. The idea is to decrement both values until n is zero, but whenever the divisor hits zero we restore it.

The restoring works like this: we always copy the divisor into the top voice with v. But while the bottom voice is non-zero, we immediately discard it and push a zero instead. This value is then shifted to the bottom voice and added to the current value there.

Finally, the modulo is how far we are into the current cycle, so we subtract the divisor from the result with ^- (which is actually minus the modulo, but we only want to know if it's zero or not, so this doesn't matter).

1-     mod    1+1-))
?(1-
 ^     mod     ( 0##

This is then the main loop. The top voice is initialised to -1 (to account for the fact that 1 is always a divisor), the middle voice reads the input and the bottom voice receives a copy. Before computing the modulo, the middle voice decrements the current divisor.

After the modulo is computed we increment the counter, but decrement it again if the modulo was non-zero.

Finally, we compute the logical not, by pushing a 1 onto the bottom voice but putting a 0 on top if the divisor counter was non-zero, before printing it:

                    (0

                    10)!
\$\endgroup\$
4
\$\begingroup\$

Fortran 2003, 51 bytes

Here is a solution using Fortran's array capabilities. Fortran 2003 is really only required for the shorter array constructor [ ] instead of the old (/ /).

read*,n
print*,count([(mod(n,i),i=1,n)]==0)==2
end
\$\endgroup\$
4
\$\begingroup\$

MATLAB, 24 31 36 bytes

  1. Changed to 31 bytes in order to add in the case of n=1
  2. Changed to 36 bytes to make a full program and to incorporate the 1 byte saving from a suggestion by pawel.boczarski (thanks!)

Since isprime is already taken, an alternative is to take a look at the greatest common divisor of the number in question n with every number from 2 up to n-1. If the GCD of every number in the output is 1, then the number is prime. However, we need to check for the case of n=1, and so by definition, this shouldn't be prime:

n=input('');n-1&all(gcd(n,2:n-1)==1)

This creates an anonymous function that checks if the number is prime and assigns it to the variable f. To call the function, simply do f(n) once it's created with n being a positive integer.

Sample Runs

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
1

ans =

     0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
2

ans =

     1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
3

ans =

     1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
4

ans =

     0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
5

ans =

     1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
7

ans =

     1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
10

ans =

     0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
13

ans =

     1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
15

ans =

     0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
20

ans =

     0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
23

ans =

     1

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
33

ans =

     0

>> n=input('');n-1&all(gcd(n,2:n-1)==1)
37

ans =

     1
\$\endgroup\$
4
  • \$\begingroup\$ Two tips: you can omit f= - the anonymous handle is a perfect solution (2 bytes saved), moreover in case of positive integer n~=1 can be replaced by n-1 (1 byte saved) - I tried in Octave and it worked, should work in Matlab as well. \$\endgroup\$ Sep 12, 2015 at 8:59
  • \$\begingroup\$ @pawel.boczarski thanks! I had the anonymous handle but thought it conflicted with the definition of a "full program". Could you perhaps clarify on what this means? \$\endgroup\$
    – rayryeng
    Sep 12, 2015 at 9:02
  • \$\begingroup\$ Uhm, you're right. This is clarified in the task spec that a full program is demanded, I didn't notice that. But the tip with n-1 instead of n~=1 will still work. \$\endgroup\$ Sep 12, 2015 at 9:10
  • \$\begingroup\$ @pawel.boczarski that'll shave one byte off. Thanks! Also thanks for the clarification \$\endgroup\$
    – rayryeng
    Sep 12, 2015 at 9:19
4
\$\begingroup\$

HPR, 1217 bytes

393 bytes with macros

HPR is an unusable language I created for a challenge here. It has only five commands, and it's not Turing complete; I was actually surprised that a primality test could be programmed in HPR. This answer stretches the conditions of input formats a bit, since the input has to be provided as a descending list of integers from n to 1, encoded in unary and separated by 0s. There has to be a trailing 0, so the number 4 would be encoded as 11110111011010. The program prints 1 if the input is a prime, and an empty line if not. Here's the source code:

$!($)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(--))(*#(!(-)(#(-)()))())))!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))())!(#(*#(!(-)(#(-)()))())(!(-)(#(-)()))-!(-)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(#(#(!($)(#(*)()#(!(-)(#(-)()))())!(-)(#(-)())*)()#(!(-)(#(-)()))())(!(-)(#(-)())))(-#(!(-)(#(-)()))())#(!(-)(#(-)()))())))(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())($!($)(!(!(-)(#(-)())#(!(-)(#(-)()))())(!(!(-)(#(-)())#(!(-)(#(-)()))())(#(*)()#(!(-)(#(-)()))()))!(-)(#(-)())#(*)(!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))#(!(-)(#(-)()))())!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(*)(!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))#(!(-)(#(-)()))())))-#(!(-)(#(-)()))())-#(!(-)(#(-)()))())!(!(-)(#(-)())#(!(-)(#(-)()))())(!(-)(#(-)())#(!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(--))(*#(!(-)(#(-)()))()))!(-)(#(-)())*#(!(-)(#(-)()))()!(-)(-)

This was not written by hand, but generated from this 393-byte source by TheNumberOne's macro system:

def d 0 !(-)(#(-)())
def l 0 #(<d>)()
def f 1 !({0})(#({0})())
def n 1 !(<d><l>)({0})
def o 2 <n>(<n>({0})){1}
def m 0 <d><f>(-#(!(*)(#(*)())<l>)(<d>))#(-)(<l>)
def x 0 <d>#(*)(<m>)<l>
def z 1 <d>*<l>!(-)(-{0})
def i 0 <d>#(<z>(-))(*<l>)
$!($)(<o>(<i>,<m>!(#(*<l>)(<d>)-!(-)(<n>(!(#(#(!($)(#(*)()<l>)<d>*)()<l>)(<d>))(-<l>)<l>)))(<o>($!($)(<o>(#(*)()<l>,<x>))<n>(<x>),-<l>))-<l>))<n>(<i>)<z>()

Explanation

An HPR program is run in an environment, which is a set containing nonnegative integers and lists. Initially, it contains the input list, and the five commands modify the environment in different ways. However, it's not possible to obtain larger numbers than the maximum of the list, and it's not possible to add new elements to lists. Thus, trial division is the way to go. I'm not going to completely explain the code in this post, but an expanded version with comments can be found here.

\$\endgroup\$
4
\$\begingroup\$

Sesos, 28 24 bytes

0000000: 1651b8 77cd1c 345e33 c67bbe c673b8 676c38 67fe98  .Q.w..4^3.{..s.gl8g..
0000015: 70e201

Uses trial division. Try it online! Check Debug to see the generated binary code.

How it works

The binary file above has been generated by assembling the following SASM code.

set numin     ; Switch to numeric input.
set numout    ; Switch to numeric output.

get, sub 1    ; Read an integer n from STDIN and decrement it.
              ; If n is 1, this will leave a 0 in cell 0.
jmp           ; While loop entry point; if the cell is 0, skip the loop body.
    add 1     ; Add 1 to restore n.

    ; The following is the actual primality test. To see how it works, consult the
    ; corresponding section of this answer.

    jmp, rwd 1, add 1, fwd 2, add 1, rwd 1, sub 1, jnz
    fwd 1
    jmp
        sub 1, rwd 1
        jmp, fwd 1, add 1, rwd 1, sub 1, jnz
        rwd 1
        jmp
            fwd 1, add 1, fwd 1, sub 1, fwd 1, add 1, rwd 1
            jmp, fwd 1, jnz
            fwd 1
            jmp, rwd 1, add 1, fwd 1, sub 1, jnz
            rwd 2
            jmp, rwd 1, jnz
            fwd 1, sub 1
        jnz
        fwd 3
    jnz
    rwd 1, sub 1
    jmp, rwd 1, jnz

jnz           ; While loop exit marker; since the previous instruction also sets
              ; an exit marker, the current cell will be 0 and we exit the loop.
rwd 1, put    ; Retrocede to the previous cell and print its content to STDOUT.
              ; If n > 1, this will print the result from the primality test.
              ; If n = 1, it will simply print 0.

Modulus computation

The core of this answer is its modulus algorithm, which is based on the divmod algorithm from Esolangs. Unlike the latter, it doesn't compute a quotient and works if the divisor is 1.

Suppose the tape in in the following state, where n and d are positive integers.

  v
  n     0     d     0     0     0

To compute n % d, we will decrement the third cell n times. Each time we decrement it, we also increment the fourth cell (so their sum is d at all times), and swap their contents every time the third cell reaches 0.

We have to decrement the first cell once for each iteration, and stop once it reaches 0. Since this will destroy the content of the first cell, we'll also increment the second cell once for each iteration, effectively copying n to the second cell.

Once the first cell reaches 0, the tape will be in the following state.

  v
  0     n   d-n%d  n%d    0     0  

We achieve this as follows.

jmp           ; While the first cell is non-zero:
    fwd 1     ;     Advance to the second cell.
    add 1     ;     Increment it.
    fwd 1     ;     Advance to the third cell.
    sub 1     ;     Decrement it.
    fwd 1     ;     Advance to the fourth cell.
    add 1     ;     Increment it.
    rwd 1     ;     Retrocede to the third cell.
    jmp       ;     While the current cell in non-zero.
        fwd 1 ;         Advance to the next cell.
    jnz       ;     This will advance to the fifth cell if the third is non-zero
              ;     and stay on the third cell otherwise.
    fwd 1     ;     Advance either to the fourth or sixth cell.
    jmp       ;     While the fourth/sixth cell is non-zero:
        rwd 1 ;         Retrocede to the third/fifth cell.
        add 1 ;         Increment it.
        fwd 1 ;         Advance to the fourth/sixth cell.
        sub 1 ;         Decrement it.
    jnz       ;     This will add the fourth/sixth cell to the third/fifth cell,
              ;     zeroing the former in the process. Since the sixth cell has a
              ;     value of 0, this loop is a no-op if the third cell in 0; other-
              ;     wise, it sets the third cell to d and the fourth cell to 0.
    rwd 2     ;     Retrocede to the second/fourth cell.
    jmp       ;     While the current cell is non-zero:
        rwd 1 ;         Retrocede to the previos cell.
    jnz       ;     This places the head to the left of the first cell.
    fwd 1     ;     Advance to the first cell.
    sub 1     ;     Decrement it.
jnz           ; 

Primality test (WIP)

For input n > 1, we can use the modulus algorithm from the previous section to implement a primality test by trial division.

If n is already on the tape, we procede as follows.

  1. Create a copy of n and decrement it to leave the tape as

                      v
          n     0     d     0     0     0
    

    where d = n - 1.

  2. Retrocede to n and use the modulus algorithm to compute n % d, leaving the tape as follows.

          v
          0     n   d-n%d  n%d    0     0  
    
  3. Advance to the cell containing n % d.

    1. If n % d > 0, add d - n % d to n % d to restore d, decrement it, and go back to step 2.

    2. If n % d = 0, we found the first divisor of n (1 for primes); go to step 4.

  4. Since n % d = 0, d - n % d = d.

    We retrocede to that cell, decrement it to leave d - 1 in it (0 if and only if n is prime), and retrocede until finding the first 0 cell. This leaves the tape as

                 v            V                 
          0      0     n     d-1   0    0     0  
    

    where v marks the location of the tape head if d - 1 > 0, and V the location if **d - 1 = 0.

    Note that the value of the cell under the tape head will be 0 in either case. The cell to the left will contain n if n is prime, and 0 if n is composite.

\$\endgroup\$
2
  • \$\begingroup\$ You should add the BF version of your modulus algorithm to the Esolangs page. \$\endgroup\$
    – mbomb007
    Jul 25, 2016 at 15:35
  • \$\begingroup\$ Done. \$\endgroup\$
    – Dennis
    Jul 25, 2016 at 17:09
4
\$\begingroup\$

Jellyfish, 13 bytes

p|&*!<
 E   i

Try it online!

Uses the squared-factorial approach based on Wilson's theorem.

Explanation

Jellyfish is Zgarb's language based on his 2D syntax challenge. The semantics are largely inspired by J, but the syntax is where it gets interesting. All functions are single characters and laid out on a grid. Functions take their arguments from the next token south and east of them and return the result north and west. This let's you create an interesting web of function calls where you reuse values by passing them into several functions from multiple directions. There are also higher-order functions called operators, which let you construct more complex functions from the built-in ones.

The only non-functions in the above code are E and &. The former redirects |'s search for its southern argument to the east, so that | actually takes i as that input.

& applied to a single unary function (in this case *) uses the binary definition by supplying the single argument twice. Since the binary definition of * is multiplication, this yields a squaring function.

Taking these things into account, we can write up a more conventional expression:

p(i | (&* ! < i))

Here, i is just the input we're testing for primality. < decrements it, ! computes its factorial, &* squares it. | is modulo although it divides its right-hand operator by its left to compute the remainder. Hence the stuff inside the p(...) computes (n-1)!^2 % n. The p just prints the result.

\$\endgroup\$
1
  • \$\begingroup\$ I'm a little surprised how much you can do with my nonsensical collection of built-ins. :D But thanks for the praise! \$\endgroup\$
    – Zgarb
    Aug 3, 2016 at 20:19
4
\$\begingroup\$

WolframAlpha, 10 bytes

isprime(n)
\$\endgroup\$
2
  • \$\begingroup\$ haha, this is interesting... \$\endgroup\$
    – ABcDexter
    Aug 31, 2016 at 9:56
  • \$\begingroup\$ Save some bytes with 'n prime'. \$\endgroup\$
    – Pavel
    Dec 29, 2016 at 22:40
4
\$\begingroup\$

Logicode, 601 511 467 bytes

circ o(n)->cond n<->0+n/o(n>)
circ p(n)->[
cond n->var c=~((~(o(n)))>)/var c=0
cond (~n)<->var d=p(c)+0/var d=c+1
d
]
circ q(n)->[
cond n->var e=~((~(o(n)))>)/var e=0
cond (~n)<->var f=e+0/var f=q(e)+1
f
]
circ r(a,b)->cond *a&*b->r(q(a),q(b))/a
circ s(a,b)->!(*(r(b,a)))
circ t(a,b)->cond b->t(q(a),q(b))/a
circ u(a,b)->cond s(a,b)->u(t(a,b),b)/!(*a)
circ v(a)->[
var j=p(j)
cond s(a,j)->[
var k=k+u(a,j)
var l=v(a)
]/[
var k=k
]
*((~k)>)
]
var j=1
var k
out v(binp)

Oh my, that is a lot of code.

Here's a rundown of what each circuit does:

  • o is a trimmer, and it strips the extra 0's at the start (this is used for p and q.
  • p is a successor, and q is a decrement.
  • r is a preliminary bit to s (lessthan).
  • s is the lessthan (which uses the remainder checker).
  • t is a subtractor, which calculates a - b for any two positive integers a and b (in binary).
  • u is a mod checker, which returns 1 if a%b is not 0, and 0 if it is 0.
  • v is the actual prime checker, which returns 1 if the number is not prime, and 0 if the number is.
    • The j and k at the bottom are the divisor (b in the mod checker) and the un-bool'd output respectively.

The final line is the "input" bit, which asks for user input in binary (any other character that is not 0 or 1 in the input will be ignored), and returns 1 if the result is not prime, and 0 if the result is.

Edit 1: Saved a whopping 90 bytes (implemented circ/cond one-liners).

Edit 2: Saved another 44 bytes (implemented boolean operator, multi-line conds, and null variables).

\$\endgroup\$
4
\$\begingroup\$

Dyalog APL, 10 9 bytes

2=∘≢∘∪⍳∨⊢

I don't think this one has been posted.

\$\endgroup\$
4
\$\begingroup\$

Tcl, 78 75 bytes

Thanks to sergiol

if $argv<2 {exit 1}
incr d
while {[incr d]<$argv} {if $argv%$d==0 {exit 1}}

Original version

if {$argv<2} {exit 1}
incr d
while {[incr d]<$argv} {if {$argv%$d==0} {exit 1}}

Works for all integer values (both negative and arbitrarily large). However, as this aims to be short and not efficient, it is written with a simple divisor={2,3,4,...} loop, so you'll begin getting noticeable lag around eight digit numbers (n ≥ 108).

The input is taken on the command-line; the output is an exit code: 0 for prime and 1 for not prime.

On Windows you can use the following batch file to test it:

@echo off
tclsh a.tcl %1
if ERRORLEVEL 1 (
  echo not prime
) else (
  echo prime
)

Use it as:

C:\foo> run.bat 2017
prime

On *nixen you can use the following bash script to test it:

#! /bin/sh
tclsh a.tcl $1
if [ $? -eq 0 ]
then
  echo prime
else
  echo not prime
fi

Use it as:

% ./run.sh 2017
prime

Enjoy!

\$\endgroup\$
3
  • \$\begingroup\$ You can save some bytes: tio.run/##K0nO@f8/… \$\endgroup\$
    – sergiol
    Oct 23, 2017 at 0:40
  • \$\begingroup\$ Please be careful to test stuff before suggesting edits. ! has higher precedence than %, so the ==0 remains... Other edits made from your suggestion. Thanks! \$\endgroup\$
    – Dúthomhas
    Oct 23, 2017 at 1:49
  • \$\begingroup\$ I tested it on my local machine and it seemed to work \$\endgroup\$
    – sergiol
    Oct 23, 2017 at 9:18
4
\$\begingroup\$

Symbolic Python, 48 bytes

___=_
__("__=_/_"+";_=-~_;__*=_*_"*~-_)
_=__%___

Try it online!

Uses Wilson's theorem, i.e. that \$(n-1)!^{2} \% n = 1\$ if \$n\$ is a prime, otherwise it equals \$0\$.

Explanation:

___=_                              # Save the value of input to ___
__(                             )  # Evaluate string
   "__=_/_"                        # Initialise __ as 1
           +";             "*~-_   # Then repeat n-1 times
              _=-~_;               # Decrement n
                    __*=_*_        # Multiply __ by n squared
_=__%___                           # Output the value of __ modulo ___
\$\endgroup\$
4
\$\begingroup\$

Alchemist, 126 bytes

_->In_a
a->b+c
0e+b+c->g+h
f+0c+b->e+b
e+0h+c->f+c
f+0b+c->c
0e+0f+g->b
0f+h+0s->c
0f+0a+0g+0h+c->f
f+0b+0c+h->s
s+0h->Out_"1"

Try it online!

Outputs 1 for primes, and nothing for composite numbers. Here's a script that tests the program against numbers below 100.

This is rather inefficient, as I removed a restriction that prevented one rule undoing another rule for a sweet one byte save (worth it!). To be much more efficient, we can replace the 0e in the third rule with f and add f to the other side too. Try it online!

Explanation:

_->In_a           # Create the input number of a atoms
a->b+c            # Convert all them to b and c atoms
                  # b will serve as a permanent save of the input
                  # c will be a counter starting at the input

0f+0a+0g+0h+c->f  # Decrement c and start the main loop by setting the f flag
# Note that f and 0e are mostly interchangeable, and the same with 0f and e     
0e+b+c->g+h       # Subtract the counter from the input, keeping a copy of both
f+0c+b->e+b       # When the counter runs out, set the e flag
0f+h+0s->c        # Move the temporary counter atoms back to the main counter
e+0h+c->f+c       # Once done, set the f flag again
f+0b+c->c         # If the counter isn't 0 when the input reaches 0
                  # Then the input is not divisible by the counter

0e+0f+g->b        # Convert the temporary input atoms back to the main input
                  # Reuse the temp counter to main counter rule again

# Once both are done, start the loop over again, decrementing the counter
# This continues until:

f+0b+0c+h->s      # If both the counter and the input reach 0 at the same time
                  # Then the input is currently divisible by the counter
                  # Decrement the temporary counter atom
s+0h->Out_"1"     # If the temp counter is 0 after that (i.e. the highest factor is 1)
                  # Print 1
\$\endgroup\$
4
\$\begingroup\$

Google Sheets, 31 bytes

=mod(fact(A1-1),A1) = mod(-1,A1

Try it on my Google Sheet It uses Wilson's theorem, which, in modular arithmetic, is:

(n − 1)! ≡ −1 (mod n) 

read: n − 1 factorial is congruent modulo n to negative 1

However, it is important to maintain the distinction between (mod n) notation and and the modulo operator. We could rewrite Wilson's theorem using more familiar mod operators:

(n − 1)! % n = -1 % n

and that's what i wrote into google sheets. Google Sheets also does parenthesis autocompletion, so i omitted the final parentheses.

\$\endgroup\$
4
\$\begingroup\$

Java, 108 bytes

interface P{static void main(String[]a){long l=new Long(a[0]),i=1;for(;0<l%++i%l;);System.out.print(l==i);}}

Try it online!

Port of my Ink answer. Would beat all existing answers in C#, Python (2 and 3), and possibly other languages if ported.

Ungolfed

interface PrimeChecker {
    // Unlike members of classes, members of interfaces are public by default. 
    static void main(String[] args) {
        long input = new Long(args[0]),
             div = 1;
        for (; 0 < (  input % (++div) // Trial division, finish when div divides input
                    % input           /* If input is at least 2, this has no effect.
                                         But (1 % n) = 1 for any n > 1
                                         so without this, the loop would never end
                                         when the input is 1 */
                   );
            ) { /* The loop body is empty, we're just using it to set div */ }
        // div is now the lowest number greater than 1 that divides the input
        // (or 2, if the input is 1)

        // The input is prime iff that number is equal to the input
        System.out.println(input == div);
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Note for those who, like me, didn't understand the existence of the last %l at first, it's to shortcut the loop when the input is 1. \$\endgroup\$ May 16, 2019 at 15:42
4
\$\begingroup\$

Taxi, 1238 bytes

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Cyclone.Pickup a passenger going to The Underground.Go to The Underground:n 2 r 2 r.Switch to plan q i.[l]Pickup a passenger going to Cyclone.Go to Zoom Zoom:n 3 l 2 r.Go to Cyclone:w.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Divide and Conquer.Go to Sunny Skies Park:n 1 r.Go to Divide and Conquer:n 1 r 1 r 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:e 1 l 1 l 2 l.Pickup a passenger going to The Underground.Pickup a passenger going to Equal's Corner.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Switch to plan c i.Go to The Underground:n 3 r 1 r 2 l.Switch to plan p i.[q]0 is waiting at Writer's Depot.[p]1 is waiting at Writer's Depot.Go to Writer's Depot:n 3 l 2 l.Pickup a passenger going to Post Office.Go to Post Office:n 1 r 2 r 1 l.[c]Go to Sunny Skies Park:n.Pickup a passenger going to Cyclone.Go to The Underground:n 1 r 1 r 2 r.Switch to plan l.

Try it online!


With many ideas from this answer, but 1 character shorter using the same shortening techniques.note This takes a slightly different approach so that “The Underground” is the return point for each iteration instead of “Zoom Zoom”. Even though this ends up only 1 character shorter, it's actually one whole instruction shorter! The reduction is relatively little because there's 2 more turns and “The Underground” is mentioned more.

The ways this answer has golfed more than the linked answer are as follows:

  • Removing all quotes around plans and strings. As long as there is no space or other special character they are not needed.
  • For the Switch to plan "name" if no one is waiting the only check is whether there is any text after "name". This means that the if no one is waiting part can be replaced with i.
  • If we did use quotes like the original answer we could also remove the spaces after closing quotes.

This is the code ungolfed with some comments.

    [Read number and convert to int]
Go to Post Office: west 1st left, 1st right, 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left, 1st right.

    [Duplicate to get numerator and denominator]
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left, 1st left, 2nd right.

    [Decrement denominator and duplicate both]
Pickup a passenger going to Cyclone.
Pickup a passenger going to The Underground.
Go to The Underground: north 2nd right, 2nd right.
Switch to plan "not prime" if no one is waiting.
[loop]
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north 3rd left, 2nd right.
Go to Cyclone: west.

    [Pickup for division...]
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Divide and Conquer.
Go to Sunny Skies Park: north 1st right.
Go to Divide and Conquer: north 1st right, 1st right, 2nd right, 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: east 1st left, 1st left, 2nd left.

    [Copy result to check if integer, first pickup ]
Pickup a passenger going to The Underground.
Pickup a passenger going to Equal's Corner.
Pickup a passenger going to Trunkers.
Go to Trunkers: south 1st left.
Pickup a passenger going to Equal's Corner.

    [Check if integer]
Go to Equal's Corner: west 1st left.
Switch to plan "continue" if no one is waiting.
Go to The Underground: north 3rd right, 1st right, 2nd left.
Switch to plan "prime" if no one is waiting.

    [Print whether it's a prime or not]
[not prime]
0 is waiting at the Writer's Depot.
[prime]
1 is waiting at the Writer's Depot.
Go to Writer's Depot: north 3rd left, 2nd left.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st right, 2nd right, 1st left.

    [Pickup numerator and decrement denominator for checking lower numbers]
[continue]
Go to Sunny Skies Park: north.
Pickup a passenger going to Cyclone.
Go to The Underground: north 1st right, 1st right, 2nd right.
Switch to plan "loop".

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Vyxal, 3 bytes

KḢ₃

Try it Online!

I thought something non trivial would be nice for a change. æ does the job for one byte but where's the fun in that?

-1 thanks to EmanresuA

Explained

KḢ₃
KḢ   # factors(input)[1:]
  ₃  # len(^) == 1 // prime numbers have only [1, n] as factors...other numbers have 1 or 3+ factors
\$\endgroup\$
2
  • \$\begingroup\$ This can be KḢ₃ \$\endgroup\$
    – emanresu A
    Nov 1, 2021 at 8:57
  • \$\begingroup\$ Also, 5 bytes version with no factorisation - 4 with r if you remove the $ \$\endgroup\$
    – emanresu A
    Nov 1, 2021 at 9:03
1 2
3
4 5
12

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.