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>

  • Can I take inputs as negative numbers, where abs(input) would be the number I am testing? – Stan Strum Sep 6 '17 at 3:40
  • No, the input is a strictly positive integer. – Dennis Sep 6 '17 at 3:44
  • 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/… – Lyndon White Dec 12 '17 at 6:21
  • @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. – Dennis Dec 12 '17 at 12:51
  • Could a case be made for locking this challenge and posting a new, less restrictive one? – Shaggy Jun 25 at 12:59

272 Answers 272

hello, world!, 13

hello, world!
  • 78
    Did you, like, just create this language, just for this submission? ;) – ETHproductions Sep 11 '15 at 16:43
  • 37
    @ETHproductions Looks like the latest commit was 10 days ago. – Geobits Sep 11 '15 at 16:46
  • 37
    I was hoping to have the language in slightly better shape before linking to it anywhere, but this challenge was posted and I couldn't resist. – histocrat Sep 11 '15 at 20:40
  • 29
    I would almost say that hanging on an input of 1 is correct functionality. – iamnotmaynard Sep 14 '15 at 13:45
  • 18
    The best part about this is that the program isn't just a built-in, each character plays its own part in getting the correct result. – ETHproductions Sep 22 '16 at 19:59
up vote 151 down vote
+500

Hexagony, 29 bytes

.?'.).@@/'/.!.>+=(<.!)}($>(<%

The readable version of this code is:

   . ? ' .
  ) . @ @ /
 ' / . ! . >
+ = ( < . ! )
 } ( $ > ( <
  % . . . .
   . . . .

Explanation: It test if there is a number from 2 to n-1 who divides n.

Initialization:

Write n in one memory cell and n-1 in an other:

   . ? ' .
  . . . . .
 . . . . . .
+ = ( . . . .
 . . . . . .
  . . . . .
   . . . .

Special Case n=1:

Print a 0 and terminate

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . .
 . . . . . .
  . . . . .
   . . . .

The loop

Calculate n%a and decrease a. Terminate if a=1 or n%a=0.

   . . . .
  ) . . . /
 ' / . . . >
. . . . . . .
 } ( $ > ( <
  % . . . .
   . . . .

Case a=1:

Increase a 0 to an 1, print it and terminate. (The instruction pointer runs in NE direction and loops from the eastern corner to the south western corner. And the $ makes sure it ignores the next command)

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . )
 . . $ . . <
  . . . . .
   . . . .

Case a%n=0:

Print the 0 and terminate (The instruction pointer is running SW and loops to the top to the @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
  • 59
    Holy crap, that's one impressive first post. :) I'll put up the bounty right now (I'll award it in 7 days, to draw some more attention to your answer). Welcome to PPCG! – Martin Ender Sep 20 '15 at 15:17
  • 32
    Great answer! +1 for "The readable version of this code is: <...>" :-) – agtoever Sep 21 '15 at 7:05

Hexagony, 218 92 58 55 bytes

Notice: This answer has been solidly beaten with a side-length 4 solution by Etoplay.

)}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[

The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as Sp3000's Labyrinth answer. After starting out with a hexagon of size 10, I managed to compress it down to size 5. However, I was able to reuse some duplicate code and there are still quite a bunch of no-ops in the code, so size 4 might just be possible.

Explanation

To make sense of the code, we first need to unfold it. Hexagony pads any source code to the next centred hexagonal number with no-ops (.), which is 61. It then rearranges the code into a regular hexagon of the corresponding size:

     ) } ? } .
    = ( . . ] =
   } = ' . } . }
  ~ . / % * . . &
 . = & { . < . . .
  . . . = | > ( <
   . . } ! = . .
    . & @ \ [ .
     . . . . .

This is quite heavily golfed with crossing and overlapping execution paths and multiple instruction pointers (IPs). To explain how it works, let's first look at an ungolfed version where control flow doesn't go through the edges, only one IP is used and the execution paths are as simple as possible:

             . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
          . . . . . . . . . . @ . . . . .
         . . . . . . . . . . ! . . . . . .
        . . . . . . . . . . % . . . . . . .
       . . . . . . . . . . ' . . . . . . . .
      . . . . . . . . . . & . . . . . . . . .
     . . . . . . . . . . { . . . . . . . . . .
    . . . . . . . . . . * . . . . . . . . . . .
   . . . . . . . . . . = . . . . . . . . . . . .
  . . . . . . . . . . } . . . . . . . . . . . . .
 ) } ? } = & { < . . & . . . . . . . . . . . . . .
  . . . . . . . > ( < . . . . . . . . . . . . . .
   . . . . . . = . . } . . . . . . . . . . . . .
    . . . . . } . . . = . . . . . . . . . . . .
     . . . . | . . . . | . . . . . . . . . . .
      . . . . * . . . ) . . . . . . . . . . .
       . . . . = . . & . . . . . . . . . . .
        . . . . > } < . . . . . . . . . . .
         . . . . . . . . . . . . . . . . .
          . . . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
             . . . . . . . . . . . . .

Side note: the above code starts with executing the first line, which is full of no-ops. Then, when the IP hits the north east edge, it wraps to the left-most corner (the )), where the actual code begins.

Before we start, a word about Hexagony's memory layout. It's a bit like Brainfuck's tape on steroids. In fact, it's not a tape, but it's a hexagonal grid itself (an infinite one), where each edge has an integer value, which is initially 0 (and as opposed to standard Brainfuck, the values are signed arbitrary-precision integers). For this program, we'll be using four edges:

enter image description here

We'll compute the factorial on edge A, count down our input on edge C and store another copy of the input (for the modulo) on edge D. B is used as a temporary edge for computations.

The memory pointer (MP) starts out on edge A and points north (this is important for moving the MP around). Now here is the first bit of the code:

)}?}=&{

) increments edge A to 1 as the basis of the factorial. } makes the MP take a right-turn, i.e. move to edge C (pointing north-east). Here we read the input as an integer with ?. Then we take another right-turn to edge D with }. = reverses the MP, such that it points at the vertex shared with C. & copies the value from C (the input) into D - the value is copied from the left because the current value is non-positive (zero). Finally, we make the MP take a left-turn back to C with {.

Next, < is technically a branch, but we know that the current value is positive, so the IP will always turn right towards the >. A branch hit from the side acts as a mirror, such that the IP moves horizontally again, towards the (, which decrements the value in C.

The next branch, < is actually a branch now. This is how we loop from n-1 down to 1. While the current value in C is positive, the IP takes a right-turn (to execute the loop). Once we hit zero, it will turn left instead.

Let's look at the loop "body". The | are simple mirrors, the > and < are also used as mirrors again. That means the actual loop body boils down to

}=)&}=*}=

} moves the MP to edge B, = reverses its direction to face the vertex ABC. ) increments the value: this is only relevant for the first iteration, where the value of B is still zero: we want to ensure that it's positive, such that the next instruction & copies the right neighbour, i.e. A, i.e. the current value of the factorial computation, into B.

} then moves the MP to A, = reverses it again to face the common vertex. * multiplies both neighbours, i.e. edges B and C and stores the result in A. Finally, we have another }= to return to C, still facing the vertex ABC.

I hope you can see how this computes the factorial of n-1 in A.

So now we've done that, the loop counter in C is zero. We want to square the factorial and then take the modulo with the input. That's what this code does:

&}=*{&'%!@

Since C is zero, & copies the left neighbour, i.e. the factorial in A. }=* moves to B and stores the product of the two copies of the factorial (i.e. the square) in B. { moves back to C, but doesn't reverse the MP. We know that the current value is now positive, so & copies input from D into C. ' the MP backwards to the right, i.e. onto A. Remember, the square of the factorial is in B and the input is in C. So % computes (n-1)!^2 % n, exactly what we're looking for. ! prints the result as an integer (0 or 1) and @ terminates the program.


Okay, but that was the ungolfed version. What about the golfed version? You need to know two more things about Hexagony:

  1. The edges wrap around. If the IP hits an edge of the hexagon, it jumps to the opposite edge. This is ambiguous when the IP hits a corner straight on, so hitting a corner also acts as a branch: if the current value is positive, the IP jumps to the grid edge to its right, otherwise to the one to its left.
  2. There are actually 6 IPs. Each of them starts in a different corner, moving along the edge in the clockwise direction. Only one of them is active at a time, which means you can just ignore the other 5 IPs if you don't want them. You can switch to the next IP (in clockwise order) with ] and to the previous one with [. (You can also choose a specific one with #, but that's for another time.)

There are also a few new commands in it: \ and / are mirrors like |, and ~ multiplies the current value by -1.

So how does the ungolfed version translate to the golfed one? The linear set up code )}?}=&{ and the basic loop structure can be found here:

        ) } ? } .  ->
       . . . . . .
      . . . . . . .
     . . . . . . . .
->  . = & { . < . . .
     . . . . . > ( <
      . . . . . . .
       . . . . . .
        . . . . .

Now the loop body crosses the edges a few times, but most importantly, the actual computation is handed off to the previous IP (which starts at the left corner, moving north east):

        ) . . . .
       = . . . ] .
      } = . . } . .
     ~ . / . * . . .
    . . . . . . . . .
     . . . = . > ( <
      . . } . = . .
       . & . \ [ .
        . . . . .

After bouncing off the branch towards south east, the IP wraps around the edge to the two = in the top left corner (which, together, are a no-op), then bounces off the /. The ~ inverts the sign of the current value, which is important for subsequent iterations. The IP wraps around the same edge again and finally hits [ where control is handed over to the other IP.

This one now executes ~}=)&}=*} which undoes the negation and then just runs the ungolfed loop body (minus the =). Finally it hits ] which hands control back to the original IP. (Note that next time, we execute it this IP, it will start from where it left off, so it will first hit the corner. We need the current value to be negative in order for the IP to jump back to the north west edge instead of the south east one.)

Once the original IP resumes control, it bounces off the \, executes the remaining = and then hits > to feed into the next loop iteration.

Now the really crazy part: what happens when the loop terminates?

        ) . . . .
       . ( . . ] =
      . . ' . } . }
     . . . % * . . &
    . . . . . . . . .
     . . . = | . . <
      . . } ! . . .
       . & @ . . .
        . . . . .

The IP moves north east form the < and wraps around to the north east diagonal. So it ends up on the same execution path as the loop body (&}=*}]). Which is actually pretty cool, because that is exactly the code we want to execute at this point, at least if we add another =} (because }=} is equivalent to {). But how does this not actually enter the earlier loop again? Because ] changes to the next IP which is now the (so far unused) IP which starts in the top right corner, moving south west. From there, the IP continues along the edge, wraps to the top left corner, moves down the diagonal, bounces off the | and terminates at @ while executing the final bit of linear code:

=}&)('%!@

(The )( is a no-op of course - I had to add the ( because the ) was already there.)

Phew... what a mess...

  • Nice! How new is this? Also, you may wish to create an esolangs page whenever you get a stable release – mbomb007 Sep 12 '15 at 21:33
  • 18
    @mbomb007 I implemented the language two days ago (and designed it over two or three days before that). And yes, I'll definitely add an esolangs page, but I think the spec isn't 100% stable yet (there are still 3 unassigned commands for instance). Once I feel that it's more stable, I'll add it to both esolangs and our meta post. – Martin Ender Sep 12 '15 at 21:36
  • Under the expanded hex is it wraps to the left-most corner (the 1). What 1 are you talking about there? – mbomb007 Sep 13 '15 at 4:15
  • @mbomb007 fixed. The ) used to be a 1. – Martin Ender Sep 13 '15 at 6:54
  • 5
    +1 just for the level of detail in your explanation of how it works. If more languages came with an example that detailed more people could use them :D – jdarling Oct 22 '15 at 1:25

Pyth, 4 bytes

}QPQ

Prints True or False.

  • 10
    I know that this is old but now you can also do that like this: P_Q and save 1 byte. – drobilc Feb 19 '16 at 20:23
  • 10
    It's now possible with P_ – Blue Jul 22 '16 at 18:27
  • 1
    @drobilc You can cut the Q, as an EOF when the function is expecting an argument, it uses the input – Stan Strum Sep 11 '17 at 3:27

Retina, 16 bytes

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

Try it online!

Let's start with a classic: detecting primes with a regex. Input should be given in unary, using any repeated printable character. The test suite includes a conversion from decimal to unary for convenience.

A Retina program consisting of a single line treats that line as a regex and prints the number of matches found in the input, which will be 0 for composite numbers and 1 for primes.

The lookahead ensures that the input is not composite: backtracking will try every possible substring (of at least 2 characters) for (..+), the lookahead then attempts to match the rest of the input by repeating what was captured here. If this is possible, that means the input has a divisor greater than 1, but which is less than itself. If that is the case the negative lookahead causes the match to fail. For primes there is no such possibility, and the match continues.

The only issue is that this lookahead also accepts 1, so we rule that out by matching at least two characters with ...

  • That's actually an irregular expression, since the primes do not form a regular language. – PyRulez Jun 28 '17 at 7:10
  • @PyRulez Most real-world regex flavours are a lot more powerful than the theoretical concept of regular expressions. I improved the wording though. – Martin Ender Jun 28 '17 at 7:11
  • 1
    The most powerful "regex" engines out in the open right now have recognition power equal to that of a linear bounded automata. Standard issue regex, pattern recursion, unlimited lookhead, and unlimited lookbehind are all you need for context-sensitive parsing (though backreferences and such generally help with complicating efficient parsing), and some have them all. Don't even get me started on the engines that let you embed code into the regex. – eaglgenes101 Nov 10 '17 at 5:24

CJam, 4 bytes

qimp

CJam has a built-in operator for primality testing.

  • 16
    Alternatively: limp – Sp3000 Sep 11 '15 at 15:19
  • 40
    pimp my cjam. – flawr Sep 11 '15 at 18:04
  • 11
    pimp is objectively more pimp – MickLH Sep 12 '15 at 0:32
  • You can also do l~mp – Cows quack Sep 13 '15 at 8:46
  • 11
    @Cyoce, q reads a line of input, i parses it as an integer, and mp is the built-in. CJam has two groups of two-char built-ins: the "extended" ones begin e and the "mathematical"ones begin m – Peter Taylor Mar 20 '16 at 7:16

Help, WarDoq!, 1 byte

P

Outputs 1 if the input is prime, 0 otherwise.

HTML+CSS, 254+nmax*28 bytes

We can check primality using regular expressions. Mozilla has @document, which is defined as:

@document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# {
  <group-rule-body>
}

To filter elements via CSS based on the current URL. This is a single pass, so we have to do two steps:

  1. Get input from the user. This input must somehow be reflected in the current URL.
  2. Reply to the user in as little code as possible.

1. Getting Input

The shortest way I can figure to get input and transfer that to the URL is a GET form with checkboxes. For the regex, we just need some unique string to count appearances.

So we start with this (61 bytes):

<div id=q><p id=r>1<p id=s>0</div><form method=GET action=#q>

We got two unique <p>s to indicate whether the entered number is a prime (1) or not (0). We also define the form and it's action.

Followed by nmax checkboxes with the same name (nmax*28 bytes):

<input type=checkbox name=i>

Followed by the submit element (34 bytes):

<input name=d value=d type=submit>

2. Display Answer

We need the CSS (159 bytes) to select the <p> to display (1 or 0):

#q,#s,#q:target{display:none}#q:target{display:block}@-moz-document regexp(".*\\?((i=on&)?|(((i=on&)(i=on&)+?)\\4+))d=d#q$"){#s{display:block}#r{display:none}}

» Try it at codepen.io (firefox only)

  • 10
    +1: This is my all time favourite abuse of HTML, and the kind of stuff that makes me love codegolf. – cat Dec 29 '15 at 1:40
  • This is certainly interesting, but I'm not sure if it satisfies the rules of this challenge. In particular, I don't think it complies with Your algorithm [...] should, in theory, work for arbitrarily large integers. Couldn't you use a regex on the value of an input field as well? – Dennis Dec 29 '15 at 2:16
  • @Dennis Maybe. Probably even. But that wouldn't solve the problem you mentioned. I leave it here as a non-competing entry, because this is the most on-topic challenge for that. – mınxomaτ Dec 29 '15 at 2:20
  • Why not? If you have a number in unary in an input field, your code would no longer depend on the maximum number. – Dennis Dec 29 '15 at 2:22
  • 3
    Hm, I thought about this a bit more, and there's really no difference between having only x checkboxes and an interpreter that has only y-bit numbers. Disregard my previous comment. – Dennis Aug 6 '16 at 23:17
up vote 34 down vote
+1000

Hexagony, 28 bytes

Since Etoplay absolutely trounced me on this question, I felt that I had to outgolf his only other answer.

?\.">"!*+{&'=<\%(><.*.'(@>'/

Try it online!

I use Wilson's Theorem, like Martin did in his answer: Given n, I output (n-1!)² mod n

Here it the program unfolded:

   ? \ . "
  > " ! * +
 { & ' = < \
% ( > < . * .
 ' ( @ > ' /
  . . . . .
   . . . .

And here is the readable version:

Very readable

Explanation:

The program has three main steps: Initialisation, Factorial and Output.

Hexagony's memory model is an infinite hexagonal grid. I am using 5 memory locations, as shown in this diagram:

Memory

I will be referring to these locations (and the Integers stored in them) by their labels on that diagram.

Initialisation:

Initialisation

The instruction pointer (IP) starts at the top left corner, going East. The memory pointer (MP) starts at IN.

First, ? reads the number from input and stores it in IN. The IP stays on the blue path, reflected by \. The sequence "&( moves the MP back and to the left (to A), copies the value from IN to A and decrements it.

The IP then exits one side of the hexagon and re-enters the other side (onto the green path). It executes '+ which moves the MP to B and copies what was in A. < redirects the IP to West.

Factorial:

I compute the factorial in a specific way, so that squaring it is easy. I store n-1! in both B and C as follows.

Factorial

The instruction pointer starts on the blue path, heading East.

=' reverses the direction of the MP and moves it backwards to C. This is equivalent to {= but having the = where it is was helpful later.

&{ copies the value from A to C, then moves the MP back to A. The IP then follows the green path, doing nothing, before reaching the red path, hitting \ and going onto the orange path.

With (>, we decrement A and redirect the IP East. Here it hits a branch: <. For positive A, we continue along the orange path. Otherwise the IP gets directed North-East.

'* moves the MP to B and stores A * C in B. This is (n-1)*(n-2) where the initial input was n. The IP then enters back into the initial loop and continues decrementing and multiplying until A reaches 0. (computing n-1!)

N.B: On following loops, & stores the value from B in C, as C has a positive value stored in it now. This is crucial to computing factorial.

Output:

Output

When A reaches 0. The branch directs the IP along the blue path instead.

=* reverses the MP and stores the value of B * C in A. Then the IP exits the hexagon and re-enters on the green path; executing "%. This moves the MP to OUT and calculates A mod IN, or (n-1!)² mod n.

The following {" acts as a no-op, as they cancel each-other out. ! prints the final output and *+'( are executed before termination: @.

After execution, (with an input of 5) the memory looks like this:

Memory2

The beautiful images of the control flow were made using Timwi's Hexagony Coloror.

Thank you to Martin Ender for generating all of the images, as I couldn't do it on my PC.

  • What are you using for these memory diagrams? I've seen Esoteric IDE but I couldn't get it to run... – NieDzejkob Nov 14 '17 at 15:43
  • @NieDzejkob you're better off asking Martin in chat , since he made them for me anyway. – H.PWiz Nov 14 '17 at 16:08
  • @NieDzejkob Yeah, the memory diagram can be exported from the EsoIDE. chat.stackexchange.com/rooms/27364/… if you want to chat about this some more. – Martin Ender Nov 14 '17 at 18:13

Mornington Crescent, 2448 bytes

We're back in London!

Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Hammersmith
Take Circle Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take Circle Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Victoria
Take Circle Line to Temple
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Victoria
Take Circle Line to Aldgate
Take Circle Line to Victoria
Take Circle Line to Victoria
Take District Line to Upminster
Take District Line to Embankment
Take Circle Line to Embankment
Take Northern Line to Angel
Take Northern Line to Moorgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take District Line to Upney
Take District Line to Cannon Street
Take District Line to Acton Town
Take District Line to Acton Town
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Hammersmith
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Ruislip
Take Piccadilly Line to Ruislip
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Mornington Crescent

Timwi was so kind to implement the control flow stations Temple and Angel in Esoteric IDE as well as add input and integer parsing to the language specification.

This one is probably better golfed than the "Hello, World!", because this time I wrote a CJam script to help me find the shortest path between any two stations. If you want to use it (although I don't know why anyone would want to...), you can use the online interpreter. Paste this code:

"Mornington Crescent"
"Cannon Street"
]qN/{'[/0=,}$:Q;{Q{1$#!}=\;_oNo'[/1>{']/0="[]"\*}%}%:R;NoQ{R\f{f{\#)}:+}:*},N*

Here the first two lines are the stations you want to check. Also, paste the contents of this pastebin into the input window.

The output will show you which lines are available at the two stations, and then a list of all stations which connect the two, sorted by the length of the station names. It shows all of them, because sometimes it's better to use a longer name, either because it allows a shorter line, or because the station is special (like Bank or Temple) so that you want to avoid it. There are some edge cases where two stations aren't connected by any single other station (notably, the Metropolitan and District lines never cross), in which case you'll have to figure out something else. ;)

As for the actual MC code, it's based on the squared-factorial approach as many other answers because MC has multiplication, division and modulo. Also, I figured that a single loop would be convenient.

One issue is that the loops are do-while loops, and decrementing and incrementing is expensive, so I can't easily compute (n-1)! (for n > 0). Instead, I'm computing n! and then divide by n at the end. I'm sure there is a better solution for this.

When I started writing this, I figured that storing -1 in Hammersmith would be a good idea so I can decrement more cheaply, but in the end this may have cost more than it saved. If I find the patience to redo this, I might try just keeping a -1 around in Upminster instead so I can use Hammersmith for something more useful.

  • 10
    Is London turing complete? – Rohan Jhunjhunwala Jul 12 '16 at 1:38
  • 1
    @RohanJhunjhunwala probably – Martin Ender Jul 12 '16 at 6:47
  • Wow! I love seeing well thought out questions. I especially love seeing questions where you have to write a program to write a program. – Rohan Jhunjhunwala Jul 12 '16 at 12:41

Brachylog (V2), 1 byte

Try it online!

Brachylog (V1), 2 bytes

#p

This uses the built-in predicate #p - Prime, which constrains its input to be a prime number.

Brachylog is my attempt at making a Code Golf version of Prolog, that is a declarative code golf language that uses backtracking and unification.

Alternate solution with no built-in: 14 bytes

ybbrb'(e:?r%0)

Here is a breakdown of the code above:

y            The list [0, …, Input]
bbrb         The list [2, …, Input - 1]
'(           True if what's in the parentheses cannot be proven; else false
     e           Take an element from the list [2, …, Input - 1]
     :?r%0       The remainder of the division of the Input but that element is 0
)
  • 1
    You might want to edit the Brachylog 2 version of this into the post, too, now that the syntax is a byte shorter. – user62131 May 11 '17 at 16:10
  • 1
    @ais523 True, done. – Fatalize May 11 '17 at 16:15
  • Does the Brachylog 2 answer postdate the challenge? – Scott Milner May 12 '17 at 16:30
  • 1
    @ScottMilner Yes, but this is explicitely allowed in this challenge: "Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge" – Fatalize May 12 '17 at 16:34

Haskell, 49 bytes

Using xnor's Corollary to Wilson's Theorem:

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
  • Wouldn't it be shorter to do main=interact$\n-> ...? – John Dvorak Sep 20 '15 at 6:57
  • 2
    Counterintuitively, no! Consider that you'd need interact...read in there somewhere, which makes it a lot longer than just readLn. Often do notation can be more concise than you might expect, especially when the alternative is a lambda. – Lynn Sep 20 '15 at 20:34

Labyrinth, 29 bytes

1
?
:
}  +{%!@
(:'(
 } {
 :**

Reads an integer from STDIN and outputs ((n-1)!)^2 mod n. Wilson's theorem is pretty useful for this challenge.

The program starts at the top-left corner, beginning with 1 which multiplies the top of the stack by 10 and adds 1. This is Labyrinth's way of building large numbers, but since Labyrinth's stacks are filled with zeroes, the end effect is as though we just pushed a 1.

? then reads n from STDIN and : duplicates it. } shifts n to the auxiliary stack, to be used at the end for the modulo. ( then decrements n, and we are ready to begin calculating the squared factorial.

Our second : (duplicate) is at a junction, and here Labyrinth's control flow features come into play. At a junction after an instruction is executed, if the top of the stack is positive we turn right, for negative we turn left and for zero we go straight ahead. If you try to turn but hit a wall, Labyrinth makes you turn in the other direction instead.

For n = 1, since the top of the stack is n decremented, or 0, we go straight ahead. We then hit a no-op ' followed by another decrement ( which puts us at -1. This is negative, so we turn left, executing + plus (-1 + 0 = -1), { to shift n back from the auxiliary stack to the main and % modulo (-1 % 1 = 0). Then we output with ! and terminate with @.

For n > 1, at the second : we turn right. We then shift } our copied loop counter to the auxiliary stack, duplicate : and multiply twice **, before shifting the counter back { and decrementing (. If we're still positive we try to turn right but can't, so Labyrinth makes us turn left instead, continuing the loop. Otherwise, the top of the stack is our loop counter which has been reduced to 0, which we + add to our calculated ((n-1)!)^2. Finally, we shift n back with { then modulo %, output ! and terminate @.

I said that ' is a no-op, but it can also be used for debugging. Run with the -d flag to see the state of the stack every time the ' is passed over!

  • 2
    Squaring the factorial is a really cool trick :) – Lynn Sep 11 '15 at 18:06
  • @Mauris Thanks! I need to give credit where it is due though - I first saw the trick used by xnor here – Sp3000 Sep 11 '15 at 18:16
  • 4
    Yay, the first Labyrinth answer not written by me! :) – Martin Ender Sep 11 '15 at 18:48

Bash + GNU utilities, 16

  • 4 bytes saved thanks to @Dennis

  • 2 bytes saved thanks to @Lekensteyn

factor|awk NF==2

Input is one line taken from STDIN. Output is empty string for falsey and non-empty string for truthy. E.g.:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
  • 2
    Cool, learned about another coreutil. Your can strip two characters by counting the number of fields: factor|awk NF==2 – Lekensteyn Sep 18 '15 at 11:03
  • @Lekensteyn - thanks - for some reason I missed your comment before :) – Digital Trauma May 24 '16 at 19:30
  • I was going to post something somewhat similar, only longer and without AWK. Nicely done. – David Conrad Feb 6 '17 at 19:16

Java, 126 121 bytes

I guess we need a Java answer for the scoreboard... so here's a simple trial division loop:

class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}

As usual for Java, the "full program" requirement makes this much larger than it would be if it were a function, due mostly to the main signature.

In expanded form:

class P{
    public static void main(String[]a){
        int i=2,n=Short.valueOf(a[0]);
        for(;i<n;)
            n=n%i++<1?0:n;
        System.out.print(n>1);
    }
}

Edit: Fixed and regolfed by Peter in comments. Thanks!

  • Buggy: it reports that 1 is prime. Otherwise there'd be a 4-char saving by removing p and saying for(;i<n;)n=n%i++<1?0:n;System.out.print(n>0); – Peter Taylor Sep 11 '15 at 20:32
  • 2
    OTOH class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}} works – Peter Taylor Sep 11 '15 at 20:53
  • 6
    changing line 3 to 'long i=2,n=Long.valueOf(a[0]);` results in no change in length but a wider range of valid inputs. – James K Polk Sep 17 '15 at 21:02
  • 4
    Instead of .valueOf you can use new, as in new Short(a[0]), or new Long(a[0]), which is a bit shorter. – ECS Jan 25 '16 at 8:55
  • 1
    You can save 4 bytes by using an interface and dropping the public modifier. – RamenChef Dec 13 '17 at 19:28

Brain-Flak, 112 108 bytes

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

Try it online!

How it works

Initially, the first stack will contain a positive integer n, the second stack will be empty.

We start by decrementing n as follows.

(
  {}      Pop n.
  [()]    Yield -1.
)       Push n - 1.

n = 1

If n = 1 is zero, the while loop

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

is skipped entirely. Finally, the remaining code is executed.

<>    Switch to the second stack (empty).
{}    Pop one of the infinite zeroes at the bottom.
{<>}  Switch stacks while the top on the active stack is non-zero. Does nothing.
(
  []    Get the length of the active stack (0).
  {}    Pop another zero.
)     Push 0 + 0 = 0.

n > 1

If n - 1 is non-zero, we enter the loop that n = 1 skips. It isn't a "real" loop; the code is only executed once. It achieves the following.

{                   While the top of the active stack is non-zero:
  (
    (
      ({})                Pop and push n - 1.
      ()                  Yield 1.
    )                   Push n - 1 + 1 = n.
    <>                  Switch to the second stack. Yields 0.
  )                   Push n + 0 = n.
                      We now have n and k = n - 1 on the first stack, and n on
                      the second one. The setup stage is complete and we start
                      employing trial division to determine n's primality.
  {                   While the top of the second stack is non-zero:
    {}                  Pop n (first run) or the last modulus (subsequent runs),
                        leaving the second stack empty.
    <>                  Switch to the first stack.
    (
      (
        {}                  Pop n from the first stack.
        <
          (
            (
              {}              Pop k (initially n - 1) from the first stack.
              [()]            Yield -1.
            )               Push k - 1 to the first stack.
            ()              Yield 1.
            <>              Switch to the second stack.
          )               Push k - 1 + 1 = k on the second stack.
        >               Yield 0.
      )               Push n + 0 = n on the second stack.
      <>              Switch to the first stack.
    )               Push n on the first stack.
    <>              Switch to the second stack, which contains n and k.
                    The first stack contains n and k - 1, so it is ready for
                    the next iteration.
    {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}  Compute and push n % k.
  }               Stop if n % k = 0.
}               Ditto.

n % k is computed using the 42-byte modulus algorithm from my divisibility test answer.

Finally, we interpret the results to determine n's primality.

<>    Switch to the first stack, which contains n and k - 1, where k is the
      largest integer that is smaller than n and divides n evenly.
      If (and only if) n > 1 is prime, k = 1 and (thus) k - 1 = 0.
{     While the top of the first stack is non-zero:
  {}    Pop it.
}     This pops n if n is prime, n and k - 1 if n is composite.
(
  []    Yield the height h of the stack. h = 1 iff n is prime).
  {}    Pop 0.
)     Push h + 0 = h.
  • 2
    You don't need to pop the last 0 on the stack, since the truthy 1 on top is enough; you can save two bytes that way by removing the last {}. – Steven H. Oct 5 '16 at 23:18
  • Hm, I'm torn. On one hand, the question says that output should consist solely of a truthy or falsy value and 1 0 is two values. On the other hand, we'd accept arrays as long as the language considers them truthy or falsy and multiple stack items is the closest thing Brain-Flak has to arrays. Might be worth taking this to meta. – Dennis Oct 6 '16 at 0:39
  • I've verified with the creator of Brain-Flak that 1 0 is truthy. chat.stackexchange.com/transcript/message/32746241#32746241 – Steven H. Oct 6 '16 at 1:01
  • 3
    Relevant meta discussion: Truthiness in Brain-Flak and similar stack-based languages – Dennis Oct 6 '16 at 3:59

R, 37 29 bytes

n=scan();cat(sum(!n%%1:n)==2)

Uses trial division. scan() reads an integer from STDIN and cat() writes to STDOUT.

We generate a vector of length n consisting of the integers 1 to n modulo n. We test whether each is 0 by negating (!), which returns a logical value that's true when the number is 0 and false when it's greater than 0. The sum of a logical vector is the number of true elements, and for prime numbers we expect the only nonzero moduli to be 1 and n, thus we expect the sum to be 2.

Saved 8 bytes thanks to flodel!

  • With f=function(x)sum(!x%%1:x)==2 you can do it in 28 bytes. – Mutador Dec 21 '15 at 16:35
  • 2
    @AndréMuta For this challenge, all submissions must be full programs rather than just functions. Thanks for the suggestion though. – Alex A. Dec 21 '15 at 20:13

TI-BASIC, 12 bytes

2=sum(not(fPart(Ans/randIntNoRep(1,Ans

Pretty straightforward. randIntNoRep( gives a random permutation of all integers from 1 to Ans.

This bends the rules a little; because lists in TI-BASIC are limited to 999 elements I interpreted

assume that the input can be stored in your data type

as meaning that all datatypes can be assumed to accommodate the input. OP agrees with this interpretation.

A 17-byte solution which actually works up to 10^12 or so:

2=Σ(not(fPart(Ans/A)),A,1,Ans
  • @toothbrush TI-BASIC is a tokenized language, so every token here is one byte, except for randIntNoRep( which is two. – lirtosiast Sep 13 '15 at 19:28
  • +1 Ah, I've never seen TL-BASIC before. Thanks for letting me know – Toothbrush Sep 13 '15 at 19:29
  • 1
    Although, it is a bit unfair, isn't it...? I should write a golfing language that requires only 1-4 bytes (the question ID), and then the parameters. It will pick the top answer in a language it understands, execute it (passing any parameters), and return the result... I wonder if that's breaking the rules? :-) – Toothbrush Sep 13 '15 at 19:30
  • @toothbrush In TI-BASIC's defense: to the interpreter, it's no more unfair than Pyth and CJam's one-character commands, and TI-BASIC is more readable. – lirtosiast Sep 13 '15 at 19:34
  • 1
    True. I dislike those kinds of languages, since solutions in almost every other language are longer... although I recently beat CJam with VB6! :-] – Toothbrush Sep 13 '15 at 19:35

PARI/GP, 21 bytes

print(isprime(input))

Works for ridiculously big inputs, because this kind of thing is what PARI/GP is made for.

  • 6
    isprime does an APR-CL primality proof, so does slow down quite a bit as inputs get very large. ispseudoprime(input) does an AES BPSW probable prime test, which will be much faster for over 100 digits. Still no known counterexamples after 35 years. Version 2.1 and earlier of Pari, from pre-2002, uses a different method that can easily give false results, but nobody should be using that. – DanaJ Sep 11 '15 at 18:30

TI-BASIC, 24 bytes

Note that TI-Basic programs use a token system, so counting characters does not return the actual byte value of the program.

Upvote Thomas Kwa's answer, it is superior.

:Prompt N
:2
:While N≠1 and fPart(N/Ans
:Ans+1
:End
:N=Ans

Sample:

N=?1009
                         1
N=?17
                         1
N=?1008
                         0
N=?16
                         0

Now returns 0 if not a prime, or 1 if it is.

  • 3
    Isn't the square root just an optimisation that you don't actually need for the program to be correct? – Martin Ender Sep 11 '15 at 15:24
  • Why would you need to divide by two? – Geobits Sep 11 '15 at 15:29
  • I always love TI-BASIC answers. – Grant Miller Feb 27 at 1:05

Stack Cats, 62 + 4 = 66 bytes

*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Needs to be run with the -ln command-line flags (hence +4 bytes). Prints 0 for composite numbers and 1 for primes.

Try it online!

I think this is the first non-trivial Stack Cats program.

Explanation

A quick Stack Cats introduction:

  • Stack Cats operates on an infinite tape of stacks, with a tape head pointing at a current stack. Every stack is initially filled with an infinite amount of zeros. I will generally ignore these zeros in my wording, so when I say "the bottom of stack" I mean the lowest non-zero value and if I say "the stack is empty" I mean there's only zeros on it.
  • Before the program starts, a -1 is pushed onto the initial stack, and then the entire input is pushed on top of that. In this case, due to the -n flag, the input is read as a decimal integer.
  • At the end of the program, the current stack is used for output. If there's a -1 at the bottom, it will be ignored. Again, due to the -n flag, the values from the stack are simply printed as linefeed-separated decimal integers.
  • Stack Cats is a reversible program language: every piece of code can be undone (without Stack Cats keeping track of an explicit history). More specifically, to reverse any piece of code, you simply mirror it, e.g. <<(\-_) becomes (_-/)>>. This design goal places fairly severe restrictions on what kinds of operators and control flow constructs exist in the language, and what sorts of functions you can compute on the global memory state.
  • To top it all off, every Stack Cats program has to be self-symmetric. You might notice that this is not the case for the above source code. This is what the -l flag is for: it implicitly mirrors the code to the left, using the first character for the centre. Hence the actual program is:

    [<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]
    

Programming effectively with the entire code is highly non-trivial and unintuitive and haven't really figured out yet how a human can possibly do it. We've brute forced such program for simpler tasks, but wouldn't have been able to get anywhere near that by hand. Luckily, we've found a basic pattern which allows you to ignore one half of the program. While this is certainly suboptimal, it's currently the only known way to program effectively in Stack Cats.

So in this answer, the template of said pattern is this (there's some variability in how it's executed):

[<(...)*(...)>]

When the program starts, the stack tape looks like this (for input 4, say):

     4    
... -1 ...
     0
     ^

The [ moves the top of the stack to the left (and the tape head along) - we call this "pushing". And the < moves the tape head alone. So after the first two commands, we've got this situation:

...   4 -1 ...
    0 0  0
    ^

Now the (...) is a loop which can be used quite easily as a conditional: the loop is entered and left only when the top of the current stack is positive. Since, it's currently zero, we skip the entire first half of the program. Now the centre command is *. This is simply XOR 1, i.e. it toggles the least significant bit of the top of the stack, and in this case turns the 0 into a 1:

... 1 4 -1 ...
    0 0  0
    ^

Now we encounter the mirror image of the (...). This time the top of the stack is positive and we do enter the code. Before we look into what goes on inside the parentheses, let me explain how we'll wrap up at the end: we want to ensure that at the end of this block, we have the tape head on a positive value again (so that the loop terminates after a single iteration and is used simply as a linear conditional), that the stack to the right holds the output and that the stack right of that holds a -1. If that's the case, we do leave the loop, > moves onto the output value and ] pushes it onto the -1 so we have a clean stack for output.

That's that. Now inside the parentheses we can do whatever we want to check the primality as long as we ensure that we set things up as described in the previous paragraph at the end (which can easily done with some pushing and tape head moving). I first tried solving the problem with Wilson's theorem but ended up well over 100 bytes, because the squared factorial computation is actually quite expensive in Stack Cats (at least I haven't found a short way). So I went with trial division instead and that indeed turned out much simpler. Let's look at the first linear bit:

>:^]

You've already seen two of those commands. In addition, : swaps the top two values of the current stack and ^ XORs the second value into the top value. This makes :^ a common pattern to duplicate a value on an empty stack (we pull a zero on top of the value and then turn the zero into 0 XOR x = x). So after this, section our tape looks like this:

         4    
... 1 4 -1 ...
    0 0  0
         ^

The trial division algorithm I've implemented doesn't work for input 1, so we should skip the code in that case. We can easily map 1 to 0 and everything else to positive values with *, so here's how we do that:

*(*...)

That is we turn 1 into 0, skip a big part of the code if we get indeed 0, but inside we immediately undo the * so that we get our input value back. We just need to make sure again that we end on a positive value at the end of the parentheses so that they don't start looping. Inside the conditional, we move one stack right with the > and then start the main trial division loop:

{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}

Braces (as opposed to parentheses) define a different kind of loop: it's a do-while loop, meaning it always runs for at least one iteration. The other difference is the termination condition: when entering the loop Stack Cat remembers the top value of the current stack (0 in our case). The loop will then run until this same value is seen again at the end of an iteration. This is convenient for us: in each iteration we simply compute the remainder of the next potential divisor and move it onto this stack we're starting the loop on. When we find a divisor, the remainder is 0 and the loop stops. We will try divisors starting at n-1 and then decrement them down to 1. That means a) we know this will terminate when we reach 1 at the latest and b) we can then determine whether the number is prime or not by inspecting the last divisor we tried (if it's 1, it's a prime, otherwise it isn't).

Let's get to it. There's a short linear section at the beginning:

<-!<:^>[:

You know what most of those things do by now. The new commands are - and !. Stack Cats does not have increment or decrement operators. However it has - (negation, i.e. multiply by -1) and ! (bitwise NOT, i.e. multiply by -1 and decrement). These can be combined into either an increment, !-, or decrement -!. So we decrement the copy of n on top of the -1, then make another copy of n on the stack to the left, then fetch the new trial divisor and put it beneath n. So on the first iteration, we get this:

      4       
      3       
... 1 4 -1 ...
    0 0  0
      ^

On further iterations, the 3 will replaced with the next test divisor and so on (whereas the two copies of n will always be the same value at this point).

((-<)<(<!-)>>-_)

This is the modulo computation. Since loops terminate on positive values, the idea is to start from -n and repeatedly add the trial divisor d to it until we get a positive value. Once we do, we subtract the result from d and this gives us the remainder. The tricky bit here is that we can't just have put a -n on top of the stack and start a loop that adds d: if the top of the stack is negative, the loop won't be entered. Such are the limitations of a reversible programming language.

So to circumvent this issue, we do start with n on top of the stack, but negate it only on the first iteration. Again, that sounds simpler than it turns out to be...

(-<)

When the top of the stack is positive (i.e. only on the first iteration), we negate it with -. However, we can't just do (-) because then we wouldn't be leaving the loop until - was applied twice. So we move one cell left with < because we know there's a positive value there (the 1). Okay, so now we've reliably negated n on the first iteration. But we have a new problem: the tape head is now in a different position on the first iteration than in every other one. We need to consolidate this before we move on. The next < moves the tape head left. The situation on the first iteration:

        -4       
         3       
...   1  4 -1 ...
    0 0  0  0
    ^

And on the second iteration (remember we've added d once into -n now):

      -1       
       3       
... 1  4 -1 ...
    0  0  0
    ^

The next conditional merges these paths again:

(<!-)

On the first iteration the tape head points at a zero, so this is skipped entirely. On further iterations, the tape head points at a one though, so we do execute this, move to the left and increment the cell there. Since we know the cell starts from zero, it will now always be positive so we can leave the loop. This ensures we always end up two stack left of the main stack and can now move back with >>. Then at the end of the modulo loop we do -_. You already know -. _ is to subtraction what ^ is to XOR: if the top of the stack is a and the value underneath is b it replaces a with b-a. Since we first negated a though, -_ replaces a with b+a, thereby adding d into our running total.

After the loop ends (we've reached a positive) value, the tape looks like this:

        2       
        3       
... 1 1 4 -1 ...
    0 0 0  0
        ^

The left-most value could be any positive number. In fact, it's the number of iterations minus one. There's another short linear bit now:

_<<]>:]<]]

Like I said earlier we need to subtract the result from d to obtain the actual remainder (3-2 = 1 = 4 % 3), so we just do _ once more. Next, we need to clean up the stack that we've been incrementing on the left: when we try the next divisor, it needs to be zero again, for the first iteration to work. So we move there and push that positive value onto the other helper stack with <<] and then move back onto our operational stack with another >. We pull up d with : and push it back onto the -1 with ] and then we move the remainder onto our conditional stack with <]]. That's the end of the trial division loop: this continues until we get a zero remainder, in which case the stack to the left contains n's greatest divisor (other than n).

After the loop ends, there's just *< before we join paths with the input 1 again. The * simply turns the zero into a 1, which we'll need in a bit, and then we move to the divisor with < (so that we're on the same stack as for input 1).

At this point it helps to compare three different kinds of inputs. First, the special case n = 1 where we haven't done any of that trial division stuff:

         0    
... 1 1 -1 ...
    0 0  0
         ^

Then, our previous example n = 4, a composite number:

    2           
    1    2 1    
... 1 4 -1 1 ...
    0 0  0 0
         ^

And finally, n = 3, a prime number:

    3           
    1    1 1    
... 1 3 -1 1 ...
    0 0  0 0
         ^

So for prime numbers, we have a 1 on this stack, and for composite numbers we either have a 0 or a positive number greater than 2. We turn this situation into the 0 or 1 we need with the following final piece of code:

]*(:)*=<*

] just pushes this value to the right. Then * is used to simplify the conditional situation greatly: by toggling the least significant bit, we turn 1 (prime) into 0, 0 (composite) into the positive value 1, and all other positive values will still remain positive. Now we just need to distinguish between 0 and positive. That's where we use another (:). If the top of the stack is 0 (and the input was a prime), this is simply skipped. But if the top of the stack is positive (and the input was a composite number) this swaps it with the 1, so that we now have 0 for composite and 1 for primes - only two distinct values. Of course, they are the opposite of what we want to output, but that is easily fixed with another *.

Now all that's left is to restore the pattern of stacks expected by our surrounding framework: tape head on a positive value, result on top of the stack to the right, and a single -1 on the stack right of that. This is what =<* is for. = swaps the tops of the two adjacent stacks, thereby moving the -1 to the right of the result, e.g. for input 4 again:

    2     0       
    1     3       
... 1 4   1 -1 ...
    0 0 0 0  0
          ^

Then we just move left with < and turn that zero into a one with *. And that's that.

If you want to dig deeper into how the program works, you can make use of the debug options. Either add the -d flag and insert " wherever you want to see the current memory state, e.g. like this, or use the -D flag to get a complete trace of the entire program. Alternatively, you can use Timwi's EsotericIDE which includes a Stack Cats interpreter with a step-by-step debugger.

  • 3
    >:^] should be the official Stack Cats logo – Alex A. Jun 24 '16 at 23:28

Haskell, 54 bytes

import Data.Numbers.Primes
main=readLn>>=print.isPrime

Nothing much to explain.

  • 1
    The same score can be achieved (although very inefficiently) without external libraries, using Wilson's theorem: main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1 – Lynn Sep 11 '15 at 17:31
  • 9
    We can even do shorter: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0 is 49 bytes. – Lynn Sep 11 '15 at 18:06
  • 4
    @Mauris: Nice. Please post it as a separate answer. – nimi Sep 11 '15 at 21:16

Ruby, 15 + 8 = 23 bytes

p$_.to_i.prime?

Sample run:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
  • Heheh, I knew there would be a builtin in Ruby somewhere, but I couldn't be bothered to look for it, so I answered in C. +1. – Level River St Sep 11 '15 at 15:01
  • @steveverrill, I knew it because was a big help for Project Euler. – manatwork Sep 11 '15 at 15:03

JavaScript, 39 36 bytes

Saved 3 bytes thanks to ETHproductions:

for(i=n=prompt();n%--i;);alert(1==i)

Displays true for a prime, false otherwise.

The for loop tests every number i from n-1 until i is a divisor. If the first divisor found is 1 then it's a prime number.


Previous solution (39 bytes):

for(i=n=prompt();n%--i&&i;);alert(1==i)

How was left an unneeded test:

for(i=2,n=prompt();n%i>0&&i*i<n;i++);alert(n%i>0) //49: Simple implementation: loop from 2 to sqrt(n) to test the modulo.
for(i=2,n=prompt();n%i>0&&i<n;i++);alert(n==i)    //46: Replace i*i<n by i<n (loop from 2 to n) and replace n%i>0 by n==i
for(i=2,n=prompt();n%i&&i<n;i++);alert(n==i)      //44: Replace n%i>0 by n%i
for(i=2,n=prompt();n%i&&i++<n;);alert(n==i)       //43: Shorten loop increment
for(i=n=prompt();n%--i&&i>0;);alert(1==i)         //41: Loop from n to 1. Better variable initialization.
for(i=n=prompt();n%--i&&i;);alert(1==i)           //39: \o/ Replace i>0 by i

I only posted the 39 bytes solution because the best JavaScript answer was already 40 bytes.

  • 2
    Welcome to Programming Puzzles & Code Golf! – Dennis Aug 27 '16 at 0:48
  • 2
    Great answer! The &&i doesn't actually do anything in this program, so you can remove it. – ETHproductions Sep 24 '16 at 1:48
  • should add n>1 to the final condition though, if You don´t want 1 to be prime. – Titus Oct 17 '16 at 13:08
  • 1
    @Titus If the input is 1 the for loop will do n%--i once : 1%0 returns NaN and stops the loop. When alert is called i is already equal to 0 so 1==i returns false. – Hedi Oct 17 '16 at 20:21
  • 2
    i<2 (and some text) – Scheintod Mar 16 at 8:26

Snails, 122

Input should be given in unary. The digits may be any mix of characters except newlines.

^
..~|!(.2+~).!~!{{t.l=.r=.}+!{t.!.!~!{{r!~u~`+(d!~!.r~)+d~,.r.=.(l!~u~)+(d!~l~)+d~,.l.},l=(.!.)(r!~u~)+(d!~!.r~)+d~,.r.!.

In this 2D pattern matching language, the program state consists solely of the current grid location, the set of cells which have been matched, and the position in the pattern code. It's also illegal to travel onto a matched square. It's tricky, but possible to store and retrieve information. The restriction against traveling onto a matched cell can be overcome by backtracking, teleporting (t) and assertions (=, !) which leave the grid unmodified after completing.

Factorization of 25

The factorization for an odd composite number begins by marking out some set of mutually non-adjacent cells (blue in diagram). Then, from each yellow cell, the program verifies that there are an equal number of non-blue cells on either side of the adjacent blue one by shuttling back and forth between the two sides. The diagram shows this pattern for one of the four yellow cells which must be checked.

Annotated code:

^                         Match only at the first character
..~ |                     Special case to return true for n=2
!(.2 + ~)                 Fail for even numbers
. !~                      Match 1st character and fail for n=1
!{                        If the bracketed pattern matches, it's composite.
  (t. l=. r=. =(.,~) )+   Teleport to 1 or more chars and match them (blue in graphic)
                          Only teleport to ones that have an unmatched char on each side.
                          The =(.,~) is removed in the golfed code. It forces the
                          teleports to proceed from left to right, reducing the
                          time from factorial to exponential.
  !{                      If bracketed pattern matches, factorization has failed.
    t . !. !~             Teleport to a square to the left of a blue square (yellow in diagram)
    !{                    Bracketed pattern verifies equal number of spaces to
                          the left or right of a blue square.
      {              
        (r!~ u~)+         Up...
        (d!~!. r~)+       Right...
        d~,               Down...
        . r . =.          Move 1 to the right, and check that we are not on the edge;
                          otherwise d~, can fall off next iteration and create and infinite loop
        (l!~ u~)+         Up...
        (d!~ l~)+         Left...
        d ~,              Down...
        . l .             Left 1
      } ,                 Repeat 0 or more times
      l  =(. !.)          Check for exactly 1 unused char to the left
      (r!~ u~)+           Up...
      (d!~!. r~)+         Right...
      d ~,                Down...
      . r . !.
    }
  }
}

Python 3, 59 bytes

Now uses input() instead of command line arguments. Thanks to @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
  • Take input using input() would be much shorter – Beta Decay Sep 11 '15 at 17:02
  • Thanks, I've already written with using of input(), but I forgot to refresh my answer. Thanks again! – uno20001 Sep 11 '15 at 17:11
  • 4
    52 bytes: n=m=int(input()), print(all(n%m for m in range(2,n))) – jozzas Sep 16 '15 at 5:38
  • 1
    Are you serious. Spend 25 extra characters for a lame quadratic speedup? Here we hate bytes. We spend every hour,minute, and second of our lives getting rid of the nineteenth byte. (Just kidding. But we don't do time optimizations that increase program length.) – CalculatorFeline Mar 20 '16 at 4:15
  • 1
    Use n%i<1 instead. – Erik the Outgolfer Oct 17 '16 at 15:52

C, 67 bytes

i,n;main(p){for(scanf("%d",&i),n=i;--i;p=p*i*i%n);putchar(48+p%n);}

Prints !1 (a falsey value, by Peter Taylor's definition) 0 if (n-1)!^2 == 0 (mod n), and 1 otherwise.

EDIT: After some discussion in chat, puts("!1"+p%n) seems to be considered a bit cheaty, so I've replaced it. The result is one byte longer.

EDIT: Fixed for big inputs.

Shorter solutions

56 bytes: As recommended in the comments by pawel.boczarski, I could take input in unary by reading the number of command line arguments:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);putchar(48+p%n);}

invoking the program like

$ ./a.out 1 1 1 1 1
1                        <-- as 5 is prime

51 bytes: If you allow "output" by means of return codes:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
  • Your solution could be made shorter using unary representation (number of commandline arguments), as in my solution posted. You could shave off some bytes on scanf call. – pawel.boczarski Sep 12 '15 at 12:43
  • puts("!1"+p%n) How could you ever do a+b for char* values? – Erik the Outgolfer Jul 17 '16 at 15:11
  • If the string "!1" starts at address a, then at a+1 you’ll find the string "1". – Lynn Jul 17 '16 at 16:40
  • @Lynn Oh, I thought it was for concatenation (yeah, better leave that to strcat(const char*,const char*).) – Erik the Outgolfer Jul 17 '16 at 21:28
  • Could you change p=p*i*i%n to p*=i*i%n – Albert Renshaw Jan 24 '17 at 22:29

APL, 40 13 bytes

2=+/0=x|⍨⍳x←⎕

Trial division with the same algorithm as my R answer. We assign x to the input from STDIN () and get the remainder for x divided by each integer from 1 to x. Each remainder is compared against 0, which gives us a vector of ones and zeros indicating which integers divide x. This is summed using +/ to get the number of divisors. If this number is exactly 2, this means the only divisors are 1 and x, and thus x is prime.

Python 2, 44

P=n=1
exec"P*=n*n;n+=1;"*~-input()
print P%n

Like Sp3000's Python answer, but avoids storing the input by counting the variable n up from 1 to the input value.

C++ template metaprogramming. 166 131 119 bytes.

Code compiles if the constant is a prime, and does not compile if composite or 1.

template<int a,int b=a>struct t{enum{x=t<a,~-b>::x+!(a%b)};};
template<int b>struct t<b,0>{enum{x};};
int _[t<1>::x==2];

(all newlines, except final one, are eliminated in "real" version).

I figure "failure to compile" is a falsey return value for a metaprogramming language. Note that it does not link (so if you feed it a prime, you'll get linking errors) as a full C++ program.

The value to test is the integer on the last "line".

live example.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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