Is this number a prime?

Question

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 code-golf 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>

Answer 1

Regex (.NET), 604 517 499 469 455 bytes

^((?=[6-9](?<1>){6}|)(?=[3-59](?<1>){3}|)(?=[258](?<1>){2}|)(?=[147](?<1>)|).)+$(?<!(?=(?<-1>.)+(?(1)^))\11(?=((?<=(?=(?=((?<-2>)(?=.*$((?<-2>\2)(?<3>)|){9}).)+(?(2)^))(?>(?<-1>)(.)(?<=((?<5-1>\1)|){9}^.*))*(?<2>.(?<=((?<5>)(?<-1>\1)|){9}((?<-1>\1){10}|())((?<2-1>)(?<-3>\3)|){9}(?<-9>(?<-1>))?(?<1>){10}(?<-3>)(?<-1>)(?<5>^.*)))+$(?!\9)(?(3)^)(?<=(?<-5>(?=(?<1>(?=.*$\5)|.)).)*){10}(\12)?()|){9}^.*).)*)(?<-13>){3}^(?<-14>(?(14)|((?<2>(.)?))){10})+.*|^1)

Try it online!
Try it online! - primes matched in unary, for comparison

Takes its input in decimal, which must not have any leading zeros. Output is in the form of "match" (prime) or "no match" (non-prime).

Processing numbers in decimal with a regex has been a very under-explored territory. Previously, the most complicated tasks that had ever been done were:

• Match numbers divisible by 7
• Match correct statements of addition
  • non-negative integers
  • signed numbers with optional decimal point

Matching prime numbers with a regex has been done in unary, but had never before been done in decimal.

The challenges faced here are:

• All the computation of a regex must be done inside the space of the input, and its "variables" (capture groups) can only either be empty or contain substrings from the input.
• The number of times a loop may iterate cannot exceed a polynomial function of the length of the input. (This limit only applies loops of continuous calculation, in which the result of each iteration must be carried on to the next. Searching for a value that fits a property can use backtracking, whose number of "iterations" can go as high as an exponential function of the length of the input, and this regex exploits that for the divisor search.)
• In most regex flavors, there's no mutable data type analogous to an array. In .NET however, Balanced Groups provide what is essentially a stack data type; this can (cumbersomely) be used to emulate an array. The only way to iterate through such a stack is to destroy it, though, so every time this is done, it must be copied to another stack, in reverse order. Thus, it must be copied in reverse a second time to be reused.

I had already written a .NET regex to match primes in decimal a couple weeks before, but it must be given a hard-coded maximum bound. It's 192 bytes in length (and isn't shortened by reducing its limit from \$999\$ to \$255\$, but is shortened to 189 bytes by dropping zero-handling), and does its calculations in unary, after converting the decimal input to unary. (Its numeric variables are represented by the number of captures on each stack, being agnostic to the contents of the captures.) At the time, I thought it would be impossible to do this without a bound.

In order to match primes up to infinity, a very different algorithm must be used: actual base-encoded arithmetic, with long division. This is only possible in the .NET regex engine.

This regex captures the input in unary-coded decimal, where, on a balanced capture group that encodes a number, each digit is represented by a series of contiguous empty captures on the stack (with their count being the digit's value), and each digit is terminated by a non-empty capture. Depending on the capture group, some of them have their termination mark below each digit, and some have it above each digit; when a stack is reversed, this gets flipped. The long division is done in this data type.

Other alternatives would be converting the input from decimal to binary and then doing the arithmetic in binary, or using binary-coded decimal. I initially expected the former would turn out to be shortest, but after finishing and golfing an implementation of reading decimal input into binary, I realized that a prime regex using that would be well over 900 bytes.

.NET has a fairly obscure balanced group operation that is rarely used: (?<name1-name2>pattern). This matches (but does not capture) pattern, captures (pushes a value onto) \k<name1> as the interval from the end of the top capture on \k<name2> to the current cursor position, and then deletes (pops) that top capture from \k<name2>. If the interval is "negative", this actually causes .NET to throw an exception, Index was outside the bounds of the array, the next time that capture is used.

This regex takes advantage of the (?<name1-name2>pattern) syntax for golf reasons, using it as an equivalent for (?<-name2>)(?<name1>). It makes sure to only do this when the cursor is at the beginning of the input string, so that only empty values are pushed onto \k<name1>. This is used in two places, and I currently do not know why the first instance is working, instead of throwing the above-described exception; it seems to be that at least some of the \1 empties it pops would have been captured from elsewhere than the beginning of the string. The (?<-2>\2)(?<3>) does in fact throw this exception if an attempt is made to convert it from (?=.*$((?<-2>\2)(?<3>)|){9}) to (?<=((?<3-2>\2)|){9}^.*). As far as I know there's no debugger for .NET regex, so it may be tricky to get to the bottom of this.

When interpreting the explanation below, remember that lookbehinds in .NET, (?<=...) and (?<!...), are evaluated from right to left – so read those from bottom to top, one quantified token at a time. When entering a lookahead inside a lookbehind, go back to reading from top to bottom.

^
# Read decimal number into C1, in unary-coded decimal
(
    # Read this digit, adding it to C1
    (?=[6-9] (?<1>){6}|)  # C1 digit += 6, if digit is in [      6789]
    (?=[3-59](?<1>){3}|)  # C1 digit += 3, if digit is in [   345   9]
    (?=[258] (?<1>){2}|)  # C1 digit += 2, if digit is in [  2  5  8 ]
    (?=[147] (?<1>)   |)  # C1 digit += 1, if digit is in [ 1  4  7  ]
    .                     # C1: push separator
)+$
# C1 now has least-significant digit on top, separator above
(?<!
    (?= # Assert C1==0; since it must have the same number of separators as
        # there are digits in the input, if once we remove that number of
        # captures from it, it has nothing remaining, its value was zero.
        (?<-1>.)+
        (?(1)^)
    )
    \11 # Assert the quotient is not a power of 10 (all we really want is to
        # assert the quotient != 1, but that would be more complex to do);
        # discarding the powers of 10 other than 1 is harmless, because in those
        # cases where the remainder is zero, twice the divisor will yield half
        # the quotient and the remainder will still be zero.
    (?= # Calculate the remainder of division, letting C1 = C1 % C2:
        # C2 now has most-significant digit on top, separator above
        (                                      # C2
            (?<=
                (?=
                    # C1 now has least-significant digit on top, separator above
                    (?=                        # C3 = reverse(C2)
                        (                      # C3
                            (?<-2>)            # C2: pop separator
                            (?=
                                .*$
                                (
                                    (?<-2>\2)
                                    (?<3>)
                                |
                                ){9}
                            )
                            .                  # C3: push separator
                        )+
                        # Don't let C2 grow to be longer in digits than the
                        # input number
                        (?(2)^)
                    )
                    # C3 now has least-significant digit on top, separator above

                    # mutually align C1 with C3: C5 = reverse(C1), giving it its
                    # least-significant portion with no C3 digits to subtract
                    (?>
                        (?<-1>)                # C1: pop separator
                        (.)                    # C5: push separator
                        (?<=
                            (
                                # I'm not currently sure why "(?<5-1>\1)" can be
                                # used here as a shorthand for "(?<-1>\1)(?<5>)"
                                # but I think it has something to do with the
                                # fact that this mutually-align loop will only
                                # do a nonzero number of iterations after C2 has
                                # been padded with at least one leading zero,
                                # meaning C1 will have already been rewritten by
                                # reversing C5, i.e. we won't be dealing with
                                # the original capture of C1.
                                (?<5-1>\1)
                            |
                            ){9}
                            ^.*
                        )
                    )*

                    # \9 = borrow flag = unset = 0 (clear)

                    # C5 = reverse(C1 - C3); C2 = reverse(C3)
                    (?<2>
                        .       # C2: push separator at the end of each
                                #     iteration
                        (?<=
                            (                  # C5 digit = C1 digit
                                (?<5>)
                                (?<-1>\1)
                            |
                            ){9}
                            (
                                (?<-1>\1){10}  # C1 digit -= 10
                            |              # or...
                                ()             # \9 borrow flag = set
                            )
                            (                  # C1 digit -= C3 digit;
                                               # C2 digit  = C3 digit
                                # Using "(?<2-1>)" as a shorthand for
                                # "(?<-1>(?<2>))" works here because it is
                                # guaranteed to pull only from the captures
                                # pushed by "(?<1>){10}", which is always done
                                # at the beginning of the string.
                                (?<2-1>)
                                (?<-3>\3)
                            |
                            ){9}
                            (?<-9>             # if \9 borrow flag is set,
                                               # unset it...
                                (?<-1>)        # ...and C1 digit -= 1
                            )?
                            (?<1>){10}         # C1 digit += 10
                            (?<-3>)            # C3: pop separator
                            (?<-1>)            # C1: pop separator
                            (?<5>^.*)          # C5: push separator
                        )
                    )+$
                    (?!\9)       # Assert borrow is 0 (clear)
                    (?(3)^)      # Assert C3 has been emptied, and thus
                                 # completely processed (and by implication,
                                 # so has C1 been)
                    # C2 now has most-significant digit on top, separator above
                    # C5 now has most-significant digit on top, separator below
                    (?<=                       # C1 = reverse(C5)
                        (?<-5>
                            (?=
                                (?<1>
                                    (?=.*$\5)
                                |
                                    .
                                )
                            )
                            .
                        )*
                    ){10}
                    # C1 now has least-significant digit on top, separator above
                    (\12)?       # \11 = set if \12 is already set
                    ()           # \12 = set
                |
                    # or do nothing
                ){9}             # This digit of the quotient can range from
                                 # 0 to 9 (but we don't have to save the
                                 # quotient, just the remainder)
                ^.*
            )
            .   # pad C2 with one more leading zero
        )*
    )
    (?<-13>){3} # Assert C2 >= 2, unless C2 has a leading zero, using C13 as a
                # disposable copy of C2. The only numeric value of C2 without a
                # leading zero that puts only 2 captures on it is C2 == 1.
                # Values of C2 with leading zero(s) will cause the long division
                # algorithm to give an incorrect result, but never a false
                # positive of getting a remainder of zero, so this only results
                # in a little slowdown, testing invalid divisors.
    # C2 now has most-significant digit on top, separator above
    ^
    (?<-14>     # C13 = C2 = arbitrary number (a divisor to test)
        (?(14)|
            ((?<2>
                (.)?    # \14 = set optionally, ending incrementing of digit and
                        #      pushing a separator onto C2; due to the outer
                        #      loop being "(?<-14>)", if it still isn't set by
                        #      the last iteration of this loop, it will be.
            ))
        ){10}
    )+
    .*          # allow C2 to have fewer digits than the input
|
    ^1          # exclude 1, which is non-composite but also non-prime
)

As per the challenge rules, this does not bother to avoid matching \$0\$. But this can be fixed by changing |^1 to |^0*1? or |^[01], at a cost of 3 bytes.

Speed-improved version, 525 495 483 bytes

^((?=[6-9](?<1>){6}|)(?=[3-59](?<1>){3}|)(?=[258](?<1>){2}|)(?=[147](?<1>)|).)+$(?<!(?=(?<-1>.)+(?(1)^))\11(?=((?<=(?=(?=((?<-2>)(?=.*$((?<-2>\2)(?<3>)|){9}).)+(?(2)^))(?>(?<-1>)(.)(?<=((?<5-1>\1)|){9}^.*))*(?<2>.(?<=((?<5>)(?<-1>\1)|){9}((?<-1>\1){10}|())((?<2-1>)(?<-3>\3)|){9}(?<-9>(?<-1>))?(?<1>){10}(?<-3>)(?<-1>)(?<5>^.*)))+$(?!\9)(?(3)^)(?<=(?<-5>(?=(?<1>(?=.*$\5)|.)).)*){10}(\12)?()|){9}^.*).)*)(?<-13>){2}\13(?<-13>)^(?<-14>(?(14)|((?<2>(.)?))){10}(?<-15>))+(?<15>)(.)*|^1)

Try it online!
Try it online! - primes matched in unary, for comparison

This version limits its divisor search to \$\lceil{n\over 2}\rceil\$ digits, where \$n\$ is the number if digits in the input. This is guaranteed to go at least as high as the square root of the input number. It can test all the numbers up to \$3333\$ on TIO in 59 seconds.

Only the section that differs is explained below:

    # Assert C2 >= 2, using C13 as a disposal copy of C2:
        # The only numeric value of C2 without a leading zero that puts only 2
        # captures on it is C2 == 1
        (?<-13>){2}
        \13
        (?<-13>)
    # C2 now has most-significant digit on top, separator above
    ^
    (?<-14>         # C13 = C2 = arbitrary number (a divisor to test)
        (?(14)|
            ((?<2>
                (.)?    # \14 = set optionally, ending incrementing of digit and
                        #      pushing a separator onto C2; due to the outer
                        #      loop being "(?<-14>)", if it still isn't set by
                        #      the last iteration of this loop, it will be.
            ))
        ){10}
        (?<-15>)
    )+
    (?<15>)         # C15 += 1
    (.)*            # allow C2 to have fewer digits than the input;
                    # C15 += number digits skipped

Try it on regex101 - This is 540 503 491 bytes, as regex101 does it own validation on regexes instead of leaving that up to the engine in question, and does not currently support the (?<name1-name2>) syntax.

Regex (.NET), 692 449 396 325 bytes

^((?=(0|)).){2,}$(?<!(?=(?=((?<=(?=(?=(?<-3>(?=((?=.*$\3)|.)).)+(?(3)^))(?<-2>(?=((?=.*$\2)|.)).)*(?<-2>.(?<=(?=(?=(\2\4^|(?!\2^|\4^)|.))(?=(?<5>\7\6^|(?!\7|\6^)|.))(?(7)\2^(?!\4^)(?<-7>)|(?!\2^)\4^())?(?<3>\4^|.))^.*)(?<-4>))+$(?!\7)(?(4)^)(?<=(?<-5>(?=(?<2>(?=.*$\5)|.)).)+)|)^.*).)*)(?<-2>\2)+$)^(\B(?<3>.)|.(?<3>)){2,}.+)

Try it online!
Try it online! - primes matched in unary, for comparison

Takes its input in binary, which must not have any leading zeros. As such, it is non-competing in this challenge, which specifies that input may be taken in decimal, unary, or byte array.

The internal representation of a binary number as a capture stack is for \$0\$s to be non-empty captures, and \$1\$s to be empty captures. As such, the latter can match after the end of the string, and the former cannot.

^
# Read binary number into C2
(
    (?=
        (0|)  # C2
    )
    .
){2,}$  # at least 2 iterations to exclude 0 and 1 as non-prime
# C2 now has least-significant bit on top
(?<!
    (?=
        (?=
            (                                      # C3
                (?<=
                    (?=
                        # C2 now has least-significant bit on top
                        (?=
                            (?<-3>                 # C4 = reverse(C3)
                                (?=
                                    (              # C4
                                        (?=.*$\3)
                                    |
                                        .
                                    )
                                )
                                .
                            )+
                            # Don't let C3 grow to be longer in bits than the
                            # input number
                            (?(3)^)
                        )
                        # C4 now has least-significant bit on top

                        # mutually align C2 with C4
                        (?<-2>                     # C5 = reverse(C2)
                            (?=
                                (                  # C5
                                    (?=.*$\2)
                                |
                                    .
                                )
                            )
                            .
                        )*

                        # \7 = borrow flag = unset = 0 (clear)

                        # C5 = reverse(C2 - C4); C3 = reverse(C4)
                        (?<-2>
                            .
                            (?<=
                                (?=
                                    (?=
                                        (                # \6 = \2 xnor \4
                                            \2\4^
                                        |
                                            (?!\2^|\4^)
                                        |
                                            .
                                        )
                                    )
                                    (?=
                                        (?<5>            # C5: push bit \6 xnor \7
                                            \7\6^
                                        |
                                            (?!\7|\6^)
                                        |
                                            .
                                        )
                                    )
                                    # if \2 xnor \7, and \4 xor \7, then \7 = not \7
                                    (?(7)
                                        \2^
                                        (?!\4^)
                                        (?<-7>)          # \7 = unset borrow flag
                                    |
                                        (?!\2^)
                                        \4^
                                        ()               # \7 = set borrow flag
                                    )?
                                    (?<3>                # C3: push bit from C4
                                        \4^
                                    |
                                        .
                                    )
                                )
                                ^.*
                            )
                            (?<-4>)
                        )+$
                        (?!\7)       # Assert borrow is 0 (clear)
                        (?(4)^)      # Assert C4 has been emptied, and thus
                                     # completely processed (and by implication,
                                     # so has C2 been)
                        # C5 and C3 now have most-significant bit on top
                        (?<=
                            (?<-5>                 # C2 = reverse(C5)
                                (?=
                                    (?<2>
                                        (?=.*$\5)
                                    |
                                        .
                                    )
                                )
                                .
                            )+
                        )
                    |
                        # or do nothing
                    )
                    ^.*
                )
                .   # pad C3 with one more leading zero
            )*
        )
        # Assert C2 == 0
        (?<-2>
            \2
        )+$
    )
    # C3 now has most-significant bit on top
    ^
    (         # C3 = arbitrary number
        \B  # most-significant digit must be 1
        (?<3>.)  # C3: push 0 (non-empty)
    |
        .(?<3>)  # C3: push 1 (empty)
    ){2,}     # give C3 at least 2 bits, to force C3 >= 2
    .+        # force C3 to have at least 1 less bit than C5, making C3 < C5
)

Answer 2

Prolog (SWI), 42 40 39 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 (Y will never be greater than X, but the =< operator is one byte shorter than the =:= operator which represents equality for arithmetic expressions). If it is not the case that X =< Y then the predicate is true if 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.

Answer 3

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)

Answer 4

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
$

Answer 5

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 (v₁, ..., v_n) to the vector (v₁ + ... + v_n), i.e.,

>
	dab

This creates an alias > for the builtin function dab, which maps the vector (v₁, ..., v_n) to the vector (v₂, ..., v_n).

dip

The remaining builtin, dip, maps the vector (v₁, ..., v_n) to the vector (|v₁ - 1|, ..., |v_n - 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(v₁, ..., v_n) = (v₂ + ... + v_n, v₁ + ... + v_n).

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 v₂ + ... + v_n ≤ v₁ + ... + v_n, B maps the result returned by f to (0, v₁). + takes the sum, returning (v₁).

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 (v₁, ..., v_n) to (|v₁ - 1|, ..., v_n).

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.

Answer 6

><>, 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).

Answer 7

gs2, 2 bytes

Vk

Basically read-num is-prime.

Answer 8

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.

Answer 9

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.

Answer 10

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"

Answer 11

Python 2, 46 bytes

m=n=input()
a=1
while~-m:m-=1;a*=m*m
print a%n

Answer 12

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

Answer 13

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.

Answer 14

Python 3, 52 bytes

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

Saved a byte thanks to xnor in chat.

Answer 15

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)!).

Answer 16

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

Answer 17

naz, 334 318 316 311 307 bytes

Original solution:

2x2v
1x0f0v1s2x0v1v1s2x1v2v3x1v0l
1x1f2v1o
1x4f0v1a2x0v1v1s2x1v2v3x1v4l
1x5f3v2x1v0f2v3x0v5l9v3x2v2g2v
1x3f5v2x0v8v2x9v3v1s2x3v5f0v3x2v1e2v2a3x3v3l8f
1x2f9v1s2x9v0v9a9a9a9a9a9a9a9a9a9a9a1a2x0v5f
1x6f1r8s8s8s8s8s8s
6f2x8v
6f5m2m2x0v
6f2x1v
2v3x1v4l0v2x5v2v2x0v    
1x7f5v2x3v1s3x2v1e1s3x2v8e3f
1x8f2v1a1o
1x9f2v9a9a9a9a2x3v8v1s3x2v7l3f
9f

Only works after the current bugfixes to naz so it doesn't work here yet. As I'm not a good golfer and naz is cryptic enough, I didn't try to reduce the number of bytes further. I'm convinced there are multiple bytes to be shaved off somewhere.

Input

This program takes any three-digit natural number (001 to 999) as a command line argument in decimal representation.

Output

This program writes output: 0 for non-primes and output: 1 for primes output: is a constant output by the naz-interpreter that cannot be suppressed.

Truthy and falsy values don't exist in naz, as naz does not have a construct like if(b), so I used 0 and 1 as common falsy / truthy values. One can easily change them to any other string / number by modifying 1f (for false) and 8f (for true)

How it works

naz's only datatype is a signed byte from +127 to -127. When this limit is exceeded, the interpreter halts the execution immediately. So in order to test all three digit natural numbers (including those > 127), I used 2 variables for a combined number, having the hundreds in one variable and the ones in another.

For example: The number +540 would be separated in two bytes, 5 and 40.

naz has 9 register / variables that will do all of the calculation in this program. I'll refer to them as [0] (value of variable 0) to [9] (value of variable 9). If I'm combining two variables to create a bigger number, i'll refer to it as [8]::[5] (the number generated by [8] * 100 + [5] that cannot be represented in naz's data format)

Line by Line

2x2v: initial Setup. Naz doesn't have the constant 0 anywhere, except for the accumulator at the start of each program. I decided for my whole program that [2] should be 0 to give me access to that constant.

1x0f0v1s2x0v1v1s2x1v2v3x1v0l: function f0: [0] -= [1], [1] := 0. This function assumes [1] > 0.

1x1f2v1o: f1: print 0. This is my false function. It can be modified to print any falsy value.

1x4f0v1a2x0v1v1s2x1v2v3x1v4l: f4: [0] += [1], [1] := 0. This function assumes [1] > 0

1x5f3v2x1v0f2v3x0v5l9v3x2v2g2v: f5: calculate the remainder of [9]::[0] divided by [3] by repeated subtraction. Note that there will always be the negative value of the remainder, for example 5 % 3 = -1. Also note that [9]::[0] will be destroyed in this process and [0] will contain the remainder afterwards. [3] will not be modified. Calls f0 for the subtraction and f2 to handle carry-bit arithmetic.

1x3f5v2x0v8v2x9v3v1s2x3v5f0v3x2v1e2v2a3x3v3l8f: f3: The main prime-testing function: copies [8]::[5] to [9]::[0] (as expected by f5), decrements [3] calls 5f to calculate the remainder, ends the whole loop if [0] == 0 (i.e. [8]::[5] is divisible by [3]) by calling f1, continues the loop if [3] > 2 (note that [3] is decremented before calling f5, so this will test divisible by 2 iff [3] == 3 at this point in time. Call f8 (true function) if no other conditional hit (i.e. `[0] != 0 && [3] <= 2)

1x2f9v1s2x9v0v9a9a9a9a9a9a9a9a9a9a9a1a2x0v5f: f2: The carry-bit function. reduces [9] by 1 and increments [0] by 100. Calls f5 again afterwards as conditionals in naz do not result in function calls, so there's no jump back into 5f without this.

1x6f1r8s8s8s8s8s8s: f6: The input function: as '0' is 48, subtract 48 from the character read to get its numerical value in the accumulator.

6f2x8v: Read the hundreds and write them to [8].

6f5m2m2x0v: Read the tens, multiply them by ten and write them to [0]

6f2x1v: Read the ones, write them to [1]

2v3x1v4l0v2x5v2v2x0v: Call f4 iff [1] > 0, move [0] to [5], reset [0] := 0

1x7f5v2x3v1s3x2v1e1s3x2v8e3f: f7: Handle special cases. The general idea in this program is that any 3 digit number that is not a prime has to have at least one divisor in (2, 100). However, even primes smaller than 100 will have one divisor in (2, 100), themselves. This function only gets called if [8] == 0, i.e. [8]::[5] < 100, so instead of starting at a predetermined divisor we start at [5] (note that f3 will decrement [3] before checking divisibility). If [8] == 1, we jump to f1 (FALSE), if [8] == 2 we jump to f8 (TRUE) otherwise we continue with the prime-check function 3f.

1x8f2v1a1o: f8: My true function. As with f1, can be easily modified to do whatever we want if this number is a prime.

1x9f2v9a9a9a9a2x3v8v1s3x2v7l3f: f9: Setup [3] := 36 (as 35**2 > 1000). Goto f7 iff [8] == 0 (special cases), else call f3

9f: Execute 9f.

Edits

-16 bytes by replacing 0v9a9a9a9a9a9a9a9a9a9a9a1a2x0v (30 bytes) with 2v5a4m5m2x1v4f (14 bytes) in 2f

-2 bytes by replacing 8v1s3x2v7l with 8v3x2v7e in 9f

-5 bytes by removing all unnecessary '\n' (I really, really do miss them). That is the newline after 2x2v(1 byte), all of the initializing calls to 6f (3 bytes) and after 2v3x1v4l0v2x5v2v2x0v (1 byte)

-4 bytes by replacing 9a9a9a9a with 9a4m in 9f

Final Version

2x2v1x0f0v1s2x0v1v1s2x1v2v3x1v0l
1x1f2v1o
1x4f0v1a2x0v1v1s2x1v2v3x1v4l
1x5f3v2x1v0f2v3x0v5l9v3x2v2g2v
1x3f5v2x0v8v2x9v3v1s2x3v5f0v3x2v1e2v2a3x3v3l8f
1x2f9v1s2x9v2v5a4m5m2x1v4f5f
1x6f1r8s8s8s8s8s8s
6f2x8v6f5m2m2x0v6f2x1v2v3x1v4l0v2x5v2v2x0v1x7f5v2x3v1s3x2v1e1s3x2v8e3f
1x8f2v1a1o
1x9f2v9a4m2x3v8v3x2v7e3f
9f

Answer 18

Minecraft 1.12.2 (expandable), 5446 bytes per bit (1-255 version: 49014 bytes)

6 wide x 16 high x 44 long structure composed of two files, pchk_v1_1_front.nbt (3705 bytes) and pchk_v1_1_back.nbt (1741 bytes).

pchk_v1_1_front.nbt

pchk_v1_1_back.nbt

Less golfed:

8 bit version:

Notes on setting up

• Each module can be pasted right next to the last one, with no gap in between. No extra work is needed, however sometimes it is easier to replace the granite blocks with glass before copying & pasting, then to replace them back to a solid block afterwards. This prevents certain key observers from firing on clone/paste/fill/etc..

• When making a machine larger than 8 bits, the default timings may not be long enough. For any delay that scales with the number of modules, a long delay circuit is used. Increasing the number of items in each hopper should fix the problem just fine.

Operating the machine

1. Input the number to be checked as a signed (two's complement) integer. Only strictly positive inputs are valid for the challenge, but internally the machine requires signed integers in the trial division process. Do not change the input while the machine is running.
2. Connect a button to the rightmost end of the SYNC wire (pictured above) and press it once to run the machine. There is a built-in delay right at the start, so there is no need to wait for the machine to finish updating from the input changing before starting.
3. When the left lamp turns on, the machine has finished running. The right lamp is on when the input is prime, and off when it is not. Don't worry if it takes a while-- at 500 TPS (using Carpet mod /tick rate), checking the primality of the number 127 took around 7 minutes.

Explanation

Each module is composed of a few components:

• Input / Number (magenta)
• Divisor (light blue)
• Divider (orange)
• Control logic / SYNC pipeline (pink)
• Output lamps, connections between components, etc.

The button pressed to start computation connects directly to the SYNC wire, which starts the control logic on all modules on the exact same tick. The control logic implements the following pseudocode:

<SYNC pulse>

reset output

Number == 1:
    light Done
    <end of path>

Number != 1:
    reset Divisor + lock Number into Divisor

loop:
    decrement Divisor

    ; Now, Number >= 2 and Divisor = Number - 1.
    ; We check if Divisor divides Number until it does (composite), or until
    ; Divisor is 1 (prime). We have to check the latter first each loop 
    ; iteration as when Number is 2, Divisor starts at 1.

Divisor == 1:
    light Prime
    light Done
    <end of path>

Divisor != 1:
    check if Divisor divides Number

Divides:
    light Done
    <end of path>

Does not divide:
    goto loop

The divider implements its own logic as follows (repeated subtraction with State storing the current state):

divloop:
    reset State + lock Number into State
    ; Divisor is hardcoded into the divider
    
    ; When State - Divisor results in State's bit flipping, the T flip flop is
    ; toggled. Otherwise, State remains the same.
    update State
    
    State < 0:
        ; negative -> does not divide
        return DND
    
    State > 0:
        ; Could still be zero, keep going
        ; (no extra work needed here)
    
    State == 0:
        ; zero -> divides, n is composite
        return DIVIDES
         
    State != 0:
        goto divloop

Notes

• The module could probably be golfed down quite a bit further, if anyone wants to try.
• An analog (comparator) version might be smaller and would definitely be much faster than the current binary version.

Answer 19

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 &.

Answer 20

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.

Answer 21

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

Answer 22

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.

Answer 23

JavaScript (ES6), 47 bytes

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

Answer 24

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

Answer 25

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

Answer 26

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.

Answer 27

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.

Answer 28

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

Answer 29

Excel, 41 bytes

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

Takes input from A1.

4 bytes saved thanks to @Joffan!

Answer 30

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.