196
\$\begingroup\$

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.

Rosetta code features lists by language of idiomatic approaches to primality testing, one using the Miller-Rabin test specifically and another using trial division. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!" and Golf you a quine for great good!.

Furthermore, the capability of implementing a primality test is part of our definition of programming language, so this challenge will also serve as a directory of proven programming languages.

Task

Write a full program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.

Input

  • If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).

  • If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.

    In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

    For scoring purposes, submit the program that corresponds to the input 1.

Output

Output has to be written to STDOUT or closest alternative.

If possible, output should consist solely of a truthy or falsy value (or a string representation thereof), optionally followed by a single newline.

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Additional rules

  • This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

  • Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

    The language Piet, for example, will be scored in codels, which is the natural choice for this language.

    Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

  • Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.

    Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

  • If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

  • Built-in functions for testing primality are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

  • Unless they have been overruled earlier, all standard rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 57617; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

\$\endgroup\$
  • \$\begingroup\$ Can I take inputs as negative numbers, where abs(input) would be the number I am testing? \$\endgroup\$ – Stan Strum Sep 6 '17 at 3:40
  • 1
    \$\begingroup\$ Is there a reason for the full program requirement, rather than allowing the full range of default input types? E.g. answering with a function that takes its input as an argument, is currently disallowed? codegolf.meta.stackexchange.com/questions/2447/… \$\endgroup\$ – Lyndon White Dec 12 '17 at 6:21
  • 2
    \$\begingroup\$ @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. \$\endgroup\$ – Dennis Dec 12 '17 at 12:51
  • 1
    \$\begingroup\$ @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

290 Answers 290

10
\$\begingroup\$

Mouse, 65 47 bytes

?N:0S:1I:(I.N.=0=^N.I.\0=[S.1+S:]I.1+I:)S.1=!$

This uses trial division.

Ungolfed:

? N:              ~ Read an integer from STDIN and store it in N
0 S:              ~ Start a summation variable at 0
1 I:              ~ Start an interator variable at 1
( I. N. = 0 = ^   ~ While I != N
  N. I. \ 0 = [   ~ Check whether I divides N
    S. 1 + S:     ~ If so, increment the sum
  ]
  I. 1 + I:       ~ Increment the iterator
)
S. 1 = !          ~ If the sum is 1, the only divisor encountered
                  ~ is 1 (we didn't go all the way to N in the
                  ~ loop) and thus N is prime
$
\$\endgroup\$
  • 3
    \$\begingroup\$ May I ask what trial division is? \$\endgroup\$ – Beta Decay Sep 13 '15 at 14:03
  • 1
    \$\begingroup\$ @BetaDecay You check the remainder when dividing by each number up to n. It's the brute force prime checking algorithm. \$\endgroup\$ – Alex A. Sep 13 '15 at 16:07
9
\$\begingroup\$

Swift 2.0, 70 100 98 82 77 75 bytes

A simple trial division loop, divided by 2 instead of sqrt() as it takes less bytes! Will default to using 64-bit ints.

let n=Int(Process.arguments[1])!;print(n<4||(2..<n).filter{n%$0<1}.count<1)
\$\endgroup\$
  • 1
    \$\begingroup\$ Is there a need to divide by two? I think you can use the 2..<n range instead to save another. \$\endgroup\$ – Geobits Sep 11 '15 at 14:56
  • 1
    \$\begingroup\$ This prints true for 0 and 1. You can change the condition from n<4|| to n>1&& to make it work. Also: You can change Process.arguments[1] to readLine()! \$\endgroup\$ – Kametrixom Sep 12 '15 at 15:58
  • \$\begingroup\$ Instead of ".count<1" you can use: "==[]" to crop some extra characters. \$\endgroup\$ – Simon Dec 4 '15 at 20:43
9
\$\begingroup\$

gs2, 2 bytes

Vk

Basically read-num is-prime.

\$\endgroup\$
9
\$\begingroup\$

C, trial division, 72 bytes

i=1;main(n){for(scanf("%d",&n);n%++i&&i*i<n;);printf("%d",n<3?n-1:n%i);}

Note special handling for n=1,2

We need to stop the loop before i gets to n-1, so i<n-1 would do, but i*i<n is more efficient.

\$\endgroup\$
  • \$\begingroup\$ I used this to post a Javascript answer with the same functionality :) \$\endgroup\$ – Sam Sep 11 '15 at 15:05
  • \$\begingroup\$ You get the exact same behaviour in one byte less by just putting everything on a single line, no separator needed. \$\endgroup\$ – hvd Sep 13 '15 at 21:45
  • \$\begingroup\$ @hvd OMG! how did I miss that ?! thanks. \$\endgroup\$ – Level River St Sep 13 '15 at 22:31
  • \$\begingroup\$ Replace i and n to save the initialization - when run with no arguments, the first parameter is 1. \$\endgroup\$ – ugoren Sep 17 '15 at 7:15
9
\$\begingroup\$

Cheddar, 37 bytes

Looks like a full program is required which unfortunately means a lot of boilerplate:

print Math.prime(Number::IO.prompt())

This might not work on TIO so you'd have to put it into a file and call it that way

Function, 10 bytes

Math.prime

This returns a function which checks if input is prime using Math.prime. Example:

$ cheddar primechecker.cheddar -x "[1, 3, 4, 10, 13] => (print) + f"
\$\endgroup\$
  • 2
    \$\begingroup\$ A full program is required. \$\endgroup\$ – Dennis Jan 6 '17 at 20:18
  • \$\begingroup\$ @Dennis >_> sorry for being so late, didn't see your comment until now but fixed \$\endgroup\$ – Downgoat Apr 13 '17 at 13:28
9
\$\begingroup\$

Dodos, 154 143 136 133 126 122 121 bytes

	N , , + > > D f f
D
	D ,
	N F > > M
M
	M m
	+ B m f
m
	F
	+ B
,
	dip F
	>
F
	+ B f
f
	+ >
	+
B
	N
N
	B dip
+
	dot
>
	dab

Try it online!

Builtins and aliases

+
	dot

This creates an alias + for the builtin function dot, which maps the vector (v1, ..., vn) to the vector (v1 + ... + vn), i.e.,

>
	dab

This creates an alias > for the builtin function dab, which maps the vector (v1, ..., vn) to the vector (v2, ..., vn).

dip

The remaining builtin, dip, maps the vector (v1, ..., vn) to the vector (|v1 - 1|, ..., |vn - 1|).

B and N

B
	N
N
	B dip

This defines a pair of mutually recursive functions. Recall that Dodos only divide or surrender.

B, if called from outside this function group, is meant to take a pair (x, y) as argument. B(x, y) simply calls N(x, y). This will always succeed, because all calls to N go through B.

N(x, y) attempts to call B(|x - 1|, |y - 1|). The tuple inequality (|x - 1|, |y - 1|) < (x, y) holds if an only if x > 0, so N(0, y) will return (0, y), since B(1, |y - 1|) surrenders.

Whenever x ≤ y, calling B(x, y) simply decrements both coordinates x times before surrendering, returning (0, y - x). If x > y, both coordinates will still be dipped x times. However, once the second coordinate reaches 0, it will cycle between 0 and 1, resulting in (0, (x - y) % 2).

N, if called from outside this function group, is meant to take a singleton (x) as argument. N(x) calls B(|x - 1|), which calls simply N(|x - 1|).

N(0) calls B(1), which attempts to call N(1). This surrenders, so B(1) returns 1, and so does N(0).

Whenever x > 0, N(x) will decrement x until reaching N(1) → B(0) → N(0) → B(1). Since B(1) surrenders, N(0)'s argument is the return value of N(x).

Thus, N(0) = 1, while N(x) = 0 whenever x > 0.

F and f

F
	+ B f
f
	+ >
	+

f returns the results of + > and + as a vector; + > takes the sum of the vector without its first coordinate, while + takes the sum f the whole vectors.

Thus, f(v1, ..., vn) = (v2 + ... + vn, v1 + ... + vn).

On occasions, we'll call f outside of F. Notably, f(x) = (0, x), f(0, x) = (x, x), and
f(x, y) = (y, x + y)

F simply calls three functions we've seen before. Since v2 + ... + vn ≤ v1 + ... + vn, B maps the result returned by f to (0, v1). + takes the sum, returning (v1).

Thus, calling F on a vector returns its first coordinate.

,

,
	dip F
	>

dip F dips the first coordinate of the argument vector, while > returns the remaining coordinates. Thus, , maps (v1, ..., vn) to (|v1 - 1|, ..., vn).

In particular, , maps (x) to (|x - 1|), so we can use it instead of dip for singleton vectors.

M and m

M
	M m
	+ B m f
m
	F
	+ B

m is always meant to be called on a pair. It simply combines a few functions we've seen before. Recall that B behaves differently if x ≤ y and if not.

We have m(x, y) = (x, y - x) if x ≤ y but m(x, y) = (x, (x - y) % 2) otherwise.

M is always meant to be called on a pair, whose first coordinate will be non-zero. M attempts to recursively call itself on the result of m. Since m doesn't change the first coordinate of its argument, we only need to examine the second one.

On the second line, B(m(f(x, y))) = B(m(y, x + y)) = B(y, x). After + takes the sum, we get x - y if x ≥ y, but (y - x) % 2 otherwise.

If y = qx, M(x, y) = M(x, qx) will successively call M(x, (q - 1)x), M(x, (q - 2)x), ..., M(x, x), M(x, 0). At the end, M(x, 0) attempts to recursively call itself, which surrenders. The return value is (x, 0), concatenated with all singletons returned by the second line. Since the second line maps (x, x) to 0, the result of M(x, y) will match the pattern (x, 0, 0, ...).

If y = qx + r, with 0 < r < x, we'll proceed in similar fashion, eventually reaching M(x, x + r), then M(x, r).

  • If r = 1 and x is even, m(x, r) = (x, (x - r) % 2) = (x, 1), and the recursive call to M surrenders. In the previous call, the second line mapped (x, x + r) to (x + r - x) % 2 = 1, so the result of M(x, y) will match the pattern (x, 1, 1, ...).

  • If r = 1 and x is odd, m(x, r) = (x, (x - r) % 2) = (x, 0), and the recursive call to M succeeds.

    Likewise, if r > 1, then m(x, r) = (x, (x - r) % 2) ≤ (x, 1) < (x, r), and the recursive call to M succeeds.

    In both cases, the second line will be evaluated for the last time with argument (x, t). Since we have t < r < x, the outcome is the non-zero vector (x - t), so the result of M(x, y) will match the pattern (x, ?, x - t, ...).

Thus, the third element of the vector returned by M(x, y) will be 0 if and only if x is a divisor of y.

D

D
	D ,
	N F > > M

D expects (n, n) as its initial argument.

The first line will recursively call D on the result of ,, so we'll call D(n, n) → D(n - 1, n) → ... → D(1, n) → D(0, n) → D(1, n), surrendering and returning (0, n).

The second line will be evaluated for every (k, n), with 0 < k ≤ n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns (k, ?, 1, ...) if k is a divisor of n, (k, ?, 0, ...) otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., n | n).

main

	N , , + > > D f f

Our entry point expects a singleton (n), with n > 0.

Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., n | n).

After discarding (0, n) with > >, a call to + takes the sum of the Booleans, counting the number of divisors of n.

, , dips the divisor count twice, resulting in a 0 only for zero or two divisors. Since n > 0, there is at least one divisor, so the result is 0 if and only if n has exactly two divisors.

Finally, N takes the logical NOT, returning 1 for primes and 0 for non-primes.

\$\endgroup\$
  • \$\begingroup\$ I've edited my answer. \$\endgroup\$ – Dennis Mar 22 '18 at 1:56
  • \$\begingroup\$ Not really related, but ... no chatroom for Dodos yet? \$\endgroup\$ – Weijun Zhou Mar 22 '18 at 2:40
  • 1
    \$\begingroup\$ @WeijunZhou Fixed. \$\endgroup\$ – Dennis Mar 22 '18 at 2:47
  • \$\begingroup\$ That's a tricky language! Some typos near the end: 0 < k < n should be 0 < k ≤ n, k | n should be n | n (two places), and "M returns 1" should be something like "M returns third element 1". \$\endgroup\$ – Ørjan Johansen Mar 22 '18 at 3:42
  • \$\begingroup\$ @ØrjanJohansen All fixed, I think. Thanks! \$\endgroup\$ – Dennis Mar 22 '18 at 3:49
8
\$\begingroup\$

><>, 25 + 3 = 28 bytes

:1-:v
v!?:<-1$**:@:
>r%n;

Inputting as a byte with i is shorter, but ><> can handle numbers larger than 255, hence the need for command line input in order to follow the rules. The +3 is for the v flag, i.e. run like

py -3 fish.py primes.fish -v 101

Outputs (n-1)*((n-1)!)^2 mod n (the initial (n-1)* is unnecessary, but it makes the code shorter).

\$\endgroup\$
  • \$\begingroup\$ I don't quite understand what you mean by your first sentence and I'm curious to know. Care to explain? The rules seem to say that it only needs to work for the integers 1 to 255. \$\endgroup\$ – cole Sep 11 '15 at 23:21
  • 3
    \$\begingroup\$ @Cole The rules say you can read a single byte "if this is your languages largest data type" \$\endgroup\$ – Sp3000 Sep 12 '15 at 1:08
8
\$\begingroup\$

Python 2, 46 bytes

m=n=input()
a=1
while~-m:m-=1;a*=m*m
print a%n
\$\endgroup\$
  • \$\begingroup\$ Just 2 bytes shorter than the functional version: n=input();print all(n%m for m in range(2,n))*~-n. If all([]) returned False it would be the other way around. \$\endgroup\$ – DLosc Sep 11 '15 at 19:34
8
\$\begingroup\$

Matlab/Octave 24

It is just using a builtin function, using a sieve.

disp(isprime(input('')))

You could also use this:

isprime(input(''))

Which would print the output as the last result in the console, but I am not sure whether this is allowed.

\$\endgroup\$
  • \$\begingroup\$ I am curious, where did you get the information about the other method that you mentioned? (Perhaps it is different in a newer vesion?) \$\endgroup\$ – flawr Sep 15 '15 at 17:52
  • \$\begingroup\$ This link I guess the MuPAD notice at the top is relevant. \$\endgroup\$ – Martin Ender Sep 15 '15 at 17:56
  • \$\begingroup\$ Yes that is what makes the difference, thanks for the link=) \$\endgroup\$ – flawr Sep 15 '15 at 19:46
8
+200
\$\begingroup\$

Sesos, 50 49 bytes

Algorithm #3...

0000000: 16def7 f5991b 7441bf 3f0ebb eecfd8 b86b33 b7eb33  ......tA.?......k3..3
0000015: 37ecda bccdd8 b86b33 3ffcfe 8c7de8 797cfc f599c3  7......k3?...}.y|....
000002a: f973f5 8479c5 03                                  .s..y..

Try it online!

This is the very first working code I got, so I'm sure it's possible to shave off a few more bytes here. Here's the BF-code I wrote (with some rather sparse comments that are mostly meant for myself):

,
[>+>+>+<<<-]                ; triplicate input
>>[-                        ; i from n_1 down to 0
    <+[-<<<+>>>             ; j from n down to 0 copying n to the left
        [                   ; k from j down to 1
            >[<<+<+>>>-]    ; add i to the values on the left
            <<[>>+<<-]      ; move one copy of i back
            >>>>+<<<-       ; decrement k while copying j to the right
        ]
        >>[<<+<<->>>>-]     ; subtract n from i*j while copying it
        <<[>>+<<-]          ; move n back
        >>>[<<<+>>>-]       ; move j back
        <<<<<[              ; if not equal:
            ,               ; reset to zero
            >               ; move to zero left of j
        ]
        >
    ]
    <<<[>>>+<<<-]           ; move n back to j
    >[<]>>>                 ; if we didn't exit move back to i
                            ; otherwise remain on the zero left of j
]
>,+>-[<->,]<.

I then used this Retina script to convert that to Sesos ASM:

set numin
set numout

get
jmp
   fwd 1
   add 1
   fwd 1
   add 1
   fwd 1
   add 1
   rwd 3
   sub 1
jnz
fwd 2
jmp
   sub 1
   rwd 1
   add 1
   jmp
      sub 1
      rwd 3
      add 1
      fwd 3
      jmp
         fwd 1
         jmp
            rwd 2
            add 1
            rwd 1
            add 1
            fwd 3
            sub 1
         jnz
         rwd 2
         jmp
            fwd 2
            add 1
            rwd 2
            sub 1
         jnz
         fwd 4
         add 1
         rwd 3
         sub 1
      jnz
      fwd 2
      jmp
         rwd 2
         add 1
         rwd 2
         sub 1
         fwd 4
         sub 1
      jnz
      rwd 2
      jmp
         fwd 2
         add 1
         rwd 2
         sub 1
      jnz
      fwd 3
      jmp
         rwd 3
         add 1
         fwd 3
         sub 1
      jnz
      rwd 5
      jmp
         get
         fwd 1
      jnz
      fwd 1
   jnz
   rwd 3
   jmp
      fwd 3
      add 1
      rwd 3
      sub 1
   jnz
   fwd 1
   jmp
      rwd 1
   jnz
   fwd 3
jnz
fwd 1
get
add 1
fwd 1
sub 1
jmp
   rwd 1
   sub 1
   fwd 1
   get
jnz
rwd 1
put

And of course the final conversion to binary is done by Sesos itself.

I scrapped three earlier attempts for trial division, and ultimately really got tired of the modulo computation. So I started thinking about how I could avoid that altogether. I ended up coming up with a very simple primality test, that for some reason never occurred to me before and might be handy for a lot of other esolangs where doing a multiplication is fine but computing a modulo is a royal pain:

In essence, I just compute the full multiplication between [1, ..., n-1] and [1, ..., n] starting from the largest value. After each multiplication, I subtract n from the result. If that gives 0, I terminate. This is bound to terminate, because at the beginning of the final iteration of the outer loop, I'm computing 1 * n. If I get there, it's a prime. Otherwise, some earlier multiplication will have given n and the loop stops there instead. That means I can simply check after terminating whether the first iterator is equal to 1 or not in order to decide primality.

I'll probably post the Brainfuck-version of this as well, once I'm happy with the golfing.

\$\endgroup\$
8
\$\begingroup\$

ShapeScript, 53 25 23 bytes

_11?1-"@1?*@1-"1?*!?*@%

The program uses Wilson's theorem; it prints 1 for primes and 0 for non-primes. Input is in unary.

I created ShapeScript for this competition. The interpreter on GitHub has a slightly modified syntax and better I/O (none of which are required in this answer).

Try it online!

How it works

_        Take the length of the input to convert from unary to integer (N).
1        Push 1 (accumulator).
1?1-     Push a copy of N and subtract 1. Let's call the result I.
"        Push a string that, when evaluated, does the following:
  @        Swap I with the accumulator.
  1?       Push a copy of I.
  *        Multiply it with the accumulator.
  @        Swap the updated accumulator with I.
  1-       Decrement I.
"
1?       Push a copy of N-1.
*!       Repeat the string N-1 times and evaluate the result.
         This calculates (N-1)! and leaves I = 0 on the stack.
?        Use I to copy the factorial.
*        Multiply to calculate the factorial's square.
@%       Calculate N%((N-1)!*(N-1)!).
\$\endgroup\$
8
\$\begingroup\$

Prolog (SWI), 42 40 bytes

+X:-X>1,2+X.
Y+X:-X=:=Y;0<X mod Y,1+Y+X.

Try it online!

Tests primality by checking whether any of the numbers less than the number and greater than one divide the number.


Explanation

+X:-X>1,2+X

defines a new predicate +/1 that is true if X > 1 and 2+X is satisfied. Despite what it appears, this is not an arithmetical expression. It refers to the predicate defined on the next line.

Y+X:-X=:=Y;0<X mod Y,1+Y+X.

This defines a new predicate +/2 that is true if X =:= Y (=:= represents equality for arithmetic expressions), or both X mod Y is not zero (since X mod Y can't be negative, checking that it is greater than zero is sufficient) and 1+Y+X is true. The trick with 1+Y+X is that the two pluses do not end up being used the same way. The + operator is left associative so 1+Y+X is equivalent to (1+Y)+X. Since the expression must be a call to a predicate and +/2 is a predicate that I defined, the interpreter then calls +/2 with arguments 1+Y and X. Thus recursively the program will check whether any Y from 2 to X-1 divides X (it stops at X since X=:=Y would be true and so the truth value of the others becomes irrelevant).

Operators in SWI-Prolog

This program heavily abuses the way operators are handled in SWI-Prolog. SWI-Prolog does not define predicates for arithmetic operators such as +. This makes sense since the arithmetical + is not a predicate since the output of a predicate must be true or false. What SWI-Prolog does instead is it builds structures out of the operators and then the predicates that evaluate arithmetic expressions (such as =:= and <) know how to evaluate those structures. For instance after the +/2 predicate in my program recurses three times with the initial Y=2 then Y=1+(1+(1+2)) not Y=5. The fact that + is not defined as a predicate means that I can define it as a predicate myself and since it is an operator I can save the bytes that I would otherwise need to spend on parentheses and commas.

\$\endgroup\$
7
\$\begingroup\$

Foo, 40 bytes

&1@@@>>&>&1<(2-1@<<@>&%+1@>>%<)&2/@>+%$i

Probably not the best approach, but I wanted to give it a try. Thanks to the "wonders" of Foo's do-while loops, I had to special case 1 and 2, both of which output errors to STDERR (but STDOUT output is correct).

The input is hardcoded as the number after the first &.

\$\endgroup\$
7
\$\begingroup\$

Bubblegum, 98 bytes

from math import factorial as F#
try:n=int(i)-1;o=n*(F(n)%-~n==n)
except:o=sum(map(int,i.split()))

This prints p - 1 if p is prime and 0 otherwise.

It may not look like it, but this is the shortest known Bubblegum program that achieves this task.

There are probably shorter programs, but their discovery would require a cryptographic break of the SHA-256 hash.

\$\endgroup\$
  • \$\begingroup\$ Did you choose the hash value based on this program or did you find it starting from a random hash? \$\endgroup\$ – Sp3000 Sep 11 '15 at 17:03
  • \$\begingroup\$ Option 1. The program works for addition and primality testing. \$\endgroup\$ – Dennis Sep 11 '15 at 17:05
  • \$\begingroup\$ Wait what according to the esolangs page this is identical to the code for calculating a sum... \$\endgroup\$ – ev3commander Nov 18 '15 at 20:56
  • \$\begingroup\$ @BlockCoder1392 If you give this program one number it will test primality. If you give it two or more it will add. \$\endgroup\$ – pppery Feb 25 '16 at 2:13
7
\$\begingroup\$

Perl, 23 20 bytes

say/^(?!(..+)\1+$)/

using -n option.

say<>=~/^(?!(..+)\1+$)/

Using the regular expression+unary input approach, prints 11 (or whatever number you entered) or a blank line.

Bonus: decimal version, 31 bytes

(1x<>)=~/^1$|^(11+)\1+$/||say 1
\$\endgroup\$
  • \$\begingroup\$ Does this require input in unary? \$\endgroup\$ – Lynn Sep 11 '15 at 18:45
  • \$\begingroup\$ @Mauris, clarified as you commented :) \$\endgroup\$ – ThaddeusB Sep 11 '15 at 18:46
  • \$\begingroup\$ The 20 byte version reports 1 as a prime, doesn't it? \$\endgroup\$ – Martin Ender Sep 14 '15 at 10:14
  • \$\begingroup\$ The decimal version says 0 is prime. \$\endgroup\$ – DanaJ Sep 14 '15 at 12:12
  • 2
    \$\begingroup\$ @DanaJ Good question... Per Dennis' clarification 0 failing is not an issue. \$\endgroup\$ – ThaddeusB Sep 14 '15 at 16:37
7
\$\begingroup\$

FRACTRAN, 144 bytes

29/14 222/377 59/26 247/59 329/57 19/47 2/19 11/29 403/407 217/33 11/31 2/11 1/37 1/2 23/9 43/69 23/43 1/23 425/41 4823/85 17/53 41/25 2/119 1/5

This took me way longer than expected - special casing 1 was pretty annoying. Takes 5^n as input and outputs 3^0 = 1 (falsy) if composite, or 3^1 = 3 (truthy) if prime.

The approach is similar to Conway's prime generator, performing a divmod on descending divisors. This isn't as compact though, so there's still much to golf.

\$\endgroup\$
  • \$\begingroup\$ How does 3^1 = 7? \$\endgroup\$ – feersum Sep 13 '15 at 1:06
  • \$\begingroup\$ @feersum Updated one number, forgot to update the other. Thanks for pointing out \$\endgroup\$ – Sp3000 Sep 13 '15 at 1:50
7
\$\begingroup\$

Fourier, 44 bytes

Guess who? :D

1~h2~xI~g<3{1}{5+g~g}g(g%x{0}{~hgv~x}x^~x)ho

Yes, it's my very own Fourier again, in a situation where it is actually in the running for a golfing competition.

The most bytes are spent on handling the input cases for 1 and 2.

Prints "1" for True and "0" for False.

Explanation

1~h                                            # Set h to 1
   2~x                                         # Set x to 2
      I~g                                      # Set g to user input      
         <3{1}{     }                          # If accumulator is less than three then
               5+g~g                           # Add 5 and g and set g to that value  
                     g(                  )     # Loop until the accumulator equals g
                       g%x{0}{      }          # If g%x equals 0, then
                              ~hgv~x           # Set h to 0 and set x to g-1
                                     x^~x      # Increment x and set x to that value
                                           ho  # Output the value of h
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6), 47 bytes

alert(!/^(11+)\1+$/.test('1'.repeat(prompt())))
\$\endgroup\$
  • \$\begingroup\$ @ETHproductions OK. I'm working on the case of the input being 1. \$\endgroup\$ – Toothbrush Sep 13 '15 at 17:54
  • 2
    \$\begingroup\$ This seems to be missing output. It assumes that the code is run in a console, i.e. a REPL environment. The challenge explicitly asks for a full program though. \$\endgroup\$ – Martin Ender Sep 14 '15 at 9:43
  • \$\begingroup\$ Virtually identical to one already posted, which also covers the '1' case: codegolf.stackexchange.com/a/57692/30793 \$\endgroup\$ – Mwr247 Sep 14 '15 at 14:51
  • 1
    \$\begingroup\$ Also, needs an alert or other print function to be considered valid for code golf: meta.codegolf.stackexchange.com/questions/803/… \$\endgroup\$ – Mwr247 Sep 14 '15 at 16:48
  • \$\begingroup\$ Outputs true for 0 and 1. \$\endgroup\$ – RK. Sep 17 '15 at 19:24
7
\$\begingroup\$

PowerShell, 35 Bytes

param($a)$a-match'^(?!(..+)\1+$)..'

Uses the same regex from Martin's Retina answer, as that's way shorter than anything that will wind up using the [math]:: libraries one would normally use. Expects input as command-line argument in unary format.

Corrected from initial version (which was apparently specific to the particular PowerShell implementation I coded it on) thanks to Jonathan Leech-Pepin. Grr undocumented version differences.

Examples:

PS C:\Tools\Scripts\golfing> .\is-this-number-a-prime.ps1 111111
False

PS C:\Tools\Scripts\golfing> .\is-this-number-a-prime.ps1 1111111
True

Bonus - PowerShell pipeline input, 29 Bytes

%{$_-match'^(?!(..+)\1+$)..'}

Same as the above, just called differently, which shaves bytes. For example,

PS C:\Tools\Scripts\golfing> 111111 | %{$_-match'^(?!(..+)\1+$)..'}
False
\$\endgroup\$
  • \$\begingroup\$ I actually had to wrap the $args[...]..' in () to be able to get it to resolve. Otherwise it was always True. \$\endgroup\$ – Jonathan Leech-Pepin Nov 4 '15 at 21:11
  • \$\begingroup\$ @JonathanLeech-Pepin Interesting - likely a versioning difference in how operations are ordered. I primarily code in PowerShell v4 (using the ISE); what were you using? \$\endgroup\$ – AdmBorkBork Nov 4 '15 at 21:27
  • \$\begingroup\$ Happened on Win7 with the latest 5.0 rtm (August), also happens on Win10 with built-in. It is not however an issue with the pipeline version. On the other hand: param($a)$a-match'^(?!(..+)\1+$)..' works and is exactly 35 bytes as well. \$\endgroup\$ – Jonathan Leech-Pepin Nov 4 '15 at 21:40
  • \$\begingroup\$ @JonathanLeech-Pepin Indeed -- I just tested and confirmed on a Windows 7 machine. How strange. Yay for undocumented features :-/ ... I've corrected the code with the param($a) iteration, which should work on any version. Thanks for the assist! \$\endgroup\$ – AdmBorkBork Nov 4 '15 at 21:56
7
\$\begingroup\$

Sesos, 67 66 65 bytes

Edit: Saved a byte by using another get instead of a loop.

Edit: Saved a byte because I don't need this rwd 6 after I changed from sub 1 to add 1 before it.

Try it online

The hexdump:

0000000: 16f8be 76ca83 e653e3 b472f0 750ef0 af9f1f fcebbb  ...v...S..r.u........
0000015: 7f7ec6 77e13b bf41f7 2961f0 af9f1f fcebbb 7f6ec7  .~.w.;.A.)a........n.
000002a: 3fc013 ef9da3 a0fbbc 77ecc7 776e1b bf73b8 576a9c  ?........w..wn..s.Wj.
000003f: 663e                                              f>

This is the Sesos assembly code that I wrote, which is assembled into the above binary to be executed:

set numin
set numout
get

jmp     ; n += (n==2)
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz
add 2
fwd 1
jmp
sub 1
rwd 1
sub 1
fwd 1
jnz
add 1
rwd 1
jmp
fwd 1
sub 1
rwd 1
get
jnz
fwd 1
jmp
sub 1
fwd 1
add 1
rwd 1
jnz
fwd 1

jmp     ; list from n to 1
jmp
sub 1
fwd 3
add 1
rwd 3
jnz
fwd 3
jmp
sub 1
fwd 3
add 1
rwd 6
add 1
fwd 3
jnz
fwd 3
sub 1
jnz

rwd 6   ; List [n, n-1, ..., 2, 2]. We don't want n%1.
add 1
jmp
rwd 6
jnz
fwd 6

jmp     ; move n one cell to the left
sub 1
rwd 1
add 1
fwd 1
jnz

add 2   ; copy the n's
jmp
rwd 1
jmp
sub 1
fwd 3
add 1
rwd 3
jnz
fwd 3
jmp
sub 1
fwd 3
add 1
rwd 6
add 1
fwd 3
jnz
fwd 4
jnz
rwd 7

jmp     ; compute each divmod, only the n%d results will be used
jmp
sub 1
fwd 1
sub 1
jmp
fwd 1
add 1
fwd 2
jnz
fwd 1
jmp
add 1
jmp
sub 1
rwd 1
add 1
fwd 1
jnz
fwd 1
add 1
fwd 2
jnz
rwd 5
jnz
rwd 6
jnz
fwd 8

jmp     ; go to first modulus of zero, or past end of list
fwd 6
jnz

fwd 1   ; negate cell to the right
jmp
rwd 1
add 1
fwd 1
jmp
sub 1
jnz
jnz
add 1
rwd 1
jmp
fwd 1
sub 1
rwd 1
sub 1
jnz

fwd 1   ; output
put

Explanation (In BF, since I actually wrote it in BF first)

Sesos and BF are closely related, so I will write the explanation in BF to take less space (it won't be on as many lines):

>   fwd 1
<   rwd 1
+   add 1
-   sub 1
,   get
.   put
[   jmp
]   jnz

First, Sesos is basically BF, but there is some I/O help, using the assembler directives set numin and set numout. These allow me to take an unbounded integer as input, into a single cell, or output that cell as an integer. I decided this was the easiest way to write the program for all positive integers.

My explanation is of each section from the above code, with sub-explanations showing the manipulations of the tape, in an attempt to help you understand the process and algorithm. I put the tape in curly braces, and use > to denote the pointer's location on the tape.

Section 1, the bug-fix / edge case:

It should be noted that before I fixed this, my code was only 54 bytes. Because of how I determine if a number is prime later, I had to add one to n if n==2, so I do that first. I use a , here (get) to zero a cell instead of looping with [-].

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

    n += (n==2):
    goal 1: { 2 n n }
    goal 2: { 0 n==2 n }
    goal 3: { 0 0 n* }

    { n 0 0 }
    [->+>+<<]++>
    { 2 >n n }
    [-<->]+<[>-<,]>
    { 0 >n==2 n }
    [->+<]>
    { 0 0 >n* }

Section 2, the list and my ultimate goal:

The way I check if n is prime is to check n modulo every number from n-1 to 2, which I figured would be simplest. My main goal was to reach the following data structure:

0 >{n n-1 0 0 0 0, n n-2 0 0 0 0, ..., n 2 0 0 0 0}

This facilitates the DivMod algorithm I planned to use, which requires n d 0 0 0 0 on the tape.

So I create a list from n-1 to 0, with the necessary spacing. I copy the first marked cell to the second, then copy that temp cell back into the original and into the next. Then subtract one. This repeats until I hit zero.

0 { 0 >n }
[[->>>+<<<]>>>[->>>+<<<<<<+>>>]>>>-]

0 {0 n 0 0 0 0, 0 n-1 0 0 0 0, ..., 0 2 0 0 0 0, 0 1 0 0 0 0, 0 >0 0 0 0 0}
     ^     ^      ^

Then, make the last section find n%2, since n%1 would cause a result of 0 for every n. Changing it to a zero instead of a two produces the wrong answer for n=1. After that, move back to n.

<<<<<<+
[<<<<<<]>>>>>>

0 {0 >n 0 0 0 0, 0 n-1 0 0 0 0, ..., 0 2 0 0 0 0}

Move n left one cell, preparing to copy it across the list:

[-<+>]

0 {n >0 0 0 0 0, 0 n-1 0 0 0 0, ..., 0 2 0 0 0 0}

Section 3, copy the n's

I copy n to the correct position for each entry in the list, so that I'll be ready to use the DivMod algorithm for each entry. I first add two here, so that we find another n%2, rather than n%0. This is nearly the same code as in section 2, except that I compare to the cell on the right each time, in order to stop upon completing the length of the list.

++[<[->>>+<<<]>>>[->>>+<<<<<<+>>>]>>>>]

0 {n 2 0 0 0 0, n n-1 0 0 0 0, ..., n 2 0 0 0 0, n >0 ...}
   ^     ^      ^

Section 4, compute each DivMod

I go through the list, doing the algorithm for each, after which only the n%d results are used. Though the algorithm only lists 4 cells on the site, it relies on the 5th and 6th cells being zero for its magic to work. I used the version which does not preserve n, since I won't need it anymore.

The algorithm:

# >n d 0 0 0 0
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
# >0 d-n%d n%d n/d 0 0

As applied across the list (x marks stuff I don't really need, but do make use of later):

[
    [->-[>+>>]>[+[-<+>]>+>>]<<<<<]
    <<<<<<
]>>>>>>>>

0 {0 x >n%(n-1) x 0 0, 0 x n%(n-2) x 0 0, ..., 0 x n%2 x 0 0}

Section 5, if any n%d == 0

I check the list from left to right.

{0 x >n%(n-1) x 0 0, ...}

[>]

What? You expected more? Well it really is that simple. This stops at the first occurrence of 0, which is either in this list, meaning the number is not prime, since it has a divisor, or we went past the list, and the number is therefore prime.

Section 6, negate the cell to the right and output

Uses this algorithm:

temp0[-]
x[temp0+x[-]]+
temp0[x-temp0-]

I don't need the first line, since my temp is already zero. I also use get to zero a cell instead of a loop. The last line prints the resulting number, a one if prime, or a zero if not.

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

Concluding remarks

Overall, this was a fun challenge. I found the mapping to BF pretty quickly with trail and error using the interpreter and the documentation. I completed it with something like 8 hours of effort. Much of the writing occurred in Notepad++ in BF that I then converted to Sesos with a Python program, tested, and debugged.

Convert BF to Sesos

\$\endgroup\$
7
\$\begingroup\$

Reflections, 194 181 bytes

  _v@\
|* / (0    /\
   /;*      <
/0):\(1/# + /#+\
:  ; >~<   \ _ /
#|v\/ 1)
(0*    \#:(1 \
\\#  \(0__0) /
 _  / (0\
/^^: 0):/
\#+ _#_
/0):^\
:  / /
#
(0 >#* _#_
\ _<
   \        /

Test it!

Outputs 1 for prime, else 0.

Explanation

First we parse the number:

  _v@\
|* / (0
     *
     (1/ -> IP leaves here
     >~<
      1)
       \#:(1 \
     \(0__0) /
  • _ reads a line from input
  • v reflects the IP down
  • / reflects the IP left
  • * at (1|1) pushes 1×1=1
  • | reflects the IP right
  • * pushes another 1
  • / reflects the IP up
  • v pops a value off the stack and reflects the IP right as it's true
  • @ at (4|0) converts all input to numbers
  • \ reflects the IP down
  • (0 moves the first digit to stack 0
  • * at (5|2) pushes 5×2=10
  • (1 moves the 10 to stack 1
  • > reflects the IP right
  • ~ pushes the number of left digits
  • < pops that number and reflects the IP down if it's not 0:
    • 1) moves the 10 from stack 1 to the main stack
    • \ reflects the IP right
    • # redefines (0|0)
    • : doubles the 10
    • (1 moves the top 10 to stack 1 again
    • \ reflects the IP down
    • / reflects the IP left
    • 0) pulls the previous result from stack 0
    • _ at (1|1) multiplies the previous result and 10
    • _ at (0|1) adds the next digit
    • (0 pushes the result to stack 0
    • \ reflects the IP up
    • > enters the loop again
  • if it's zero, reflect the IP up
    • / reflects the IP right

Now, we have the test number on stack 0.

Then, we initialise the loop:

            <
       /# + /
  • / reflects the IP right
  • # redefines (0|0)
  • + at (2|0) pushes 2+0=2
  • / reflects the IP up
  • < reflects the IP left

Now, we have a 2 (the counter) on the main stack and the input number on stack 0.

Then we have the real loop:

           /\
   /;*      <
/0):\       /#+\
:  ;       \ _ /
#|v\/
(0*
\\#
 _  / (0\
/^^: 0):/
\#+ _#_
/0):^\
:  / /
#
(0 >#* _#_
\ _<
   \        /
  • * pushes x×y
  • ; pops that again
  • / reflects the IP down
  • : duplicates the counter
  • ; discards the duplicate
  • \ reflects the IP right
  • / reflects the IP up
  • \ reflects the IP left
  • : duplicates the counter again
  • 0) pulls the input number from stack 0
  • / reflects the IP down
  • : duplicates the input
  • # redefines (0|0)
  • (0 pushes the duplicated input to stack 0
  • \ reflects the IP right
  • \ reflects the IP down
  • _ at (1|3) pops the counter and the input and pushes whether they're equal
  • ^ pops the test and reflects the IP left if true (i.e. if we have tested all numbers less than the input and haven't found a factor → the number is prime):
    • / reflects the IP down
    • \ reflects the IP right
    • # redefines (0|0)
    • + at (1|0) pushes 1+0=1
    • _ at (3|0) converts to string
    • # redefines (0|0)
    • _ at (1|0) prints
    • then the IP leaves the grid and the program ends
  • else the IP is reflected right:
  • ^ reflects the IP up
  • # redefines (0|0)
  • * pushes 0×-1=0
  • v pops the 0 and reflects the IP left
  • | reflects the IP right
  • v reflects the IP down
  • * pushes 0×-1=0
  • # redefines (0|0)
  • ^ pops the zero and reflects the IP right
  • : duplicates the counter
  • 0) pulls the input from stack 0
  • : duplicates it
  • / reflects the IP up
  • \ reflects the IP left
  • (0 pushes the duplicated input to stack 0
  • / reflects the IP down
  • _ at (2|3) checks if the input is greater than the counter. Note that this is only false if the input is 1 as else the previous check applies before.
  • ^ reflects the IP right if the check was false (i.e. input is < 2):
    • \ reflects the IP down
    • / reflects the IP left
    • / reflects the IP down
    • > enters the 'output zero' part, see below
  • else the IP is reflected left:
  • : duplicates the counter (once again)
  • 0) pulls the input from stack 0 (once again)
  • : duplicates the input (once again)
  • # redefines (0|0)
  • (0 pushes the input to stack 0 (once again)
  • \ reflects the IP right
  • _ at (2|2) pops input and counter and pushes input modulo counter
  • < pops the result and reflects the IP up if 0 (it's a factor):
    • > reflects the IP right into the 'output zero' part, see below
  • else (it's no factor) the IP is reflected down:
  • \ reflects the IP right
  • / reflects the IP up
  • / reflects the IP right
  • # redefines (0|0)
  • + at (1|0) pushes 1+0=1
  • \ reflects the IP down
  • / reflects the IP left
  • _ at (0|1) adds the 1 to the counter (counter++)
  • \ reflects the IP up
  • / reflects the IP right
  • \ reflects the IP down
  • < enters the loop again

Now for the 'output zero' part:

   >#* _#_
  • > reflects the IP right
  • # redefines (0|0)
  • * at (1|0) pushes 1×0=0
  • _ at (3|0) converts to string
  • # redefines (0|0)
  • _ at (1|0) prints '0'
  • then the IP leaves the grid and the program ends
\$\endgroup\$
  • \$\begingroup\$ Okay, I need to check out this language. \$\endgroup\$ – Esolanging Fruit Mar 7 '18 at 20:05
6
\$\begingroup\$

Julia, 46 bytes

n=int(ARGS[1]);show(sum([n%i==0for i=1:n])==2)

An integer is read as the first command line argument using int(ARGS[1]) and the result is printed to STDOUT using show. Primality is checked using trial division with the same formulation as my R answer.

Note that the builtin function isprime uses the Miller-Rabin algorithm, which is probabilistic and is thus unsuitable for this challenge. (Thanks to Martin Büttner for pointing that out.)

Saved 4 bytes thanks to kvill.

\$\endgroup\$
  • 1
    \$\begingroup\$ Isn't the use of ARGS[1] possible, as an alternative to readline()? \$\endgroup\$ – kvill Sep 13 '15 at 20:38
  • \$\begingroup\$ @kvill Yeah, I suppose so. Thanks. \$\endgroup\$ – Alex A. Sep 13 '15 at 20:44
  • 1
    \$\begingroup\$ ...and even show() is possible for another byte. \$\endgroup\$ – kvill Sep 13 '15 at 20:52
  • \$\begingroup\$ @kvill Good call. \$\endgroup\$ – Alex A. Sep 13 '15 at 21:13
6
\$\begingroup\$

JavaScript (ES6), 43 bytes

This is the shortest solution so far that accepts decimal input. Also, it doesn't use regex like the other short solutions.

p=n=>--d-1?n%d&&p(n):1;alert(p(d=prompt()))

What it uses instead is a recursive function, something that wasn't very useful when you needed to write function and return , but is now very useful because of the => notation.

Ungolfed:

p=n=>                 // p=function(n){ return
--d-1?                // if --d is not 1 (decrement d)
    n%d&&p(n)         // if n divdes d, false, else rerun the function
                      // (d has already been decremented)
:1;                   // else (if d is 1) then true
alert(p(d=prompt()))  // Use the function on the input
                      // and assign this value to d
\$\endgroup\$
  • \$\begingroup\$ One byte shorter: n%d?p(n):0 -> n%d?p(n):0 \$\endgroup\$ – user81655 Apr 9 '16 at 11:55
  • \$\begingroup\$ @user81655 I dont get what you mean. Did you make a typo? it's twice the same thing \$\endgroup\$ – Jens Renders Apr 10 '16 at 16:27
  • \$\begingroup\$ Haha, I did sorry. I meant to write n%d&&p(n). \$\endgroup\$ – user81655 Apr 10 '16 at 16:29
  • \$\begingroup\$ @user81655 Nice! I was looking for things like this but did'nt see it :) \$\endgroup\$ – Jens Renders Apr 10 '16 at 16:33
6
\$\begingroup\$

Excel, 41 bytes

=2=SUM(N(0=MOD(A1,ROW(OFFSET(A1,,,A1)))))

Takes input from A1.

4 bytes saved thanks to @Joffan!

\$\endgroup\$
  • \$\begingroup\$ This didn't work for me, even entered as an array formula (as I think you intended). However this array formula works: =OR(A1=2,AND(MOD(A1,ROW(INDIRECT("2:"&A1-1))))) at 47 bytes. \$\endgroup\$ – Joffan Jun 23 '16 at 15:21
  • \$\begingroup\$ You sure? This works fine for me. Put the input number in A1, put the formula in another cell, and it should work. \$\endgroup\$ – Mama Fun Roll Jun 23 '16 at 22:46
  • \$\begingroup\$ What numbers did you try it with? 9, for example? [BTW I learned an interesting dodge from this, so thanks] \$\endgroup\$ – Joffan Jun 23 '16 at 22:48
  • \$\begingroup\$ Hmm... interesting. This doesn't work for you? \$\endgroup\$ – Mama Fun Roll Jun 23 '16 at 23:00
  • \$\begingroup\$ No, it gives TRUE for 9 - maybe Excel version? I'm using 2010 \$\endgroup\$ – Joffan Jun 23 '16 at 23:05
6
\$\begingroup\$

Cubix, 21 bytes

%@\?I:u;>O/)((./0\)?/

Cubix is a 2-dimensional, stack-based esolang. Cubix is different from other 2D langs in that the source code is wrapped around the outside of a cube.

Test it online! Note: there's a 50 ms delay between iterations; see the browser console for current progress.

Explanation

(Note: This is somewhat confusing; I'll add a diagram with colored paths when I get a chance.)

The first thing the interpreter does is figure out the smallest cube that the code will fit onto. In this case, the edge-length is 2. Then the code is padded with no-ops . until all six sides are filled. Whitespace is removed before processing, so this code is identical to the above:

    % @
    \ ?
I : u ; > O / )
( ( . / 0 \ ) ?
    / .
    . .

Now the code is run. The IP (instruction pointer) starts out on the top left char of the far left face, pointing east. Here's an overview of the basic commands:

  • \|/_ are mirrors, and reflect the IP depending on the direction it's traveling.
  • >v<^ set the direction of the IP unconditionally.
  • ? turns the IP right if the top item is positive, or left if it's negative.
  • I inputs an integer (signed or unsigned).
  • O outputs an integer.
  • : duplicates the top item.
  • ; pops an item.
  • @ ends the program.

The first char we encounter is I, which inputs an integer from STDIN. : duplicates this integer. u makes the IP turn right twice, so it ends up on the no-op below u, facing west. Now it enters the main loop.

First, we need to check if this integer is less than 2, in which case it's not prime. So we decrement it twice with ((, then check its sign with the ?. If it's less than 0, the IP is turned left, in which case it wraps around to the bottom-left of the bottom panel, facing north. Removing the direction changes from the next bit, we get 0O@, which pushes a 0, outputs as an integer, and terminates the program.

If the input is more than 2, the IP is turned right at the ?. Next, the top item is incremented once with ). The IP wraps around to the % at the top-left of the top face, which pushes the modulo of the top two numbers. If the input M modulo any number 1 < N < M is 0, the number is not prime. So we check the sign of the top item with ?. If the top item is now 0, it gets output with O, then @ terminates the program.

Otherwise, the IP gets sent down to the ;, which pops the result of % since we have no further use for it. Now it's back where it started, and the loop continues until it takes a different turn at either of the ?s.

There is one more case I didn't mention before: if the sign of the top item is 0 at the first ?, that means we've run through every number 1 < N < M, which in turn means the input is prime. Since the top item must be 0, we increment it with ), then output with O and terminate the program with @.

I think this program is optimal, but I'm not certain. I'll keep looking to find a better solution.

\$\endgroup\$
6
\$\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\$
6
\$\begingroup\$

GNU sed -r, 19 18

/^(1|(11+)\2+)$/c↲

(that last isn't a literal character; it stands for a final newline).

Takes unary input on stdin. Anything that can be represented by two or more 1s, two or more times is a composite number and replaced by an empty line. Prime numbers are all truthy and left as-is.

There's a slight catch in that this would classify 1 as a prime (it's actually neither prime nor composite), so there are an extra 4 bytes (1|) to handle that case.

If you're willing to accept empty string as a false "output", then we could use d instead of c↲ for a further 1 byte saving.

\$\endgroup\$
  • 1
    \$\begingroup\$ I should have looked through the other answers before posting this - I thought I was being original and clever! \$\endgroup\$ – Toby Speight Sep 15 '15 at 14:40
5
\$\begingroup\$

dc, 27 bytes

?dd[d1-d1<f*]dsfxr/r2r|p

How it works (example stack for input 7):

?                             7               push input
 dd                           7 7 7           dup
   [d1-d1<f*]dsf              7 7 7 {fact}    f = factorial macro
                x             7 7 5040        execute
                 r            7 5040 7        swap
                  /           7 720           divide
                   r2r        720 2 7         swap, 2, swap
                      |       1               modular exp: 720^2 mod 7
                       p                      print output

The factorial macro breaks for input 1, or something, but it turns out not to matter, and the output is correct.

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

Mathematica, 33 bytes

Print[Mod[(#-1)!^2,#]>0&@Input[]]

or

Print[Length@Divisors@Input[]==2]

Mathematica has a built-in PrimeQ as well, but I believe it uses a probabilistic test.

\$\endgroup\$
  • \$\begingroup\$ What is the measurable difference between having and not having "Print@" at the front of that expression? \$\endgroup\$ – Eric Towers Sep 13 '15 at 23:56
  • \$\begingroup\$ @EricTowers without it, it will only print when run inside a notebook, i.e. in a REPL environment. I wouldn't consider that a full program. If you invoke the code from the command line, you need the Print@ to actually get any output. \$\endgroup\$ – Martin Ender Sep 14 '15 at 6:46
  • \$\begingroup\$ According to the documentation, PrimeQ is a deterministic algorithm. I suspect the challenge text meant the other meaning (100% correct result). \$\endgroup\$ – DanaJ Sep 14 '15 at 12:00
  • \$\begingroup\$ You could save a byte with Echo. \$\endgroup\$ – Pavel Nov 28 '16 at 19:23
  • \$\begingroup\$ @Pavel unfortunately, that also prints >> to STDOUT. \$\endgroup\$ – Martin Ender Nov 28 '16 at 19:33
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\$
  • \$\begingroup\$ Nice! I imagine the state names could be golfed a bit more, though... \$\endgroup\$ – DLosc Oct 27 '15 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\$ – SuperJedi224 Oct 29 '15 at 1:29

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.