C Preprocessor (cpp), 1260 bytes

#define l()(
#define r())
#define V(v...)v
#define T(v...)U(v)
#define U(x,y,v...)y
#define A()j l V()()I
#define I()j l V()()A
#define Q()r V()()R
#define R()r V()()Q
#define u(x,v...)T(V(D(A x,K)v D(Q x,K)))
#define D(x,y)B(x,y)
#define B(x,y)x##y
#define AK
#define IK
#define QK
#define RK
#define j(v...)a(v)
#define a(f,v...)f,f(v)
#define w(x,v...)T(W(D(E x,K)v D(Q x,K)))
#define W(v...)v
#define n(v...)b(v)
#define b(f,v...)f,f(v)
#define E()n l V()()J
#define J()n l V()()E
#define EK
#define JK
#define z(x,v...)T(X(D(F x,K)v D(Q x,K)))
#define X(v...)v
#define o(v...)d(v)
#define d(f,v...)f,f(v)
#define F()o l V()()L
#define L()o l V()()F
#define FK
#define LK
#define _(x,v...)T(Y(D(G x,K)v D(Q x,K)))
#define Y(v...)v
#define s(v...)g(v)
#define g(f,v...)f,f(v)
#define G()s l V()()N
#define N()s l V()()G
#define GK
#define NK
#define $(x,v...)T(Z(D(H x,K)v D(Q x,K)))
#define Z(v...)v
#define t(v...)h(v)
#define h(f,v...)f,f(v)
#define H()t l V()()O
#define O()t l V()()H
#define HK
#define OK
#define p(x,y)y,y()
#define q(x)u(x,p,,)
#define S(x,y)w(y,q,x)
#define e(x,y)S((),S(x,y)S(y,x))
#define M(y,x,k,i)y e(x,i),x,k,k i
#define m(x,y)z(x,M,,x,y,y)
#define c(r,x,i)r m(x,i),x,i()
#define C(x)_(x,c,,x,())
#define P(x)e(C(x),()())
P(())

Try it online!

This is not written by me, all I did is to shorten the program by using one-character identifier whenever possible (of course it's not always possible because of the use of the ## operator).

It originally comes from l4m2's answer as a demonstration of the power of the C Preprocessor. If l4m2 intends to post an answer, I will delete mine.

The input is hard coded in the last line P(()). The macro P takes input in unary as a sequence of ()()...()() and outputs () if the input is a prime, or empty if the input isn't.

Note: although the common implementation of loops in the C preprocessor uses something like

#define EXPAND(x) x
#define EXP2(x) EXPAND(EXPAND(EXPAND(EXPAND(EXPAND(x)))))
#define EXP3(x) EXP2(EXP2(EXP2(EXP2(EXP2(x)))))
#define EXP4(x) EXP3(EXP3(EXP3(EXP3(EXP3(x)))))

which would imply there's only a finite number of expansion passes the program can go through, this does not mean the primality checker program above has any limit.

It is in fact possible with the C preprocessor to do loops bounded by the input size. Consider the following example

#define f() g
#define g() f
f()()()()

It results in f. In this example the number of macro expansions is equal to the number of pairs of parentheses provided by the user, not limited by anything built in the program.

With only minor modifications, you can imagine making a macro such that f()()()() expands to ()()()()()()()()f (doubles the number of pairs of parentheses) within one expansion pass. To eliminate the final f, or to implement something like multiplication, requires more complicated machinery however. For this, I recommend reading the original (ungolfed) source code by l4m2.

Background:

The link to l4m2's answer is not viewable to users with less than 10000 reputation because it was decided by a moderator that the answer is invalid. This was because because it does not contain explanation of the Turing-incompleteness of the C preprocessor as required by that question.

The explanation can be found in https://stackoverflow.com/a/37463357/5267751 which links to a paper containing Dave Prosser's algorithm which describes the precise algorithm used by actual preprocessor, the C standard leaves some parts of the operation of the preprocessor unspecified).

I used this script to automate some replacement of identifiers by single-character identifiers (others were done by hand), if someone else intend to try to write golfed programs in the C preprocessor, it could be useful.

Tcl, 78 75   74 bytes

_{^{Thanks to sergiol}}

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

_{^{Original version}}

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

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

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

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

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

Use it as:

C:\foo> run.bat 2017
prime

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

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

Use it as:

% ./run.sh 2017
prime

Enjoy!

CASIO BASIC (CASIO fx-9750GIII), 40 24 bytes

?→N~O
Do
Dsz O
O=1
LpWhile N Rmdr O

Prints 1 if the number is prime

iogii 7 bytes

(}.:*$%

Try it!

Using the formula (n-1)!^2%n

( deincrement   } countTo   . product    # take (n-1)!
: duplicate     * multiply               # take the square of that
$ argument      % modulo                 # take result % n

6 bytes is almost possible but doesn't work for 1:

:(}%t.

run it

: dup input
( deincrement   } countTo
% vectorized mod
t tail (to remove the %1)
. product (if any 0's then 0, which is falsey, 
           else it will be some >0 number, which is truthy)

SAKO, 127 116 85 bytes

CZYTAJ:A
F=0
*1)F=F+0*MOD(ENT(A),ENT(V))
POWTORZ:V=1(1)A
DRUKUJ(1,0):F-2
STOP1
KONIEC

I used here 0 for a truthy value and any other number for a falsy one.

AGL, 5/14 bytes

• a programming language i made! check out the link to my github repo.

mp#1=

Explanation:

mp#1=
mp    => m: mathematical, p: for 'prime factors', external function
  #   => length of list
   1= => equals 1? (primes would only have itself as a prime factor)

The more built-in way:

.#2>{%0>}%1+$<

Explanation:

.#2>{%0>}%1+$<
.#2>           => [2..input)
    {%0>}%     => check if each item has a remainder (item ÷ input)
          1+   => append 1 to list so that '$<' won't raise any errors
            $< => no divisible number? (all() in python)

Jalapeño, 1 bytes

′

Hex-Dump of Bytecode

       0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0000: 71                                              

Try it Online!

Jalapeño, 9 bytes

%{₂1‥I₀Σₓ¬≤2

More interesting as uses no factorising builtins, but uncompetitive.

Explained

%{₂1‥I₀Σₓ¬≤2
%            # Input value modulo every element of:
 {₂1‥I₀      # All the numbers 1 through input
       Σₓ¬   # Sum, mapped by logical not. (Count factors of n)
          ≤2 # Is the number of factors <=2

Hex-Dump of Bytecode

       0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0000: 54 c6 31 2e 90 ea 58 5e 32                      

Try it Online!

☾, 10 chars

󰲡x󷸺ᐵ∣xᐸ⨁≡2

Try it: ☾ web interpreter

This is an explicit version of the below whisker (tacit) function:

☾, ₁₂ 11 chars (33 bytes)

󷺹󷸺→ᐵ∣ᑅ⟞→⨁≡2

Try it: ☾ web interpreter

Bespoke, 206 201 bytes

-5 bytes by removing an unnecessary DO P instruction.

PRIME N=it will have no divisors if divisor is more than integer one
in fact,algebra reveals infinite integers that go in PRIME
this is my trial division method program
one=four,to hotpatch my tested N

This program is adapted from an example program I included in the official Python interpreter (which listed every prime starting from 2). It's also descriptive of its own algorithm.

Charcoal, 23 bytes

”&+“üsＡ⟧Ｅ±？)$l»v”✂Ｓ³Ｐ

Try It Online!

Kona, 12 Bytes

{&/x!/:2_!x}

Try it online! (change n with integer)

Regenerate, 24 bytes

(x{2,$~1-1})$2{$~1%#1}!1

Attempt This Online!

Takes decimal input as a command-line argument, and outputs with a somewhat improvised truthiness/falsiness convention: I consider a string truthy iff it can be successfully parsed as a decimal number, because failing to parse as a decimal number if used as such immediately triggers the recoverable/backtracking failure that drives Regenerate's control flow. However, there are many other sensible conventions possible--nonempty/empty, positive/nonpositive, etc.

 x                          Attempt to output the letter x
  {2,     }                 repeated at least 2 times
  { ,$~1-1}                 and at most as many times as the input minus 1.
(          )                Put that string in capture group 1.
            $2              Attempt to output the string in capture group 2
(x{2,$~1-1})$2{$~1%#1}!1    (which doesn't exist at all and cannot be output!)
              {      }      repeated a number of times equal to
               $~1          the input
                  %         modulo
                   #1       the length of the string in capture group 1.
 x{ ,     }           !     If no number of x repetitions worked,
                       1    output 1 instead.

Hence, this outputs a unary representation (in non-decimal-digits) of the input's smallest non-trivial factor by trial division if one exists, and a plain 1 if it does not. Regenerate often needs to output junk in order to do any kind of manipulation on the input deeper than the five arithmetic operations it supports or embedding it verbatim, so stringent output formats are very very bad for it outside the domain of kolmogorov-complexity and kolmo-adjacent challenges it was actually designed for, but in this case the junk is limited enough to also reuse as the output.

SqueezeL, ceil(26 * 2/3) = 18 bytes

(r(p(zmf(t(nn(zn(i)))))2)n

Uses Wilson's Theorem: outputs (n-1)!**2 mod n.

          (nn(zn(i)))         Set n to the input parsed as a number (so it can be reused)
        (t           )        Decrement
    (zmf              )       Factorial
  (p                   2)     Square
(r                       n    Mod n (and implicit print)

BrainChild, 81 57 bytes

include*;int j=int i=getint();while(--j&&i%j)0print(j==1)

^{Saved 24 bytes thanks to @Deadcode}

Readable

include io.bc;
int i = getint();
int j = i;
while(--j && i%j){}
print(j==1)

Try It Online!

Although there are several other answers that use a regex, none of them discuss the history of matching primes in this way, or show alternative regexes that match primes, or examine the range of compatibility of the regex with various engines. So that is what this post is all about.

All of the answers shown here take their input in bijective unary, as a string of x characters whose length represents the number. Output is in the form of "match" (prime) or "no match" (non-prime).

First, the shortest form:

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

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater.

Try it online!

This is the standard, well-known primality test for numbers expressed in unary. I first became aware of it when arriving upon this 14 byte form independently in the course of solving one of the levels of Regex Golf on 2014-02-12 (which kick-started my interest in regex code golf). But in there, the set of test cases only started at \$2\$ (xx), thus glossing over the fact that this regex matches the non-primes \$0\$ and \$1\$.

I later learned that this regex dates back to at least as early as a 1997-10-22 Perl post by Abigail, which then began being discussed on the next day, extending to the next two pages.

The first appearance of a regex primality test on CGCC was a 2012-01-16 answer by ChristopheD to "Finding Not-Quite-Prime Numbers".

Regex (ECMAScript or better), 16 bytes

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

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater, and \$n \ge 2\$.

Try it online!

The earliest I'm aware of anybody patching the regex in this way to block the matching of \$0\$ and \$1\$ is teukon in 2014-03-13. (I had previously toyed with ^(?!(xx+|)\1+$) as a patch, but this only blocks the matching of \$0\$.) Currently all of the other answers to this CGCC question that use the standard primality-testing regex, other than the Perl one, use this patched form: Retina, PowerShell, JavaScript.

It works in any engine supporting negative lookahead, which includes JavaScript/ECMAScript, Perl, PCRE, .NET, Java, Boost, Python, Ruby, and more.

Some alternative ways of testing primality avoid matching \$0\$ and \$1\$ in a conceptually and typographically cleaner way, but are longer:

Regex (ECMAScript or better), 18 bytes

^(?!(xx+)\1+$|x?$)

Try it online!

Same logic as above, except that preventing \$n \le 1\$ from matching is done inside the negative lookahead. See also the last version below, under "Inverted logic".

Regex (ECMAScript or better), 18 bytes

^(?=(xx+?)\1*$)\1$

The smallest \$q \ge 2\$ that divides \$n\$ exists, and \$q=n\$.

Try it online!

I came up with this on 2018-12-07. This expression can be useful within a larger regex, as it automatically captures the prime in a backref, which a negative lookahead cannot do. So, (?=(xx+?)\1*$)\1$ saves 1 byte compared to (?!(xx+)\1+$)(xx+) or 2 bytes compared to (?!(xx+)\1+$)(xx+$), and uses one less capture group.

Regex (ECMAScript or better), 18 bytes

(?=(x(x*))\1+$)\2^

The largest \$q \ge 1\$ that divides \$n\$ with a quotient of \$2\$ or greater exists, and \$q-1=0\$.

Try it online!

This was arrived at first by Grimmy on 2019-04-21. I independently came up with it on 2021-03-06, basing it on my earlier finding of ^(?>(x(x*))\1+$)\2 (below).

Like the below, it captures \1=\$1\$ and \2=\$0\$. If it were to be used in a larger regex (to assert primality without consuming any characters) and its captures aren't of use, ^(?!(xx+)\1+$|x?$) would be better, being equal in length but faster in most regex engines due to evaluating the ^ first instead of last (and its ^ can be omitted to test numbers smaller than the input for primality).

Regex (Perl / Java / Boost / Python / Ruby / PCRE / .NET), 18 bytes

^(?>(x(x*))\1+$)\2

The largest \$q \ge 1\$ that divides \$n\$ with a quotient of \$2\$ or greater exists, and \$q-1=0\$.

Try it online! - PCRE

I came up with this on 2018-12-07. It could conceivably be useful within the context of a larger regex. It consumes the entire prime number, like ^(?=(xx+?)\1*$)\1$, but its captures seem less likely to be useful; they are just \1=\$1\$ and \2=\$0\$. However, there may be niche circumstances where this could be coupled with NPCG (non-participating capture group) behavior, such that \1 or \2 matches if the path including the primality expression was crossed, but doesn't match otherwise. This would be equal in length to ^(?!(xx+)\1+$)xx() but capture two potentially useful optionally-unset groups instead of just one.

Regex (Tcl ARE), 16 bytes

^((x(x*))\2+$)\3

Try it online!

Tcl ARE has both positive and negative lookaheads, but neither backreferences nor captures can be done inside one. So seemingly, it would be impossible to match primes instead of non-primes.

But as it so happens, in Tcl ARE it seems that any group anchored on both sides (^ at the beginning and $ at the end, either outside the group or inside as long as it's adjacent to the parentheses in all its alternatives), will be treated as atomic (preventing the engine from doing the equivalent of backtracking into that expression if the pattern fails to match at a later point), as if the entire expression up to and including the $ were enclosed in (?>...). This does not appear to be documented, but can be exploited to emulate a negative match.

This regex is based on the 18 byte PCRE regex above. Both capture groups are shifted forward by 1, so \2 is \$q\$ and \3 is \$q-1\$.

‍

\$\large{\text{Inverted logic}}\$

In the following answers, "no match" indicates a prime, and a match indicates a non-prime.

Regex (GNU ERE or better), 14 bytes

^(xx+)\1+$|^x$

Try it online! - GNU ERE (very slow)
Try it online! - Tcl ARE
Try it online! - ECMAScript

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater, and \$n \ne 1\$.

Gives a false positive for \$n=0\$. As explained below, this cannot be avoided.

Alternative form:

^((xx+)\2+|x)$

Regex (Tcl ARE or better), 15 bytes

^(xx+)\1+$|^x?$

Try it online! - Tcl ARE
Try it online! - ECMAScript

There does not exist any \$q \ge 2\$ that divides \$n\$ with a quotient of \$2\$ or greater, and \$n \ge 2\$.

Gives a correct answer for all \$n\ge 0\$. Doesn't work under GNU ERE, nor does any variation of it such as ^((xx+)\2+|x|)$ or ^(xx+)\1+$|^x$|^$. The moment the ability to match an empty string is added, it falsely matches all primes greater than \$7\$. This appears to be a bug in GNU ERE.

This form of primality test, eliminating the false positives on \$0\$ and \$1\$, dates back to at least as early as Abigail's 1997-11-18 signature on Perl Users Digest. It was not golfed at this point, and used a lazy quantifier for performance reasons (a change that occurred on 1997-10-24). This got carried over into some early CGCC answers, making them at least 1 byte longer than necessary.

The form presented here puts ^x?$ in the second alternative for performance reasons, so that it won't slow down the testing of \$n‍≥2\$ with the slight overhead of always trying that match first.

Alternative form:

^((xx+)\2+|x?)$

Uiua, 10 bytes ^(SBCS)

=1⧻°/×⋕&sc

Try it in the pad!

All the other Uiua answers are from extremely old versions which use features that have since been changed.

This answer makes use of the °/× un reduce multiply function, which gets the prime factorization of a number, and then checks if the length of that is one.

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 the first instance only works in RegexOptions.Compiled mode; without it, the above-described exception is thrown with inputs \$\ge 21\$, probably because some of the \1 empties it pops were captured from elsewhere than the beginning of the string. A third potential place for this trick would seem to be (?<-2>\2)(?<3>), but if an attempt is made to convert it from (?=.*$((?<-2>\2)(?<3>)|){9}) to (?<=((?<3-2>\2)|){9}^.*), the exception is thrown regardless of mode. Seeing as there's no debugger for .NET regex, it would be tricky to dig deeper into the conditional nature of this error.

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
Try it on regex101 - 487 bytes*

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

*regex101 doesn't make it possible to enable the Compiled flag, so it throws the error in versions that use the (?<5-1>\1) shorthand. Here is commented view of the section modified to avoid this error (making it 4 bytes longer):

                    # 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
                        (?=
                            .*$
                            (
                                (?<-1>\1)
                                (?<5>)
                            |
                            ){9}
                        )
                    )*

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

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
)

AWK, 28 bytes

    {for(j=2;$0%j;j++);}j~$0

Try it online!

Easyfuck, 35 31 bytes

D‘ň␗Č_-ZňÚG‰VŕPůňµ2’>Bům×É␗ţV­SHY8

^{due to lack of unicode representations for c1 control characters, they have been replaced by their superscripted abbreviations}

Decompressed:

"$>!>!>--<[$<%-`(>>+)J$>!>-]>$/~++'

"$>!>!>--<[$<%-`(>>+)J$>!>-]>$/~++'
"$>!>!                              input an 8bit integer into 1st cell and copy it into 2nd and 3rd
      >--<                          set 4th cell to 254 and go back to 3rd
          [                ]        while loop
           $<%-`(>>+)               modulo 2nd cell by 3rd and if 0 increment 4th
                     J$>!>-         copy 1st cell to 2nd and decrement 3rd
                            >$/     divide 4th cell by self to get to 0 or 1
                               ~++' turn 1 into 0 and vice versa, then print

Cabsi, 108 bytes

1PUSH 1,""
2INPUT
3DUP
4DEC
5DUP
6ROT
7DUP
8ROT
9MOD
10JNP 90
11POP
12SWAP
13GOTO 4
90POP
91POP
92EQ
93PRINT

Try it

Cabsi is Conor O’Brien’s new stack-based BASIC derivative. It has 2 stacks, but this solution only uses one of them. This is a full program, taking an integer from STDIN and outputting a zero or a one.

Explanation:

1   PUSH 1,"" REM. Stack [1 ""]
2   INPUT     REM. Stack [1 N]            Print the string, push an int from STDIN
3   DUP       REM. Stack [1 N N]

4   DEC       REM. Stack [1 N D]          D is the denominator, decremented every iteration, starts at N-1
5   DUP       REM. Stack [1 N D D]
6   ROT       REM. Stack [1 D D N]
7   DUP       REM. Stack [1 D D N N]
8   ROT       REM. Stack [1 D N D N]
9   MOD       REM. Stack [1 D N (N % D)]
10  JNP 90    REM. Stack doesn’t change.  If the result of the modulo was 0, jump to 90
11  POP       REM. Stack [1 N-1 N]
12  SWAP      REM. Stack [1 N N-1]
13  GOTO 4    REM. Stack doesn’t change.  Jump to line 4

90  POP       REM. Stack [1 D N]          At this point, N was divisible by D
91  POP       REM. Stack [1 D]
92  EQ        REM. Stack [(D == 1)]       If the denominator is 1, then N is prime, otherwise it’s composite
93  PRINT     REM. Write to STDOUT

GolfScript, 14 bytes

~.,{*.!+}*.*\%

Try it online!

This outputs this version of Wilson's theorem, used in other answers to this question:

\$(n-1)!^2 \mod{n}\$

This outputs 1 if it is a prime and 0 if it is not.

~                 # Push n
 .,               # Range from 0 to (n-1)
   {*.!+}         # Push block without executing
         *        # Fold
          .*      # Square, it could also be 2?, but for large values of n there would be an error message
            \%    # Mod n

What the block does:

    *             # Multiply
     .!           # Is it 0?
       +          # Add 1 if it was 0 and 0 if it wasn't

This uses 3 bytes to avoid the 0, there are ways of removing it from the array using 2:

~.,(;{*}*.*\%

Try it online!

The problem here is when the input is 1, in this case after removing the 0 we wouldn't have any number to multiply.

Uiua, 13 bytes

=1/+=0◿⇡.⧻&sc

Try it online! (uses a 9 byte function instead)

Couldn't find a 8-byte primality test that works for 1 yet. Correctly gives 0 (false) for the input of 0.

=1/+=0◿⇡.    input: positive integer n
      ◿⇡.    n modulo each of 0..n-1
    =0        equals 0? gives 1 for zeros and 0 for others
  /+          sum (= number of divisors minus 1)
=1            equals 1?

Uiua, 19 bytes

?¬(¬∊0◿↘2⇡.)=1.⧻&sc

Explanation:

?¬(¬∊0◿↘2⇡.)=1.⧻&sc­⁡​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌­
               ⧻&sc  # ‎⁡pushes n to the stack (read from STDIN in unary)
            =1.      # pushes 1 if n=1, otherwise 0
?¬(        )         # ‎⁢if ^^ = 1, invert the remaining 1 and finish, otherwise run the function in parentheses
      ◿↘2⇡.          # ‎⁣replace n with an array of all n mod k for 1 < k < n
   ¬∊0               # 1 if there is no 0 in that array

JavaScript (Node.js), 30 bytes

f=(n,i=n)=>i==2||n%--i&&f(n,i)

Attempt This Online!

2 bytes longer than this solution but uses a slightly different method so I thought I'd post it.

Returns falsey (0 or NaN) for composite, true for prime.

Pretty simple - checks n % i for all i from n down to 2, returning 1 only if 2 is reached.

Uiua, 19 bytes

=2/+⌕0◿+1⇡.parse&sc

If this was just a function, it'd be 10 bytes. But it's a full program so the parse function is needed :sob:

Thanks Dennis very cool.

Explained

=0/+¬±◿↘2⇡.parse&sc­⁡​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁢​‎⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁣​‎⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁡​‎⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌­
          .parse&sc  # ‎⁡Read the input as a number (which I wouldn't need if this was a function submission)
       ↘2⇡.          # ‎⁢Range [2, input)
      ◿              # ‎⁣input % n for each n in ^
    ¬±               # ‎⁤And invert the sign. Honestly this could just be `=0`, but where's the fun in that.
  /+                 # ‎⁢⁡Summate that 
=0                   # ‎⁢⁢Does the sum equal 0?
💎

Created with the help of Luminespire.

MaybeLater, 52 bytes

wheni is*ifi<n{if1>n%i o=0i++}n=read()o=1i=2write(o)

Ungolfed

when (i is *){
    if (i<n){
        if (1>n%i){
            o=0
        }
        i++
    }
}
n=read()
o=1
i=2
write(o)

Naïve approach.

Try it online!

TypeScript's Type System, 111 bytes

type P<N,B extends 1[]=[1,1],A=N>=N extends B?1:A extends[...B,...infer I]?P<N,B,I>:A extends[]?0:P<N,[...B,1]>

Try it at the TypeScript Playground!

This is a recursive generic type P taking unary number N as a list of 1s. Outputs 1 if the input is prime, and 0 otherwise. Exception-throws a recursion error for input 1, indicating falsey.

I thought primality test would be a lot longer than it ended up being so I'm pretty pleased.

type P<                    // recursive type P
  N,                       // takes unary number N
  B extends 1[]=[1,1],     // and unary number B which defaults to 2
  A=N                      // A is used to determine divisibility
>=
  N extends B?1            // if B == N, N is prime; return 1
  :A extends[...B,         // else if B fits in A
    ...infer I             //   let I be the difference
  ]?P<N,B,I>               //   recurse with A = I
  :A extends[]?0           // else if A == 0, N isn't prime; return 0
  :P<N,[...B,1]>           // else recurse with B + 1

floor, 105 bytes

F:x->floor x
r:x->1/(x-F x)
I:x->1+F(F x-x)
p:k->(F k*r k)+1/(r k-1)
f:n->(n-1)*I(F p^(n-2)(1+1/(n-1))/n)

returns nonzero for primes and zero for non-primes

Explanation

Ungolfed version:

intPair: x y -> x + 1/y
left: x -> floor x
right: x -> 1/(x-floor x)

is_int: x -> 1+floor(floor x - x)

fakt_1: n_k -> intPair ((left n_k)*(right n_k)) (right n_k - 1)

f: n -> (n-1)*is_int( (left fakt_1^(n-2) intPair 1 (n-1))/n)

Uses Wilson's theorem to determine if the input is a prime number

fakt_1^(n-2) intPair 1 (n-1) computes (n-1)!+1 (abusing that storing one in the second component of a pair, will increase the first component by 1)

The rest of f checks if (n-1)!+1 is evenly divisible by n and returns 1 if yes and zero otherwise. The multiplication with (n-1) is to ensure that 1 is not falsely detected as prime

Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>

floor, 116 bytes

F:x->floor x
r:x->1/(x-F x)
I:x->-F(F x-x)
s:p->I(F p/r p)*F p+1/(1+r p)
f:n->-F((1-n)/((1-n)^2+1))*F s^(n-2)(n+1/2)

returns non-zero for primes and zero for composites

Explanation:

Ungolfed version:

lt: x y -> -(floor((x-y)/((x-y)^2+1)))

intPair: x y -> x + 1/y
left: x -> floor x
right: x -> 1/(x-floor x)

not_int: x -> -floor(floor x - x)

prime_step: n_k -> intPair (not_int(left n_k / right n_k) * left n_k) (1+right n_k)
f: n -> (lt 1 n)*(left prime_step^(n-2)(intPair n 2))

prime_step takes a pair of integers (n,k) (encoded as a single rational number) as input an returns (0,k+1) if k is a divisor of n, and (n,k+1) otherwise.

f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0

ARBLE, 5 bytes

prime

Try it online!

Slightly more interesting solution, 45 25 bytes

sum(range(2,n-1)|nt(n%x))

Returns falsey for primes, truthy for non-primes.

Try it online!

Trilangle 1.3, 31 29 bytes

<'?<#2%._zS<.>(>.,)2-/\\_/!@@

Reads a single integer from STDIN, and prints 0 iff it's prime.

Try it on the online interpreter!

TL;DR

Keeps a running counter that starts at 2, and increments it until (input % counter) == 0. Then, it prints '0' if input == counter.

What is Trilangle?

Trilangle is a 2-D stack-based programming language. Program flow can be redirected with "mirrors" /|\_ or with branches <^7>vL. The branches can split, merge, or reflect control flow, depending on how they're used. If the IP walks off the board, it continues one row or diagonal to its left.

Code Explanation

Unfolds to this example from the README:

       <
      ' ?
     < # 2
    % . _ z
   S < . > (
  > . , ) 2 -
 / \ \ _ / ! @
@ . . . . . . .

Equivalent to this C code:

#include <stdio.h>

// Get an integer from stdin. Implementation provided by the interpreter.
extern int getint(void);

int main() {
  // RED PATH
  int input = getint();
  int counter = 2;
  while (input % counter)
    // GREEN PATH
    ++n;
  // BLUE PATH
  if (input == counter)
    // YELLOW PATH
    return 0;
  // MAGENTA PATH
  puts("0");
  return 0;
}

This uses the new 2DUP instruction z to make stack management easier: it copies both the input and counter so that they may be operated on non-destructively. The older version below used a combination of j (indexed read), 2 (duplicate), and S (swap) to achieve a similar effect.

Older answer: Trilangle 1.0,  42  41 40 bytes

'2.?..<_.@j.2'2,<|>(%!.\S)S,,)S<.....@>-

C (gcc), 119 71 69 bytes

p;main(a){for(scanf("%d",&p);++a<p;)p=p/a*a-p?p:1;puts(p-1?"1":"0");}

• Thanks to ceilingcat for the reduction to 71 bytes.

• Thanks to ceilingcat for another 2 bytes shaved off by using puts instead of printf.

Outputs 0 (falsy) when it's composite and 1 (truthy) when it's prime.

My first C answer. To me, it's just a mix of Python and Assembly. Well, at least it's probably not as long as Java...

printf("Try it online!")

Vyxal 3.0.0-beta.2, 8 bytes

1?R%0C1=

Try it online! (link is to literate version)

alternatively

1 input a->b mod 0 count 1 equal?

The fun of pre-releases

Explained

1?R%0C1=­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
1?R       # ‎⁡Range [1, input)
   %      # ‎⁢input % each in ^
    0C    # ‎⁣Count the number of 0s. This will return 0 for input = 1, because range [1, 1) is []
      1=  # ‎⁤Does that equal 1?
💎

Created with the help of Luminespire.

ForWhile, 24 bytes

9:`[_48=';+')1;[1+;;%)=#

Takes unary number less than 9⁹ as input, prints 0x01 if prime and 0x00 otherwise

online Interpreter

Explanation

The first half of the code is just number-parsing (ForWhile does not have a built-in for that). The actual prime checking code is 1;[1+;;%)=.

9:`[        )            \ repeat up to 9^9 times
    _48=                 \ read one byte, check if it is equal to 48 (char code of 0)
        ';+              \ if yes, increment second value on stack
           ')            \ if no, break from loop
             1           \ push one
              ;[         \ repeat up to n (input number) times
                1+       \ increment value on stack
                  ;;%)   \ break loop if top stack value is divisor of input -> smallest divisor of number that is greater than 1
                      =  \ check if number is equal to its smallest divisor greater than 1
                       # \ print the result to standard output

binary input (36 bytes)

99[_48-:0<!:[.'2*+1]).1;[1+;;%)=48+#

prints 1 for prime and 0 for non-prime

decimal input (37 bytes)

99[_48-:0<!:[.'10*+1]).1;[1+;;%)=48+#

prints 1 for prime and 0 for non-prime

Shasta ^v0.0.8, 31 bytes

{(all(map(range2$){|a|(%$a)}))}

Explanation:

{                   ; function($):
  (all              ;   are all truthy (i.e. non-zero):
    (map            ;     map over
      (range 2 $)   ;       the range from 2 to $
      {|a| (% $ a)} ;       function(a): $ mod a
    )               ;     end map
  )                 ;   end all
}                   ; end function

No online interpreter yet, but installation instructions are at the GitHub link and I've run it against several test cases on my machine.

Rockstar, 119 117 107 bytes

Outputs -0.5 for primes and 0 for composites.

listen to N
let D be N
let P be N-1
while P and D-2
let D be-1
let M be N/D
turn M up
let P be N/D-M

say P

Try it here (Code will need to be pasted in)

listen to N         :Read input string into variable N
let D be N          :Initialise D as N
let P be N-1        :Initialise P as N-1, which will be 0 (falsey) if N=1
while P and D-2     :While P and D-2 are not zero
let D be-1          :  Decrement D
let M be N/D        :  Assign N/D to variable M
turn M up           :  Round M up
let P be N/D-M      :  Reassign N/D-M to P
                    :End while loop
say P               :Output P

Python, 73 Bytes

import math
y=lambda b:b>1and math.factorial(b-1)%b==b-1
print(y(input()))

-37 from The Thonnu :O
+20 to fulfil challenge requirements -6 by using math.factorial.

This code is based on Wilson's Theorem.

Thunno 2, 1 byte

P

Attenpt This Online!

APL(Dyalog Unicode), 9 bytes ^SBCS

2=0+.=⍳|⊢

Try it on APLgolf!

A tacit function which takes a number and returns a boolean.

Explanation

2=0+.=⍳|⊢
  0+.=    the count of the number of 0s in
       |  the remainder from
        ⊢ the argument
          (divided by)
      ⍳   the numbers from 1..n
2=        equals 2

hyperscript, 82 69 65 bytes

def f(n)set x to n-1 repeat while n mod x decrement(x)end log x<2

This is shorter than a recursive solution because hyperscript doesn’t have a great way to do optional parameters.

<script src="https://unpkg.com/hyperscript.org@0.9.8"></script>
<script type="text/hyperscript">
def f(n)set x to n-1 repeat while n mod x decrement(x)end log x<2
</script>


<label style="font-family:monospace">n: <input type="number"style="font-size:1.5rem;width:4.5ch"_="on change call f(my value)" /></label>

Ungolfed:

def f(n)
  set x to n - 1 
  repeat while n mod x 
    decrement(x)
  end 
  return x is 1
end

Scratch, 81 bytes

Try it on Scratch!

Scratchblocks syntax:

define(n
set[i v]to((n)-(1
repeat until<(0)=((n)mod(i
change[i v]by(-1
say<(i)=(1

This works best if the procedure is checked as "Run without screen refresh." If the option is unchecked it will still work, but will take n frames to output the correct result (i.e. the result will be incorrect for n frames).

Tabloid, 358 293 bytes

DISCOVER HOW TO x WITH a, b WHAT IF b BEATS 1 WHAT IF ((a DIVIDED BY b) MODULO 1) BEATS 0 SHOCKING DEVELOPMENT x OF a, b MINUS 1 LIES! SHOCKING DEVELOPMENT 0 LIES! SHOCKING DEVELOPMENT 1 EXPERTS CLAIM y TO BE LATEST NEWS ON "" YOU WON'T WANT TO MISS x OF y, y MINUS 1 PLEASE LIKE AND SUBSCRIBE

Input through a JavaScript prompt(), and output 1! if the input is prime and 0! otherwise (exclamation point due to language restrictions)

-65 bytes by using BEATS (greater than) instead of SMALLER THAN (less than) and IS ACTUALLY (equal to), inverting some if conditions on the way

Readable version

DISCOVER HOW TO x WITH a, b
    WHAT IF b BEATS 1
        WHAT IF ((a DIVIDED BY b) MODULO 1) BEATS 0
            SHOCKING DEVELOPMENT x OF a, b MINUS 1
        LIES!
            SHOCKING DEVELOPMENT 0
    LIES!
        SHOCKING DEVELOPMENT 1
EXPERTS CLAIM y TO BE LATEST NEWS ON ""
YOU WON'T WANT TO MISS x OF y, y MINUS 1
PLEASE LIKE AND SUBSCRIBE

Original (358 bytes)

DISCOVER HOW TO x WITH a, b RUMOR HAS IT WHAT IF b SMALLER THAN 2 SHOCKING DEVELOPMENT 1 LIES! RUMOR HAS IT WHAT IF ((a DIVIDED BY b) MODULO 1) IS ACTUALLY 0 SHOCKING DEVELOPMENT 0 LIES! SHOCKING DEVELOPMENT x OF a, b MINUS 1 END OF STORY END OF STORY EXPERTS CLAIM y TO BE LATEST NEWS ON "" YOU WON'T WANT TO MISS x OF y, y MINUS 1 PLEASE LIKE AND SUBSCRIBE

Readable version

DISCOVER HOW TO x WITH a, b RUMOR HAS IT
    WHAT IF b SMALLER THAN 2
        SHOCKING DEVELOPMENT 1
    LIES! RUMOR HAS IT
        WHAT IF ((a DIVIDED BY b) MODULO 1) IS ACTUALLY 0
            SHOCKING DEVELOPMENT 0
        LIES!
            SHOCKING DEVELOPMENT x OF a, b MINUS 1
        END OF STORY
    END OF STORY
EXPERTS CLAIM y TO BE LATEST NEWS ON ""
YOU WON'T WANT TO MISS x OF y, y MINUS 1
PLEASE LIKE AND SUBSCRIBE

GAIA, 1 byte

ṗ

Try it online!

LiveCode, 128 bytes

on mouseUp
   ask ""
   put it div 2 into i
   repeat with j=2 to it-1
      put it mod j*i into i
   end repeat
   put i>0
end mouseUp

Put in a button and press the button. Asks for a number, puts true or false reporting primality into the message box. LiveCode does support stdin and stdout, but other answers here used this method so I am as well.

A function would make more sense to me, but that doesn't seem to be the accepted method here.

Explanation

Should be pretty clear:

Starts with 0 if the input is 1, or 1 or more if input > 1.

Then for every number from 2 to the input - 1, multiplies the running total by the input modulo the number. If any of the numbers evenly divide the number, the running total will change to (and remain for the rest of the loop) zero.

At the end, report whether the running total is greater than 0. If it is, the input is prime, if it has been zero-ified at any point, the input is not prime.

minigolf, 29 bytes

iT+:,:ns,:n*;s,_;*i=+0=s0=0=*

Attempt This Online!

Explanation

Generate a multiplication table of (input-1)x(input-1):

iT+                input - 1
:                  duplicate
,                  map in [1..i-1]:
  :                  duplicate i-1 so that it's preserved across iterations of map
  ns                 swap current iteration item underneath
  ,                  map in [1..i-1]:
    :                  dup curr. iter. item of outer loop (so that it's preserved)
    n*                 multiply by curr. iter. item of this map loop
  ;                  end map
  s,_                swap up & drop our preserved curr. map value
;                  end map

Aftermath of the multiplication table:
*                  flatten
i=                 Set by equality w/ input
+                  sum that
0=                 = 0? (i.e. no items in that table that equals input)
                   Note: at this point we have i-1 underneath our top value
s                  Swap i-1 upwards
0=0=               Set all >0 values to 1
*                  Multiply (i.e. if i-1 is zero, our prime checking output is 0.)

Google Sheets, 29 bytes

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

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

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

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

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

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

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

WTFstack, 13 bytes

1g{?(!)?/x<{;

WTFstack is my new programming language in which mathematical operations work on the entire stack at once.

Returns a stack of [1] if prime, and an empty stack if composite.

Interpreter

Explanation

1g            # is the input > 1?
  {           # if so, continue. else, print the stack and exit
   ?          # push the user input
    (         # -1
     !        # factorial
      )       # +1
       ?      # push the input again
        /     # divide all values on the stack by the input
         x    # push if the number is an integer or not (0 or 1)
          <   # swap the top two values on the stack
           {  # is the top of the stack truthy? if so, continue, else exit
            ; # discard the top of the stack

Thunno, 1 byte

(Technically it's \$1 \log_{256}(96) \approx\$ 0.82 bytes, but that doesn't show up on the leaderboard)

N

Attempt This Online!

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.

Python3, 53 bytes

(lambda n:all(n%i for i in range(2,n)))(int(input()))

Vyxal, 7 bytes

‹¡›$%¬

No shady built-ins, just pure, beautiful maths.
Basically Wilson's theorem

\$\large{(n-1)!+1 } \equiv 0 \left(\mod n\right)\$

Try it Online!

Explanation:

‹¡›$%¬ 
‹¡       push n-1 factorial
  ›      push n+1
   $%    modulo top two items swapped
     ¬   apply logical not

K (ngn/k), 18 bytes

1=+/1>(!x)!'x:.1:0

Try it online!

Fig, \$3\log_{256}(96)\approx\$ 2.469 bytes

{Lk

Try it online!

Outputs with reversed boolean - 0 for truthy, any other integer for falsy.

Fig, \$2\log_{256}(96)\approx\$ 1.646 bytes

mp

Try it online!

Builtin solution.

Cubestack, 98 bytes

M R2 M' b' M R M' r M R' M' U2 S S' y b' M R M' r S S' y2 U M R M' D x M R M' b f2 x' y' M R' M' b

Try it Online!

Brief explanation:

M R2 M' b' M R M' r M R' M' U2 S S'  # Set up the for loop
M R2 M'                              # Push 2 to the stack
        b'                           # Get all inputs wrapped in a list
           M R M' r                  # Get the first item of the list pushed
                    M R' M'          # Push 1 to the stack
                            U2       # Range (start, end, step)
                               S S'  # Push an empty string (the loop variable)

y b' M R M' r S S' y2 U M R M' D  # Check if n is divisible the loop variable
y                                 # Open a for loop
  b' M R M' r                     # Get the first (and only) input
              S S' y2             # Get the value of the loop variable
                      U           # Perform modulo operation on the top two items
                        M R M' D  # Check if the top item equals 0

x M R M' b f2 x' y'  # If n is divisible be the loop variable, print 0 and exit
x                    # Open an if statement (code runs if top item is truthy)
  M R M'             # Push 0 to the stack
         b           # Print
           f2        # Exit program
              x'     # Finish if statement
                 y'  # End for loop

M R' M' b  # Provided that the program didn't exit in the loop, print 1

I won't explain Cubestack's syntax here, but you can see more information about this cursed language on the docs on GitHub.

rSNBATWPL, 49 bytes

print{n=input{};(i~cond{n%i}{{i- 1}}$i*i<2)$n- 1}

Recursive solution, as a full program. As a function, it's 34:

n~(i~cond{n%i}{{i- 1}}$i*i<2)$n- 1

flax, 1 byte

V

What can I say here?

Vyxal, 1 byte

æ

Try it Online!

<>^v, 184 bytes

Prints 1 if number is prime, otherwise 0.

>]v2i>IT%0=vIT[vv
             > vv
1          I   TI
T          T    )
T          =    i
t          > ^  v
,    ^          <
               v
               >"1";
  >        >"0";
^@|

Explanation

@  Pointer starts here, goes right
|  Mirror — reverse pointer direction
@  No-op because the program is already running
^  Send instruction pointer up
,  Read number from stdin and push to stack
t  Pop and store in variable `t`
T  Push value of variable `t`
T  Same
1  Push 1
>  Send instruction pointer right
]  If top element of stack is greater or equal to the second element of the stack
  v  Send instruction pointer down
  >  Send instruction pointer right
  Go to [not prime]
Else
2  Push 2
i  Pop and store into variable `i`
[loop start]
>  Send instruction pointer right
I  Push value of variable `i`
T  Push value of variable `t`
%  Set top of stack to top of stack modulo second element of stack
0  Push 0
=  If the top two elements of the stack are equal
  v  Send instruction pointer down
  I  Push value of variable `i`
  T  Push value of variable `t`
  =  If the top two elements of the stack are equal
    >  Send instruction pointer right
    ^  Send instruction pointer up
    >  Send instruction pointer right
    Go to [prime]
  Else
[not prime]
    >  Send instruction pointer right
    "0"  Push "0"
    ;  Print top of stack
    ';' was the last character of this row, program exits
Else
I  Push value of variable `i`
T  Push value of variable `t`
If the first element of the stack (t) is smaller or equal to the second element of the stack (i)
  v  Send instruction pointer down
[prime]
  v  Send instruction pointer down
  T  Push value of T
  v  Send instruction pointer down (there only to ensure the row is long enough)
  >  Send instruction pointer right
  "1"  Push "1"
  ;  Print top of stack
  Since ';' was the last character of the row, exit
v  Send instruction pointer down
v  Idem
I  Push value of variable `i`
)  Increment top of stack
i  Pop stack and store in variable `i`
v  Send instruction pointer down
<  Send instruction pointer left
^  Send instruction pointer up
Go to [loop start]

More simply, it first checks if the number is lower or equal to 1. If so, it prints 0 and exits. Then, it sets the variable i (current divisor) to 2. Then the program enters a loop. In that loop:

• If the number modulo i is 0:
  • If i == number, print 1 and exit (prime). Else, print 0 and exit (has found a divisor, number isn't prime).
• Then it increments i, and goes back to the beginning of the loop.

run online

tinylisp, 87 bytes

(load lib/math
(d f(q((n k)(i(e n k)1(i(mod n k)(f n(+ k 1))0
(d F(q((n)(f(s n(e 1 n))2

Try it online!

If anyone knows a way to use default arguments in tinylisp, I would very much appreciate it.

This answer only uses the math library and built-ins. It is shorter than the other tinylisp answer's pure version.

Explanation

Defines f, a function taking in n (main number) and k (factor). Returns 1 if k is equal to n (we have gone through all factors up to n without stopping) and otherwise, we check if n is divisible by k. If so, we return 0, otherwise, we return f called with n and k plus 1.

Then, we define the main function F which takes in only the main number, and sets k to 2.

-10 bytes thanks to @Razetime. -7 bytes thanks to @DLosc. Added some bytes to account for n = 1 case.

Excel, 34 bytes

=SUM((MOD(A1,SEQUENCE(A1))=0)*1)=2

Link to Spreadsheet

Limited to \$n <= 2^{20}\$ because of SEQUENCE(). A 40-byte alternative that works for \$n<(2^{20}+1)^2\$ is below.

=SUM((MOD(A2,SEQUENCE(SQRT(A2)))=0)*1)=1

Add++ -i, 9 bytes

L,dFSbL2=

Try it online!

Using my favourite approach without any actual primality built-ins

Explained

L,dFSbL2=
L,          # A lambda called by the -i flag that:
  dF        # pushes all the factors of the input and the input
    S       # uniquify the stack - this is so that `1` is handled correctly
     bL2=   # does the length of the TOS equal 2?

Nibbles, 4 bytes

%^`*<<,

Uses Wilson's theorem, which states that an integer \$ n \$ \$ (n > 1) \$ is prime iff \$ (n-1)! + 1 \$ is divisible by \$ n \$. To capitalize on Nibbles' implicit args feature, I slightly modified the formula to check for \$ (n - 1)!^n \bmod n > 0 \$, which also nicely handles the \$ n = 1 \$ edge case.

In Nibbles, an integer is Truthy if it is positive, and Falsy otherwise. Under this definition, checking whether the modulus is positive isn't necessary.

Ungolfed

%         # Modulo of
 ^        #  power of
  `*      #   product of
    <<,   #    [1..n-1] (implicit $)
          #   n (implicit $)
          #  n (implicit $)

MathGolf, 1 byte

¶

   -- for each line in input
¶  -- 1 if it's prime or 0 if not (works with lists too)
   -- implicit print

Try it online!

Vyxal, 3 bytes

KḢ₃

Try it Online!

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

-1 thanks to EmanresuA

Explained

KḢ₃
KḢ   # factors(input)[1:]
  ₃  # len(^) == 1 // prime numbers have only [1, n] as factors...other numbers have 1 or 3+ factors

ErrLess, 47 bytes

q@1=1-[{3+}2xY@;>1-[{@;%0=1-[{0#.};1+xy}2]y1_#.

Could probably get golfed a lot more...

Prints 0 if the input is not prime, -1 if it is, no trailing newline.

It uses -1 as a truthy value, since that is used for if-constructs, and what you get if a comparison is true.

Explanation

q           { Input a number: (p) }
@1= 1-[{    { If p == 1 }
 3+         { 1 -> 4, so that it correctly identifies 1 as non-prime }
}
2x          { Push a stack containing the number, and two: ((p 2)) }
Y @;> 1-[{  { While p > i }
 @;%0= 1-[{ { If p%i == 0 }
  0#.       { Print 0 and halt }
 }
 ;1+x       { Increment i: ((p i++)) }
y}2]y

1_#.        { Print -1 (ErrLess's truthy value) and halt }

ErrLess is a stack-based language I made for fun over the last few months. You can read the docs here, and I also started a tutorial.

Try it online!

///, 145 bytes

/~/\/\///$/\\\\~%/+**~I/*~>**/^=$=^=$%|$+$I^^%|$%^%|$+^^%|$+^+|^^=$+^=$=^^+$*^-$**^^-$*^+$*^>~^/\~/>*~/>~>I/||/1~=\=1~/=\=|=/1~=~/*~/|~/11/1/==|=

Try it online! Outputs 1 for composite numbers (not prime), and nothing for prime numbers. I am very happy I was able to post the first answer in my favorite language on a popular question, with a fairly good score too :)

Takes input in unary asterisks, ie. input = number of asterisks

/~/\/\///$/\\\\~%/+**~I/input here~>**/...
/~/\/\///$/\\\\~%/+**~I/*~>**/...    # 1
/~/\/\///$/\\\\~%/+**~I/**~>**/...   # 2
/~/\/\///$/\\\\~%/+*****~I/*~>**/... # 6

Ungolfed: Try it online!

Explanation:

/>**/.../ Repeats n/2 times, so we don't divide the input by itself

...+**... Starts counter at 2 so we don't divide by 1

If the input is divided evenly by any of the remaining numbers, it is not prime.

We need to "export" the current counter value to outside the loop, because there is no way to only target the counter in the current iteration, since all the iterations are copies of each other. We do this by writing it after the == at the end.

The ^ are escaped /'s in the loop, I unescaped the loop code below

/+\*/-\**/ /-\*/+\*/ Increment counter

/=\=/=\+**|\+\I/ This adds +counter|+input at the end

/+**|\+**/+**|\+ replaces +counter|+counter, which has the effect of repeatedly subtracting the counter from the input, or counter%input. Ex.

/+**|+**/+**|+/
+**|+********
gives:
+**|+********
+**|+******
+**|+****
+**|+**
+**|+

/+**|\+/+|/ deletes the +counter, just leaving +|remainder

/=\+/=\= / resets the printer, and deletes the + just leaving |remainder

After the loop, we are left with the remainders of each division, separated by | (in the ungolfed, there are also spaces).

/||/1/ 2 |'s next to each other means the remainder in between was 0

Everything else deletes garbage, or handles edge case stuff with 1 and 2.

Rust (full program), 124 bytes

fn main(){let s=&mut"".into();std::io::stdin().read_line(s);let n=s.parse().unwrap();print!("{}",n>1&&(2..n).all(|x|n%x>0))}

Try it online!

How complicated it has to be to read an integer from stdin...

Arduino, 146 143 bytes

#define S Serial
int p=0,d=1;void setup(){S.begin(300);}void loop(){while(S.available())p=p*256+S.read();if(p&&!(p%++d%p)){S.print(p==d);p=0;}}

Based on the current top answer for C++. I'm not convinced my adaptation is optimal.

Reading in a number from the Serial input is actually pretty annoying in Arduino. Serial.available() gives the number of unread bytes, but unfortunately it caps out at 64, which is too small for me to use unary for this challenge. Instead, I opted to interpret the input as a byte array.
Bitshift is lower precedence than addition, and (p<<8) is longer than p*256 (note the parentheses needed).
In this case, a while loop is actually shorter than a for loop, by 1 character.

Explanation:

#define S Serial /* This macro is worth it in the end, but not by much */

int p = 0, // the case p = 0 is also taken to mean not to even attempt this anyways
    d = 1;

void setup() {
  S.begin(300); // standard is 9600 but 300 is shorter
}

void loop() {
  while (S.available()) // truthy while there are unread bytes
    p = p * 256 + S.read();

  if (p && !(p % ++d % p)) { // second condition from the C++ answer
    S.print(p == d); // method from the C++ answer
    p = 0; // reset this to stop trying
  }
}

I suppose this technically comes with the caveat that no byte of the number can be 0 (so 256 wouldn't work; it's 0x0100), as the serial port takes in null-terminated strings. That said, it's only two more characters to make a version that accepts numbers written in decimal -- just replace p*256+S.read() with p*10+S.read()-48.

Original:

int p=0,d=1;void setup(){Serial.begin(300);}void loop(){while(Serial.available())p=p*256+S.read();if(p&&!(p%++d%p)){Serial.print(p==d);p=0;}}

Taxi, 1238 bytes

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

Try it online!

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

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

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

This is the code ungolfed with some comments.

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

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

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

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

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

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

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

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

Try it online!

Knight, 35 bytes

;=y;=x+0P1;W&=z>x=y+1y%x y 0O&-xT!z

Try it online!

Edit: Outgolfed by sampersand

Rough.

Prints true for primes, false or 0 for non-primes.

# prompt for a number, coerce to integer
; = x + 0 PROMPT
# loop counter
; = i 1
# Loop while x > y and x % y != 0
; WHILE & (= cmp > x y) (% x y)
    : NOP
# Output result. The - x 1 returns false for 1.
: OUTPUT & (- x 1) (!cmp)

Knight, 24 bytes

O&-=x+0P=iT?x;W%x=i+1iNi

Prints true for primes, false for composite numbers.

# print the output of the entire body
OUTPUT
  # If the number's one, then `&` returns `false`. otherwise we execute the rhs.
  &

    # `>` will coerce `i` to a number, and return `TRUE` unless `x` is one.
    >
      = x (+ 0 PROMPT) # set `x` to the input value
      = i TRUE

    # We know `x` is prime if the first `i` that `%x i` is zero for is `x`.
    ?
      x
      ;
        # evaluate the while loop then discard it.
        # note that `+ 1 i` will coerce the initial `TRUE` to a `1`.
        WHILE % x (= i + 1 i)
          NULL # ignore the body

        # the return value of `;` is `i` here. It'll be equal to `x` for primes.
        i

OCaml, 50 bytes

fun n->List.(init (n-1) succ|>map((mod)n)|>mem 0);;

and it's almost idiomatic and readable.

just sad that init begins at 0 and not 1, could have saved a lot on that :(

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.

JavaScript (ES6), 28 bytes

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

Try it online!

Old, 33 bytes:

f=(n,t=2)=>t<n?n%t?f(n,t+1):0:n>1

MMIX, 14 bytes (56 instrs)

(jxd)

00000000: 31ff0001 7a00ff00 31ff0002 6300ff03  1”¡¢z¡”¡1”¡£c¡”¤
00000010: e3010002 f7010000 1e020001 feff0006  ẉ¢¡£ẋ¢¡¡œ£¡¢“”¡©
00000020: 7a00ff00 32ff0201 e7010001 59fffffb  z¡”¡2”£¢ḃ¢¡¢Y””»
00000030: 7b000001 f8010000                    {¡¡¢ẏ¢¡¡

Disassembled:

prime   CMP  $255,$0,1
        ZSNZ $0,$255,$0     // if(n == 1) n = 0
        CMP  $255,$0,2
        CSZ  $0,$255,3      // if(n == 2) n = 3
        SETL $1,2           // i = 2
        PUT  rD,0
0H      DIVU $2,$0,$1       // loop: q = n / i
        GET  $255,rR        // r = n % i
        ZSNZ $0,$255,$0     // if(!r) n = 0
        CMPU $255,$2,$1
        INCL $1,1
        PBNN $255,0B        // if(q >= i++) goto loop
        ZSNZ $0,$0,1
        POP  1,0            // return (bool)n

Pxem, Content: 0 bytes + Filename: 54 bytes.

• Filename (escaped): ._.c\002.y.d.a.c\002\003.t.x.c.m.%\001.y.d.a.c.m\001.+.c.t.c.!\001.-.a.n
• Content is empty.

Usage

• Input is given from stdin, as a string of decimal integer.
• Outputs the input number for truthy; no output for falsey.

How it works

._XX.z
# let input be n
# get out if <2
.a.c\002.y.d.aXX.z
# let i be 2
# while i*i<=n (or i*i-1<n); do
.a.c\002\003.t.xXX.z
  # if n%i<1; then exit; fi
  .a.c.m.%\001.y.d.aXX.z
  # i++
  .a.c.m\001.+.c.t.c.!\001.-XX.z
# done; print n
.a.a.n

Try it online!

SmallBasic, 163 bytes

n=TextWindow.ReadNumber()
t=1
If n<2 Then
t=0
Goto e
EndIf
For i=2 to Math.Power(n,.5)
If Math.Remainder(n,i)=0 Then
t=0
Goto e
EndIf
EndFor
e:
TextWindow.Write(t)

This is so self-explanatory. But some key points:-

• A simple algorithm, Set the prime check value to 1, iterate through 2 to square root of input. If there are any divisors set prime check value to 0, else continue. At last output it.

• What a shame, its Square root builtin is shorter than power by 1/2.

PPL 1.0.5, 85 bytes

fnp(n){
declareb=1
declaref=4<5
loop n - 2{
b=b+1
ifn%b<1{
f=3<2
}
}
unsetb
returnf
}

It is a "good practice" (defined by me, of course) to unset all unneeded variables before returning. The unset statement is like delete in JavaScript. The fn statement defines a function and returns the flag. Still many bugs to iron out (remember, this is still being developed) but seeing as this is a catalogue of primality tests, thought I might post one. You have to unset n and f each time you recall the function, though.

Duocentehexaquinquagesimal, 23 bytes

7 ÇÇW∞DćƒΣZ;ndž“~3¦€`н¸k

Try it online!

Java (JDK), 105 bytes

interface P{static void main(String[]a){long i=2,n=new Long(a[0]);while(n%i++>0);System.out.print(i>n);}}

Try it online!

JavaScript (ES6), 42 41 bytes

!/^(.|(.+.)\2+)$/.test(Array(-~prompt()))

Based off of this regex solution. Array(+prompt()+1) creates a string of commas from the input, and it is simply passed through the (slightly edited) aforementioned solution. Array(+prompt()+1) can be replaced with 10**prompt()/9|0, but that seems to fail for numbers greater than 10.

Java, 108 bytes

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

Try it online!

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

Ungolfed

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

        // The input is prime iff that number is equal to the input
        System.out.println(input == div);
    }
}

CSASM v2.1.2.2, 207 235 bytes

Prints a 1 (truthy) if the input is a prime integer, 0 (falsy) otherwise.
Truthy values in CSASM are non-zero numbers, non-\0 chars and non-null strings/arrays/objects.
Falsy values in CSASM are zero, the \0 character or null strings/arrays/objects.

func main:
in ""
conv i32
pop $a
push $a
push 2
comp.gte
push $f.o
brtrue a
br b
.lbl a
push 2
dup
pop $1
push $a
sub
brfalse d
.lbl c
clf.o
push $a
push $1
rem
brfalse b
inc $1
push $1
push $a
comp.lt
push $f.o
brtrue c
.lbl d
push 1
print
ret
.lbl b
push 0
print
ret
end

Commented and ungolfed:

func main:
    ; Get the input, convert it to an integer and store it in the accumulator
    in ""
    conv i32
    pop $a

    ; if $a < 2, then $a is not prime
    push $a
    push 2
    comp.gte
    push $f.o
    brtrue initLoop
    br notPrime

    .lbl initLoop
    ; Initialize the loop counter and check if $a == 2
    ; If $a is 2, return truthy early
    push 2
    dup
    pop $1
    push $a
    sub
    brfalse prime

    .lbl loop
        ; Clear the comparison flag
        clf.o

        ; If $a % $1 == 0, then $a is not prime
        push $a
        push $1
        rem
        brfalse notPrime

        ; Loop until $1 >= $a
        inc $1
        push $1
        push $a
        comp.lt
        push $f.o
        brtrue loop

    .lbl prime
    ; $a is prime
    push 1
    print
    ret

    .lbl notPrime
    ; $a is not prime
    push 0
    print
    ret
end

ArnoldC, 707 636 618 bytes

Saved 71 89 bytes thanks to pppery!

LISTEN TO ME VERY CAREFULLY f
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE n
HEY CHRISTMAS TREE k
YOU SET US UP 2
HEY CHRISTMAS TREE l
YOU SET US UP 1
HEY CHRISTMAS TREE p
YOU SET US UP 1
GET TO THE CHOPPER l
HERE IS MY INVITATION n
LET OFF SOME STEAM BENNET k
ENOUGH TALK
STICK AROUND l
GET TO THE CHOPPER p
HERE IS MY INVITATION n
I LET HIM GO k
LET OFF SOME STEAM BENNET 0
KNOCK KNOCK p
ENOUGH TALK
GET TO THE CHOPPER k
HERE IS MY INVITATION k
GET UP 1
ENOUGH TALK
GET TO THE CHOPPER l
HERE IS MY INVITATION n
LET OFF SOME STEAM BENNET k
KNOCK KNOCK p
ENOUGH TALK
CHILL
TALK TO THE HAND p
HASTA LA VISTA, BABY

Try it online!

Doesn't look like anyone's posted an ArnoldC answer here yet, and I thought the best way to respect the Terminator would be by writing an answer in his language.

ARM Thumb, no div instructions, 43 bytes

f7ff fffe represents placeholders for libc calls, to scanf and printf respectively.

b503 4669 a008 f7ff fffe bc03 2802 d907
2202 0001 1a89 d003 d8fc 3201 4282 d1f8
a001 f7ff fffe bd00 6425 00

Assembly code:

        .globl main
        .thumb
        .thumb_func
main:
        push    {r0, r1, lr}
        mov     r1, sp
        adr     r0, printf_scanf_str
        bl      scanf
        pop     {r0, r1}
        cmp     r0, #2
        bls     .Ltrue
        movs    r2, #2
.Lloop1:
        movs    r1, r0
.Ldivloop:
        subs    r1, r2
        beq     .Lfalse
        bhi     .Ldivloop
.Ldivloop_end:
        adds    r2, #1
        cmp     r2, r0
        bne     .Lloop1
.Ltrue:
        @ movs    r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value
.Lfalse:
        adr     r0, printf_scanf_str
        bl      printf
        pop     {pc}

printf_scanf_str:
        .asciz "%d"

Accepts a number from stdin, and prints nonzero if it is a prime, or zero if it isn't.

Walkthrough

Behold, a prime searcher that is so slow you'd swear it was Python.

It is a brute force modulo check using a subtraction loop with zero shortcuts.

Here, we use a trick with push to make space for the scanf output and save the link register.

push will subtract from sp and store the registers in ascending order in memory.

So for example, push {r0, r1, lr} will end up like this:

| sp + 0 | sp + 4 | sp + 8 |
| argc   | argv   | return |

We don't actually care about argc - we care about the space on sp. We can then just pass the stack pointer directly to scanf.

We do sorta care about argv. Not about what it points to, but that it is a valid (non-zero) pointer.

scanf("%d", &r0)

main:
        push    {r0, r1, lr}
        mov     r1, sp
        adr     r0, printf_scanf_str
        bl      scanf

Then, we can pop the result from scanf we stored into r0, and argv into r1 as a "non-zero" value.

        pop     {r0, r1}

Immediately return true for values <= 2. This is exactly why we pushed and popped r1.

        cmp     r0, #2
        bls     .Ltrue

Begin factorizing against 2.

        movs    r2, #2

Use a subtraction loop on a copy of r0 to check if r0 % r2 == 0.

Specifically, the subs will reach zero on an even multiple and set the zero flag (which corresponds to the eq condition). Otherwise, we loop until it underflows (not hi)

.Lloop1:
        movs    r1, r0
.Ldivloop:
        subs    r1, r2
        beq     .Lfalse
        bhi     .Ldivloop

Increment the number we factor against and loop if it is not equal to r0.

.Ldivloop_end:
        adds    r2, #1
        cmp     r2, r0
        bne     .Lloop1

Optionally, with the true condition, we set r1 to 1 if it is a prime.

But non-zero is "truthy" enough for us even if it is a little ugly. It will either be the last inverted modulo we tested, or the address of argv, all of which will be non-zero.

Due to how our subtraction loop works, by the time we jump to .Lfalse, r1 will already be zero.

.Ltrue:
        @ movs    r1, #1 @ optional, needs odd load address but will print 1 instead of a random nonzero value
.Lfalse:

r1 is already conveniently (and intentionally) in the right place to forward directly to printf, and all we need to do is reload the printf/scanf string to r0 (no easy way around this) and call printf.

Note that due to how pop works in Thumb, it isn't really that useful to do tail calls because we cannot pop directly into lr without a wide instruction.

printf("%d", r1)

        adr     r0, printf_scanf_str
        bl      printf

Last, pop the return address from lr we pushed earlier directly into the program counter to return from main.

        pop     {pc}

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

Arn, 13 12 10 7 bytes

“sƥNm(┤

Previous versions:

ï_C3<│ì♦3(

├¦&┼6k┐ÇŠq""

{•Õ╝_¸”b¦¤º!E

Try it!

Explained

Unpacked: !(1+fact-1)%.

I may add a builtin for checking primality, but until then I made use of Wilson's Theorem; that is, $$((n - 1)! + 1)\mod n\equiv 0$$ will yield true iff n is a prime number.

!                   Boolean Not
    (               Begin expression
        1           Literal one
      +             Addition
        fact        factorial function
            _       Variable initialized to STDIN; implied
          -         Subtraction
            1       Literal one
    )               End expression
  %                 Modulo
    _               Implied

Thank goodness I finally fixed operator precedence.

MAWP, 48 46 54 bytes

@1A<:.>{1A<1:.>2M}!1A[/!!\!/P\!/WA<:.>{%}\2A?0{1M}]1:.

-2 bytes from Dion's suggestion.

+8 bytes after fixing the problem with 1 as input.

Prints 1 for prime and 0 for non-prime. Can probably be golfed by a few more bytes, since it checks for 2 at the beginning first.

Try it!

qalc/Qalculate, 8 bytes

If reading from any variable is allowed:

p-1)!²%p

Otherwise 12 bytes:

ans−1)!²%ans

The great thing about "programming" in a calculator is that you can basically just enter formulas directly.

Example usage in Bash for the "ans" case:

echo "5" | qalc -t -f - "ans−1)! ²%ans"

Note that I added a space after the exclamation mark only because Bash otherwise tries to interpret "!²" as an "event". It's not actually required by qalc, which can be seen by for example creating this file:

5
(ans−1)!²%ans

…and then executing it with qalc -t -f test.txt.

Other consoles or other ways of calling qalc than Bash might not have this problem.

The calculation can also be entered in "interactive mode" by simply running qalc -t, entering the number and then entering the expression on the next input. This also works in the GUI program "Qalculate".

Meta explanation:

The output is 0 for non-prime numbers and a positive integer for prime numbers. I let this run in a loop for all numbers up to 10000 and it was always 1 for prime numbers, but I haven't checked whether that is guaranteed yet.

This solution is based on this Labyrinth answer. I essentially just found something (qalc) that has all the parts of the formula as builtins instead of having to program all the parts myself on a lower level.

The -t argument hides the interpreted calculation, so that the output of the example command looks like this:

5
1

…instead of like this:

5 = 5
rem(factorial(ans - 1)^2, ans) = 1

Reading the number in in qalc is difficult. It has a system of variables, but I haven't figured out how to set those in the CLI yet. In the GUI it's pretty easy. That's one of the main reasons why I also provided a solution with "ans".

Inserting the number into the formula two times would mean modifying the "program", which is surely not allowed.

There seems to be no way to execute multiple expressions non-interactively with qalc, except by reading in a file. In this case, I used - as a "file", which is StdIn, and used that only to store the input in ans, which is implicitly done by qalc. You could also use an actual file and use the number in that file as input. Or you could even say that ans is already the input of the "program", in which case the program is simply the 12 bytes seen above, or even any variable, then the 8 byte solution.

Algorithm explanation:

The Wikipedia article linked in the Labyrinth answer looks pretty confusing, but the principle is easy:

(6-1)!²%6 = 1·1·2·2·3·3·4·4·5·5%6
          = 1·1· 6 · 6 ·4·4·5·5%6
          = 6 ·   something    %6
          = 0

This works because every non-prime number is the product of at least two factors that are smaller than that number. Prime numbers aren't, which leads to something like this:

(5-1)!²%5 = 1·1·2·2·3·3·4·4%5
          = 1·1·2·2·3·3·4·4%5
(no multiplication of those factors results in anything divisible by 5)
          = 1

The squaring is necessary in case there is only one prime factor and that occurs twice:

(9-1)!²%9 = 1·1·2·2·3·3·4·4·5·5·6·6·7·7·8·8%9
          = 1·1·2·2· 9 ·4·4·5·5·6·6·7·7·8·8%9
          = 9 ·         something          %9
          = 0

I originally wrote this answer for TI-Basic:

fPart((Ans-1)!²/Ans

That's just 10 bytes, but it fails on the input 13 already, due to floating point imprecisions in those large numbers (12!²=229442532802560000). So the only difference to an even/odd checker within the working range is 9 and it does not fulfil the criterion to work up to 255. For inputs above 42 it even crashed from an overflow (42!²>10¹⁰⁰).

DIVCON, 8 bytes

Prequisities: Enter 1 into the INPUT_MAX prompt.

i*[;-=o]

Explanation

"Partition" by * here means solving x * y = a - a is the original accumulator value. x and y needs to be as close as possible. In addition, the following equality must be satisfied: x>=y

         Description     | Example(0) | Example(1)
         ----------------+------------+-----------
i        Take an input   |  12        | 13
 *       Partition by *  | 4, 3       | 13, 1
         ----------------+------------+-----------
  [      Left branch     |   4        | 13
         Do nothing      | *discarded*| *discarded*
         ----------------+------------+------------
   ;     Right branch    | 3          | 1
    -    x - 1           | 2          | 0
     =   x == 0?         | 0          | 1
      o  Print this value| OUT: 0     | OUT: 1
         ----------------+------------+------------
       ] End both branches

Actually, there is another implicit reverse computation. But, since INPUT_MAX is 1, the extra prompting from i is disabled.

GHC 8.2.2, 716 bytes

{-#LANGUAGE FlexibleInstances,FunctionalDependencies,UndecidableInstances,CPP#-}
#define i instance
#define c class
data F
data T
data S n
data C x s
c A p q r|p q->r
i A F q F
i A T q q
c E p x y z|p x y->z
i E F x y y
i E T x y x
c G x y b|x y->b
i G x F T
i G F(S y)F
i G x y b=>G(S x)(S y)b
c M x y z|x y->z
i M x F x
i M F(S y)F
i M x y z=>M(S x)(S y)z
c D x y b|x y->b
i D x F T
i(G(S y)x p,M(S y)x z,D x z q,A p q b)=>D x(S y)b
c K f x y|f x->y
i D m n b=>K(S n)m b
c I f s n|f s->n
i I f F F
i(K f x b,I f s m,E b(S m)m n)=>I f(C x s)n
c R n s|n->s
i R F F
i R n s=>R(S n)(C(S n)s)
c Q m n b|m n->b
i Q F F T
i Q F(S y)F
i Q(S x)F F
i Q x y b=>Q(S x)(S y)b
c P n b|n->b
i(R n s,I(S n)s m,Q m(S(S F))b)=>P n b

Try it online!

This has got to be the most beautiful code I've ever written. It's a compile-time metaprogram that determines whether a type (represented Peano-style, where F is zero and S n is n's successor) is prime.

This works in GHC 8.2.2, the version TIO currently uses. It works locally in 8.8.3 as well. I have included the language extensions in the code, all except one—the TIO example linked above has MonoLocalBinds to suppress a warning. The program works just fine without them.

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

Output has to be written to STDOUT or closest alternative.

As far as I know, metaprograms like this have no means of I/O. With FunctionalDependencies, typeclasses can act much like functions, and in this way, the typeclass P is a "function" from natural numbers to booleans (T and F—yes, the same type represents zero, false, and the empty list). I believe this to be the closest alternative to the standard streams.

The test suite I provided covers numbers from one to twenty. Try changing any T to F or vice-versa, and the program will fail to compile.

I know there are improvements that can be made, and I'll be updating this answer soonish with them.

Haskell + Parsec, 181 bytes, no math

import Text.Parsec
a=anyChar
g s=a>>= \c->try(many1$string$c:s)*>eof<|>g(c:s)
main=readLn>>= \x->print$0<case parse(try(a*>eof)<|>(pure<$>a>>=g))""$replicate x '0'of{Left _->1;_->0}

Try it online!

Ungolfed and explanation:

import Data.Either (isLeft)
import Text.Parsec (eof, (<|>), try, anyChar, many1, string, parse)
import Text.Parsec.String (Parser)

-- Successfully parses any string of nonprime length, and fails on all others.
-- Exactly one character is not prime. If more than one character exists, we recurse with `go`.
notPrime :: Parser ()
notPrime = try (anyChar *> eof) <|> (pure <$> anyChar >>= go)
    -- `go cs` reads a character `c` and determines whether the remaining input is `c:cs` repeated.
    -- If so, the parse succeeds. If not, we call `go (c:cs)` to read another character and test again.
    where go :: String -> Parser ()
          go cs = do
                  c <- anyChar
                  try (many1 $ string $ c:cs) *> eof <|> go (c:cs)

-- Checks whether the parser `notPrime` fails on a uniform string of the specified length
isPrime :: Int -> Bool
isPrime n = isLeft $ parse notPrime "" (replicate n '\0')

Try it online!

cQuents, 3 bytes

?pZ

Try it online!

Explanation

Usually, I'd put the commands here, but I feel like that wouldn't be enough.

? outputs if the input is in the sequence. Item 1: Z returns 0, as Z returns the previous item, and Item 0 is always 0. p finds the next prime number (2). Item 2: Z returns 2. p finds the next prime number, which I thought would be 2, but no, it returns 3.

Keg, 43 36 6 4 bytes (SBCS)

@MPƒ

-2 bytes using a BFL function

乁( ⏒ ͜ʖ ⏒ )ㄏ

Answer History

6 bytes

:;¡²$%

Try it online!

-30 bytes thanks to @JoKing

No TIO as it needs to be updated due to a bug found with the ² operator.

Transpiles to:

from KegLib import *
from Stackd import Stack
stack = Stack()
printed = False
duplicate(stack)
decrement(stack)
factorial(stack)
square(stack)
swap(stack)
maths(stack, '%')

if not printed:
    printing = ""
    for item in stack:
        if type(item) is Stack:
            printing += str(item)

        elif type(item) is str:
            printing += custom_format(item)
        elif type(item) == Coherse.char:
            printing += item.v

        elif item < 10 or item > 256:
            printing += str(item)
        else:
            printing += chr(item)
    print(printing, end="")

36 bytes (SBCS)

 ¿®n21®t{:©n≠©t0≠*|:©n$%[1|0]®t1+}©t.

Try it online!

-7 bytes by not using a variable to keep track of the count.

Explained

¿®n21®t{:©n≠©t0≠*|:©n$%[1|0]®t1+}©t.
¿®n                                 #Take the number to check and store it in variable n
   2                                #This will act as the divisor counter
    1®t                             #This will act as the return value, indicating the primality
       {:©n≠©t0≠*|                  #While the counter isn't equal to n and there isn't a divisor yet
                  :©n$%             #Take the counter and number, then swap for modulus
                       [1|0]®t      #Depending upon the result set t to 1 if it doesn't divide otherwise 0
                              1+}   #Increment the counter
                                 ©t.#Print the result

43 bytes (SBCS)

¿®n2®c1®t{©c©n≠©t0≠*|©n©c%[1|0]®t©n1+®c}©t.

It's a real ugly mess, but it works. I'll explain it all later. Also, doesn't work on TIO due to a bug that I found. It should work soon however.

Use the latest github interpreter

Help, WarDoq!, 1 byte

p

Outputs 1 if the input is prime (positive or negative, differs from the other solution), 0 otherwise.

LCGFuck inputNumeric=true, 138 bytes

(Will turn this into a GitHub repository soon)

1 1im1-1
1 1om2-1
1 1om1 1
<{>>>o+1 1m0<<om
<}>>1-1om0>+om
<<<++1 1 1 32
1 4 12 69 4
1 1 7 78 2
{>>>+++++c+c+++++c+++<<c<{+}}>>>c++c<c+c+c

Try it online through this TIO JS interpreter

A brainfuck variant invented by me but uses a list of linear congruential generators (LCGs) instead of cells.

The \$N=1\$ case took too much more bytes to deal with.

Ungolfed and Explanation

1 1 im 1 -1                    # Storage for the input, since the input can only be retrieved once
1 1 om 2 -1                    # Used to prevent wrapping. Necessary for handling N = 1 case
1 1 om 1 1                     # Counts up from 2 to N
<{                             # While N % counter == 0 (If N == 1 the loop is skipped)
 >>>o+                         #  Gets and increments the counter value
 1 1 m 0 <<om                  #  Use a new LCG to check N % counter
<}                             # Loop
>>
1 -1 om 0 >+om                 # The output of this LCG will be 2 if N is prime
<<<++                          # Move two states forward (2 - 2 = 0 if prime)
1 1 1 32                       # LCG for space
1 4 12 69 4                    # LCG for E, I, M
1 1 7 78 2                     # LCG for N, O, P, R, T
{>>>+++++c+c+++++c+++<<c<{+}}  # Output "NOT " if this LCG is not at state 0
>>>c++c<c+c+c                  # Output "PRIME"

Technical Details

(Copied from my obsolete challenge proposal on an LCGFuck interpreter)

An LCG is defined with 5 numbers, like 12345 678 90 -123 45. The last two numbers are optional and default to 0.

LCGFuck has 3 storage variables, the LCG list, the number list and the number memory. The functions are as follows:

• LCG list: Cyclic list that stores all LCGs created. Every entry is in turn a list of 5 numbers in the order [a, b, c, d, e] as notated in the introduction. It has a pointer that controls which LCG is chosen at the moment, and moves in a cycle through the list.
• Number list: Ordinary list that stores the numbers for LCG definition. It can store at most 5 numbers.
• Number memory: A single variable that can be read and written with an input or an LCG output.

LCGFuck has 14 operators, namely:

• \n (newline): Creates an LCG with the numbers in the order of [a, b, c(, d(, e))] and clears the list if the number list contains 3 or more numbers. No-op if the number list contains no more than 2 numbers.
• <: Shifts to the previous LCG circularly (back to the last when moving from the first).
• >: Shifts to the next LCG circularly (back to the first when moving from the last).
• +: Moves the current LCG to the next state (calculates x' = (a * x + b) mod c)
• c: Prints the output of the current LCG as a character (with the output as the codepoint).
• n: Prints the output of the current LCG as a number (with a trailing space)
• o: Writes the output of the current LCG to number memory
• i: Reads a value from the input and writes it to number memory. There is two input mode, one reading a character one time (inputNumeric=false), and one reading a number one time (inputNumeric=true)
• s: Reads the value from number memory and seeds the current LCG with it
• m: Reads the value from number memory and pushes it to the number list
• []: Output loop. Executes the loop if the current LCG is non-zero
• {}: State loop. Executes the loop if the state of the current LCG is non-zero

An integer, optionally with a negative sign at the front, pushes the number to the number list. Any characters other than the newline \n and any of -0123456789[]{}<>+cimnos are no-ops.

The code runs linearly from the first characters, except when loop ends are encountered. Loops can be nested but must be paired accordingly from the innermost loop to the outermost loop.

C# (Visual C# Interactive Compiler), 62 bytes

int n=int.Parse(ReadLine()),i=2;while(n%i>0&i++<n);Write(n<i);

Try it online!

W d, 5 bytes

(Possibly the only <=5-byter that does not use a prime or number factorization built-in?) (The two spaces here represent a tab)

àTéBΦ

repr'd:'‡T\tB⑸'

Unpacked:

m!Wk2=

Explanation

This is really difficult to read, so an explanation will be nice.

    W    % (implicit) Foreach the inclusive range from 1 to the input:
bam      % The "bam" magic! Just kidding. Evaluates b % a
         % Since b is out-of-bounds, this takes the upper-level input
         % as the operand.
   !     % Remove those that aren't valid multiples.
     k   % Is the length of the array ...
      2= % ... equal to 2?
         % i.e. primes have exactly 2 factors: 1 and itself

APL, 9 chars/bytes

2≡≢∪∨∘⍳⍨⎕

get the input

⎕

compute least common divisor between n and all integers from 1 to n

∨∘⍳⍨

count of unique values

≢∪

if it's exactly 2, then it's prime

2≡

Symbolic Raku, 17 bytes

$_=?($_%%[^] ^$_)

Try it online!

Suprisingly, this is shorter than the my previous Raku answer, though one byte longer than using the built-in

Explanation:

$_=                # Set the output to
   ?(           )  # The boolean of
     $_            # If the input is
       %%          # Divisible by
         [^]       # Only one of
             ^$_   # The range from 0 to input-1

tq, 10 bytes

?-1!xp*p%?

Explanation

Uses Wilson's theorem to do the prime-checking.

?-1!        # Generate all numbers from 2 to input - 1
    x,      # Preserve this value, prevent it from being printed
      p*p   # Generate all possible combinations of those numbers
         %? # Does the product of any combination equal to the input?

Spice, 93 bytes

;i;m;t;c;r@REA i;ADD 0 1 c;SUB i 1 m;ADD c 1 c;MOD i c t;SWI t 1 9;SWI c m 3;ADD 0 1 r;OUT r;

This outputs [1] for a prime, and [] for a non-prime.

Un-golfed explanation:

;i;m;t;c;r@ - Declare vars (@ marks end of declarations)
(line 0) REA i;      - Read input into i
(line 1) ADD 0 1 c;  - Set counter c = 1
(line 2) SUB i 1 m;  - Set store input-1 as m
(line 3) ADD c 1 c;  - Start of loop, c+=1
(line 4) MOD i c t;  - Store mod of  t=i%c
(line 5) SWI t 1 8;  - if t < 1 (if non-prime, leave loop) to line 8
(line 6) SWI c m 3;  - if c < m continue loop (go to line 3)
(line 7) ADD 0 1 r;  - set result as truthy value - r = 1
(line 8) OUT r;      - output result, r

tinylisp, 23 bytes

There's a library function.

(load library
(prime? 1

(Since tinylisp is incapable of taking user input, "For scoring purposes, submit the program that corresponds to the input 1.")

Try it online!

Here's a 112-byte solution using only the base language, no library functions:

(d D(q((F A N)(i(l A N)(D F(a F A)N)(e N A
(d _(q((F N)(i(D F 0 N)(e F N)(_(a 1 F)N
((q((N)(i(e N 1)0(_ 2 N))))1

The first line defines a function D that takes a factor F, an accumulator A (initially 0), and a number N; it returns 1 if N is divisible by F, 0 otherwise.

The second line defines a function _ that takes a minimum factor F and a number N; it returns 1 if N is coprime to all numbers from F to N-1, 0 otherwise.

The third line constructs an anonymous function that takes a number N; it returns 0 if N is 1, and otherwise calls _ with number N and minimum factor 2. As above, the scored code calls the anonymous function with an argument of 1.

Wren, 48 43 bytes

I feel surprised that I think better when using W instead of Wren. Also, the 1-primalty problem is fixed.

Fn.new{|i|(1..i).where{|x|i%x==0}.count==2}

Try it online!

T-SQL, 116 bytes

WITH t AS(SELECT 2n UNION ALL SELECT n+1FROM t WHERE n<5e4)
SELECT*FROM z,t WHERE p%n=0AND n<p OPTION(MAXRECURSION 0)

There is an Oracle SQL answer here, but couldn't find a Microsoft T-SQL version for this classic question.

Notes:

• Line break is for readability only.
• Returns no rows if prime, returns 1 or more rows otherwise. This is allowed per this output rule.
• Input is taken via pre-existing table \$z\$ with INT field \$p\$, per this input rule.
• Handles values of \$p\$ up to the max value of the INT type, \$2^{31}-1\$

Explanation:

Generates an in-memory number table \$t\$ from 2 to 50k (which exceeds the square root of the max int), then joins to the input table \$z\$ and uses the modulo operator % to test for divisibility. Any values that divide evenly are returned, so an empty result means the input is prime.

OPTION(MAXRECURSION 0) is needed to recursively generate a table with more than 100 rows, unless you've altered this configuration setting on your SQL server.

Optimized for bytes, not speed; checks more values than is strictly necessary.

Ink, 68 51 bytes

-(l)
+(n)[+]
->l
*(r)[{n}]
{n%(r+1)%n:->r|{n==(r+1)}}

Ink was made for writing interactive fiction. It was never meant to be a general-purpose programming language. So it only has one way to recieve input.
Choice prompts.
So the way it works is, if option 2 is labelled with the number you want to check, you pick option 2. Otherwise you pick option 1 to increment option 2's label. So, if you want to check if 15 is prime, you'd input

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2

TIO doesn't handle this, unfortunately.

-17 bytes by using read counts of named options instead of creating variables. This brings the overhead of taking input this way down to something like 24 characters (or even 18 if we don't care about minimising the text from the prompts), compared to the 10 for defining a parametrised stitch and returning from it.

Since full programs can use global variables and read counts, but stitches that have to be reusable can't, using full programs might actually pay off in places where I thought it wouldn't. Neat.

K (oK), 14 19 bytes

Solution:

2=+/d=_d:x%!x:. 0:`

Try it online!

Example:

root@c957fa0dccbd:/ok# echo 1 | node repl.js examples/prime.k
0
root@c957fa0dccbd:/ok# echo 2 | node repl.js examples/prime.k
1
root@c957fa0dccbd:/ok# echo 5 | node repl.js examples/prime.k
1
root@c957fa0dccbd:/ok# echo 97 | node repl.js examples/prime.k
1

Explanation:

Calculate number of factors for input, if equal to 2, then it's prime.

2=+/d=_d:x%!x:. 0:` / the solution
                0:` / read from stdin
              .     / value (ie convert "123" > 123)
            x:      / store input as x
           !        / range 0..x
         x%         / x divided by ...
       d:           / store as d
      _             / floor
    d=              / d equal to ...
  +/                / sum
2=                  / 2 equals?

C++ (gcc), 85 bytes

#include<iostream>
int main(){int n,d=1;for(std::cin>>n;n%++d%n;);std::cout<<(n==d);}

Try it online!

• -2 bytes thanks to @ceilingcat

Ungolfed

#include <iostream>
int main() {
    int n,d=1;                      
    for (std::cin >> n; n % ++d      // Trial division. If n dividible by d, end.
                          % n        /* No effect when n > 1.
                                        But required to make sure the loop ever ends if n == 1
                                     */
                            );
        ) { /* Empty loop body */ }  /* d is now the lowest number greater than 1 which
                                        divides n (or 2 if n == 1)
                                     */
    std::cout << (n==d);             // If that number is n, n must be prime.

}

Port of my Ink answer. Competitive in multiple other languages. I wasn't going to post this, but I couldn't find a C++ compiler that would compile the existing C++ answer.

Whitespace, 145 137 134 bytes

[S S S N
_Push_0][S N
S _Duplicate][T N
T   T   _Read_STDIN_as_integer_in_heap_0][T T   T   _Retrieve][S S S T  S N
_Push_2][T  S S T   _Subtract][N
T   T   T   T   N
_Jump_to_Label_FALSE_if_negative][S S S T   N
_Push_1][S N
S _Duplicate_1][N
S S N
_Create_Label_LOOP][S N
N
_Discard_top_stack][S S S T N
_Push_1][T  S S S _Add][S N
S _Duplicate][S N
S _Duplicate][S S S N
_Push_0][T  T   T   _Retrieve_heap_at_0][T  S S T   _subtract][N
T   S T N
_Jump_to_Label_TRUE_if_0][S S S N
_Push_0][T  T   T   _Retrieve_heap_0][S N
T   _Swap_top_two][T    S T T   _Modulo][S N
S _Duplicate][N
T   S T T   N
_Jump_to_Label_FALSE_if_0][N
S N
N
_Jump_to_Label_LOOP][N
S S T   N
_Create_Label_TRUE][S S S T N
_Push_1][T  N
S T _Output_1][N
N
N
_Exit][N
S S T   T   N
_Create_Label_FALSE][S S S N
_Push_0][T  N
S T _Output_0]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Outputs 1 if a prime, 0 otherwise.

Try it online (with raw spaces, tabs, and new-lines only).

General explanation:

1. Read input
2. Is it less than 2: Return 0
3. Integer i=1
4. Start loop
   • 5) Increase i by 1
   • 6) If the input and i are equal: Return 1 (last iteration of the loop)
   • 7a) Is the input modulo i 0: Return 0
   • 7b) Else: Go back to step 5

Example run (with 5 as input):

Command   Explanation                   Stack       Heap    STDIN   STDOUT

SSSN      Push 0                        [0]         {}
SNS       Duplicate (0)                 [0,0]       {}
TNTT      Read STDIN as number          [0]         {0:5}   5
TTT       Retrieve heap at 0            [5]         {0:5}
SSSTSN    Push 2                        [5,2]       {0:5}
TSST      Subtract (5-2)                [3]         {0:5}
NTTTTN    Jump to Label_FALSE if neg.   []          {0:5}
SSSTN     Push 1                        [1]         {0:5}
SNS       Duplicate (1)                 [1,1]       {0:5}
NSSN      Create Label_LOOP             [1,1]       {0:5}
 SNN      Discard top                   [1]         {0:5}
 SSSTN    Push 1                        [1,1]       {0:5}
 TSSS     Add (1+1)                     [2]         {0:5}
 SNS      Duplicate (2)                 [2,2]       {0:5}
 SNS      Duplicate (2)                 [2,2,2]     {0:5}
 SSSN     Push 0                        [2,2,2,0]   {0:5}
 TTT      Retrieve heap at 0            [2,2,2,5]   {0:5}
 TSST     Subtract (2-5)                [2,2,-3]    {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [2,2]       {0:5}
 SSSN     Push 0                        [2,2,0]     {0:5}
 TTT      Retrieve heap at 0            [2,2,5]     {0:5}
 SNT      Swap top two (2,5] -> 5,2])   [2,5,2]     {0:5}
 TSTT     Modulo (5%2)                  [2,1]       {0:5}
 SNS      Duplicate (1)                 [2,1,1]     {0:5}
 NTSTTN   Jump to Label_FALSE if 0      [2,1]       {0:5}
 NSNN     Jump to Label_LOOP            [2,1]       {0:5}

 SNN      Discard top                   [2]         {0:5}
 SSSTN    Push 1                        [2,1]       {0:5}
 TSSS     Add (2+1)                     [3]         {0:5}
 SNS      Duplicate (3)                 [3,3]       {0:5}
 SNS      Duplicate (3)                 [3,3,3]     {0:5}
 SSSN     Push 0                        [3,3,3,0]   {0:5}
 TTT      Retrieve heap at 0            [3,3,3,5]   {0:5}
 TSST     Subtract (3-5)                [3,3,-2]    {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [3,3]       {0:5}
 SSSN     Push 0                        [3,3,0]     {0:5}
 TTT      Retrieve heap at 0            [3,3,5]     {0:5}
 SNT      Swap top two (3,5] -> 5,3])   [3,5,3]     {0:5}
 TSTT     Modulo (5%3)                  [3,2]       {0:5}
 SNS      Duplicate (2)                 [3,2,2]     {0:5}
 NTSTTN   Jump to Label_FALSE if 0      [3,2]       {0:5}
 NSNN     Jump to Label_LOOP            [3,2]       {0:5}

 SNN      Discard top                   [3]         {0:5}
 SSSTN    Push 1                        [3,1]       {0:5}
 TSSS     Add (3+1)                     [4]         {0:5}
 SNS      Duplicate (4)                 [4,4]       {0:5}
 SNS      Duplicate (4)                 [4,4,4]     {0:5}
 SSSN     Push 0                        [4,4,4,0]   {0:5}
 TTT      Retrieve heap at 0            [4,4,4,5]   {0:5}
 TSST     Subtract (4-5)                [4,4,-1]    {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [4,4]       {0:5}
 SSSN     Push 0                        [4,4,0]     {0:5}
 TTT      Retrieve heap at 0            [4,4,5]     {0:5}
 SNT      Swap top two (4,5] -> 5,4])   [4,5,4]     {0:5}
 TSTT     Modulo (5%4)                  [4,1]       {0:5}
 SNS      Duplicate (1)                 [4,1,1]     {0:5}
 NTSTTN   Jump to Label_FALSE if 0      [4,1]       {0:5}
 NSNN     Jump to Label_LOOP            [4,1]       {0:5}

 SNN      Discard top                   [4]         {0:5}
 SSSTN    Push 1                        [4,1]       {0:5}
 TSSS     Add (4+1)                     [5]         {0:5}
 SNS      Duplicate (5)                 [5,5]       {0:5}
 SNS      Duplicate (5)                 [5,5,5]     {0:5}
 SSSN     Push 0                        [5,5,5,0]   {0:5}
 TTT      Retrieve heap at 0            [5,5,5,5]   {0:5}
 TSST     Subtract (5-5)                [5,5,0]     {0:5}
 NTSTN    Jump to LABEL_TRUE if 0       [5,5]       {0:5}

NSSTN     Create Label_TRUE             [5,5]       {0:5}
SSSTN     Push 1                        [5,5,1]     {0:5}
TNST      Output top as number          [5,5]       {0:5}          1
NNN       Stop program                  [5,5]       {0:5}

dc, 17 22 bytes

?d*5+v[dz%rdz<M*]dsMxp

Try it online!

I've been on a bit of a dc kick lately and although there's already a dc solution here, this is 10 5 bytes shorter. It follows the I/O request of the original question, which does add two bytes for the explicit input and output (rather than the usual rules these days that allow implicit stack I/O), but okay.

This outputs zero for composite numbers and non-zero for primes.

How it works: this program builds a stack consisting of the modulo of the input with the current stack size (so the stack looks like, from bottom to top, i%2, i%3, i%4, ...), then when it decides it's gone far enough (stack size = input) it multiplies the stack as it unwinds the recursion.

Alchemist, 126 bytes

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

Try it online!

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

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

Explanation:

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

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

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

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

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

Symbolic Python, 48 bytes

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

Try it online!

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

Explanation:

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

C#, 116 bytes

Non fancy full program entry (cherry-picking some stuff from java):

class P{static void Main(string[] a){int i=2,n=int.Parse(a[0]);for(;i<n;)n=n%i++<1?0:n;System.Console.Write(n>1);}}

Gol><>, 4 bytes

ISPh

Thanks to ASCII-only for letting me now I didn't need 2 bytes, since it was redundant.

Try it online!

05AB1E, 3 bytes

fнQ

find all factors and see if last one equals input.

Try it online!

F#, 79 84 bytes

Fixed as per Dennis's suggestion.

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

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

Original submission:

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

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

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

Pepe, 53 bytes

Uses trial-and-error modulus, so gets slower in larger integers.

REeEREErEEEEErREEeEeEReeREEEEeEeEReRererrEEreEErEeree

Try it online! Outputs 0 for truthy and none for falsy.

Perl 6, 20 bytes

say get~~$_%%one ^$_

Try it online!

There's also the built-in is-prime, but I thought it would be more interesting to do it without it. Surprisingly, this is only 4 bytes longer.

Explanation:

    get                # Get a line of input
       ~~              # Smartmatch it by setting $_ to input
         $_%%          # Is input divisible by
             one       # Only one of
                 ^$_   # The range 0 to input-1?
say                    # And print

Note that this works because n%%0 is boolified to False.

Cardinal, 24 21 bytes

Thanks to @Jo King for golfing off 3 bytes

Code:

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

Try it online!

Explanation:

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

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

Pixiedust, 59 bytes

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

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

Explanation

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

Elixir, 75 72 bytes

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

Try it online!

Pip, 10 8 bytes

1=0Na%,a

Try it online! (testing numbers 0 through 29)

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

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

Yabasic, 43 bytes

Input""n
For d=2To n
p=p+!Mod(n,d)Next
?p=1

Try it online!

Flobnar, 25 bytes

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

Try it online!

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

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

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

Foam, 9 bytes

;# #.% .#

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

Outputs 1 for prime and 0 for nonprime.

Foam has a prime checking builtin.

;#   <- read number
#.%  <- is number prime?
.#   <- output number

Julia 0.6, 44 bytes

n=parse(Int,ARGS[]);show(sum(n%(1:n).<1)==2)

Try it online!

Since the existing answers are invalid for the challenge and/or outdated by newer Julia versions, I'm adding a Julia answer that works in Julia 0.6.

For Julia 0.7 (and to avoid deprecation warnings in 0.6), this needs just one more byte (% becomes .%):

45 bytes

n=parse(Int,ARGS[]);show(sum(n.%(1:n).<1)==2)

Try it online!

Scala, 40 bytes

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

Try it online!

GNU sed -r, 19 18

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

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

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

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

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

Elixir, 122 bytes

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

Try it online!

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

Z80Golf, 30 bytes

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

Try it online!

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

Disassembly:

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

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

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

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

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.

Racket, 67 42 bytes

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

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

Previous (and much more complicated) version:

((λ(l)(or(= l 1)(ormap(λ(x)(=(modulo l x)0))(range 2 l))))(read))

Pyret, 58 bytes

i=1
(i == 1) or any({(x):num-modulo(i,x) == 0},range(2,i))

You can try this online by copying the code into the online Pyret editor!

Pyret programs are designed to be run in the online editor, so there's no way to read from STDIN. Here, the variable i represents the input. The program returns true if i is not prime and false if i is prime.

Reality, 1 byte

P

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

Alternate :

If taking input is not allowed then

p number

space is not required (replace number with your number)

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

Procedural Footnote Language, 41 bytes

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

Explanation

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

J, 19 17 Bytes

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

Explanation:

echo(p:[:".1!:1)1  | Full program.
echo(          )   | Hook: (f g) y is evaluated as y f (g y)
       [:".1!:1    | Right verb in the hook
           1!:1    | With argument 1, reads a line of input
         ".        | Evaluate, converts valid string to int
       [:          | Cap, treat these two verbs as one
     p:            | With a left argument of 1, as supplied by the hook, tests primality of its right argument
echo               | Print

Python 2, 51 bytes

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

Try it online!

Go, 231 bytes

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

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

The main code is blatantly stolen from this playground example.

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

Try it online!

Python 3, 42 55 bytes

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

Try it online!

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

Befunge-93, 28 bytes

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

Try it online!

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

How It Works:

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

Forth, 82 65 bytes

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

Ungolfed:

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

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

Run it!

Befunge 93, 33 bytes

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

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

Interpreter here.

Whispers v2, 27 bytes

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

Try it online!

Whispers v1, 27 bytes

> Input
>> 1’
>> Output 2

Try it online!

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

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

Try it online!

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.

Triangularity, 7 bytes

.).
IEp

Try it online!

Triangularity, 49 bytes

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

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

Try it online!

How it works?

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

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

Quarterstaff, 94

golfed 1!

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

Try it online!

How it works:

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

value starts as 0

10 add 10 to value

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

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

the first loop:

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

- multiply value by -1

38 add 38 to value

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

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

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

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

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

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

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

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

another while loop

[ begin the loop

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

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

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

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

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

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

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

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

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

c value = c (because value was 0 before)

] close nested loop.

back to the not modulus part

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

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

] close outer loop

tying up

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

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

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

Forked, 57 54 bytes

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

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

• Try it online! - less redundant code
• Try it online! - less redundant code and some cool wrapping behavior

Short explanation

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

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

Long, thorough explanation

Before we begin, let us define two values:

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

Here's the program's control flow:

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

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

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

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

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

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

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

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

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

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

><>, 23 22 bytes

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

Try it online!

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

How it Works:

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

Zephyr, 88 bytes

input n as Integer
set f to 0
for i from 1to n
if(n mod i)=0
inc f
end if
next
print f=2

Try it online!

Uses the "n must have exactly two perfect divisors in the inclusive range [1, n]" approach. Run a for loop over that range, count the numbers i for which n mod i is zero, and output at the end whether the count equals 2.

K, 23 bytes

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

yay for algorithmic improvements!

Explanation

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

x:0$0:`

reads the input and saves the result to the variable x

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

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

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

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

q, 35 34 bytes

Haven't golfed much yet, but we can drop 2 bytes easily if we're allowed to return nothing for 1 and 2. Really, the language truly shines in code golf where the seemingly golfed code is just idiomatic q. Using q instead of k lets us use min, mod and til operators to save some bytes.

Having to read STDIN isn't much idiomatic q, and costed us 11 bytes.

-> I was able to save a byte due to on-the-fly assignments which I forgot about

0>min 1,x mod/:2_til x:"I"$read0 0

Explanation

code is executed right-to-left

"I"$read0 0 reads STDIN, and then casts it to an integer

{..} denotes an anonymous function with x as an implicit variable, applied to the integer

til x returns a range 0..(x-1)

2_ drops 0 and 1, which are not needed for prime checking

1,x mod/: then takes mod of x with every element of the list and prepends a 1 to the list due to 1 and 2 returning empty list

0<min takes the minimum of the mods, and checks if it is bigger than zero. If it is, then it must be a prime!

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

Pyt, 1 byte

ṗ

Try it online!

Implicit input
ṗ   primality test
Implicit output

Forth (gforth), 73 61 57 bytes

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

Try it online!

Stack-Only variant, 76 68 64 61 bytes

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

Try it online!

Explanation

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

COBOL (GNU), 305 bytes ( +5 for compiler flags)

ID DIVISION.PROGRAM-ID.A.DATA DIVISION.WORKING-STORAGE SECTION. 1 I PIC 9(9). 1 V PIC 9(9). 1 R PIC 9(9). 1 Q PIC 9(9). 1 P PIC 9 VALUE 1.PROCEDURE DIVISION.ACCEPT V PERFORM VARYING I FROM 2 BY 1 UNTIL I=V DIVIDE I INTO V GIVING Q REMAINDER R IF R=0 THEN MOVE 0 TO P END-IF END-PERFORM DISPLAY P STOP RUN.

Compile with -free flag. (This allows ignoring formatting.)

Try it online!

Ungolfed version:

IDENTIFICATION DIVISION.    *> Required in every program header.
PROGRAM-ID. A.

DATA DIVISION.
WORKING-STORAGE SECTION.
    01 I PIC 9(9).          *> Loop index
    01 V PIC 9(9).          *> Value to test
    01 R PIC 9(9).          *> Remainder
    01 Q PIC 9(9).          *> Quotient
    01 P PIC 9 VALUE 1.     *> Is prime?

PROCEDURE DIVISION.
    ACCEPT V                                    *> Get value from input
    PERFORM VARYING I FROM 2 BY 1 UNTIL I>V/2   *> for (i = 2; i <= v/2; i++)
        DIVIDE I INTO V GIVING Q REMAINDER R    *>     Q = V/I; R = remainder(V/I)
        IF R=0 THEN MOVE 0 TO P END-IF          *>     If remainder is zero, not prime
    END-PERFORM
    DISPLAY P               *> Output result (1 or 0)
    STOP RUN.

SmileBASIC, Forty Four 43 bytes

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

Just checks if the number has exactly 2 divisors.

Stax, 2 bytes

|p

Run and debug online!

Added for completeness. An internal.

Wumpus, 13 bytes

I=&l2-&*=*r%O

Try it online!

Explanation

Uses Wilson's theorem in the form (n-1)!² ≡ isprime(n) (mod n) (where isprime gives 0 or 1, respectively).

The implementation doesn't really work the way it's supposed to for n = 1, but the result still ends up being 0.

I=  Read n and duplicate it.
&l  Push the stack depth n times. Since there's another copy of n on the stack to
    begin with, this pushes 1, 2, ..., n-1, n.
2-  Subtract 2 from n.
&*  Multiply the top two numbers that many times. This essentially folds
    multiplication over the range [1,n-1], which computes (n-1)!. At
    the end of this, the stack will be [n, (n-1)!]. However, in the case
    of n = 1, we only ever pushed one element for the range, so there's
    nothing left to form the factorial and the stack contains only one
    copy of 1.
=*  Square the (n-1)!.
r   Reverse the stack. This is normally just used to swap n and (n-1)!²,
    but we're using stack reversal instead of swap (~), so that the stack
    remains unchanged for n = 1.
%   Modulo. For n = 1, this computes 0 % 1 = 0 (because there's an implicit
    zero underneath the 1 on the stack). For all other n, this computes
    (n-1)!² % n, i.e. the result of the primality test.
O   Output the result as a decimal integer.

The IP then bounces off the end of the program and starts moving left again. % tries another modulo, but there's only implicit zeros on the stack, so the program ends due to the attempted division by zero.

17, 102

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

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

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

Expanded:

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

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

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

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

Block 2: Load 2 and print, then exit

Block 5: Print 0 and exit

095, 35 bytes

1Xid1.=(DD,,{d_.%(yX]D}dYs]D1.=[1s]

Returns 0 for composite and 1 for prime.

Explanation:

1X                                  ~ Set True to X
  id                                ~ Take input and duplicate
    1.=                             ~ Check if equal to 2
       (DD                          ~ If not, delete last two items
          ,,                        ~ Subtract 2
            {                       ~ For that many times,
             d_.%                   ~ see if iterator divides into input
                 (yX]               ~ If it does, set False to X
                     D}             ~ Delete last item, close loop
                       dYs]         ~ Duplicate input, print X
                           D1.=[1s] ~ If input = 2, say True

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

Implicit, 30 29 21 bytes

<2è;:(-1>1?{;|_ñè};).

Try it online!

Whew, another 10 bugs uncovered during the writing of this program. This uses trial division.

While SimpleStack uses a ... stack, I'm going to call two stack values variables. The input will be variable i and the trial-division loop counter will be variable m. Note I might've messed up this explanation somewhere along the road of golfing.

<2è;:(-1>1?{;|_ñè};).
                       implicit input i
<2                     push i < 2
  è                    exit without implicit output if truthy
   ;                   pop i < 2
    :                   set m to input
     (.............)    do
      -1                 decrement m
        >1               push m > 1
          ?{.....}       if true
            ;             pop m > 1
             |            duplicate stack (stack: i, m -> i, m, i, m)
              _           push i % m
               ñ          compute logical NOT on i % m (truthy if i % m falsy)
                è         exit without implicit output if truthy
                  ;      pop top of stack (NOT(i % m) or m > 1)
                   )    while m > 0
                    .   increment

If the input is 0 or 1, it will print nothing, so the output will be falsy. If the input is not prime, the second è exits without implicit output (making hte output empty and therefore falsy). If the input is prime, it will reach the end of the program, and the top of stack will always be 0. . increments it, turning it to 1 (truthy). Implicit output.

Broccoli, 107 bytes

(fn p ($a) (:= $d 0) (for $i in (range 2 $a) (if (= $a (* $i (int (/ $a $i)))) (:= $d (+ $d 1)))) (= $d 1))

With whitespace added:

(fn p ($a)
    (:= $d 0)
    (for $i in (range 2 $a)
        (if (= $a (* $i (int (/ $a $i))))
            (:= $d (+ $d 1))
        )
    )
    (= $d 1)
)
(map p (range 1 20))

This language is a bit of a pain to work with:

• You can't take input.

• You can't define a function from within a function.

• You can't pass a lambda to a map or reduce or a filter.

• There is no modulo function.

I'm sure this could be shorter somehow, but I'm just not seeing it.

SNOBOL4 (CSNOBOL4), 105 bytes

	N =INPUT
	X =1
	GT(N,1)	:F(C)
I	X =X + 1
	OUTPUT =EQ(X,N) 1	:S(END)
C	OUTPUT =EQ(REMDR(N,X)) 0	:F(I)
END

Try it online!

I thought about putting my explanation in all caps, but that would just look silly.

This is the brute force approach: Test if N==1, and output 0 on success, then increment X. If we reach a point where X==N, then we have found a prime number and we output 1 and terminate. If we reach a point where N %% X == 0, then we output 0.

I am still learning to golf in SNOBOL, so I think it should be possible to make this shorter.

Swift 4, 58 bytes

let n=Int(readLine()!)!;print((1..<n).filter{n%$0<1}==[1])

Try it online!

Saved a few bytes thanks to Dennis.

Jolf, 2 bytes

Try it here!

m{

Simple. m{ is the isPrime function of the math module, and j is the (implicit) user input as a number.

AnyDice, 68 bytes

function: p A {loop N over {2..A/2}{if A/N*N=A {result:0}}result: 1}

I was wondering if AnyDice counted as a language for PCG.se purposes, and it turns out it does,

This is trial division, making use of the fact that AnyDice only supports integer (truncating) division.

usage:

TryIt

output [p 333332]

outputs 0(100%)

output [p 333331]

outputs 1(100%)

Julia, 15 7 bytes

isprime

knocked down 8 bytes thanks to caird coinheringaahing

><>, 46 Bytes

i> :1\/ln;
~\?:-/^?(2l~
%$}:{<;n0/?
l1- ?/1n;\

Takes input as an ascii character, prints 1 for primes, 0 for non-primes, including 1. Loops forever if input is 0 or negative.

How it works:

 > :1\
 \?:-/

Fills the stack with integers between 0 and input, inclusive.

      /ln;
~    /^?(2l~

Removes the top two values on the stack, 0 and 1. Tests if the length of the stack is <2; if it is, the value is either 1 or 2. In either case, its truthy/falsy value is the length of the stack; print it. If the length is greater than 2, it continues to the next loop.

%$}:{<;n0/?
l1- ?/1n;\

Duplicates the value being tested from the bottom of the stack. Test if it's divisible by the value at the top. If it is, print 0. Otherwise, check that the stack length is not 1. If it is, the value being tested is prime; print 1.

Edit:

Added on to this program a bit, as a part in my attempt to conquer as much of project euler as possible in ><>.

This is for Project Euler 7: Calculating the 10001st prime

a:::***31[\>?!/l1-?\]r1-:?!/r:nao1+70.
\/{*::+1<0<\%$}:{  <~~
 \:}(?!\/-1l  \         ;nr\
\!?:-1:<\ ?!\~^.38
            \] 1+70.

Comes in at 130 Bytes, although I didn't try very hard to golf it. Pushes 10000 to the stack (since we start at 3), makes a new stack, runs the primality test on the number, starting at 3. If it's prime, decrement the counter and increase the value being tested. If its not prime, just increment the value.

The go-fish interpreter was a life saver for this--it ran orders of magnitude faster than fish.py.

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:

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:

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

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.

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:

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:

_{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.}

Groovy, 92 91

i=System.in.newReader().readLine()as int
print i==2||i>1&&!(true in(2..i-1).collect{i%it<1})

Such a verbose way to read from stdin...

Common Lisp, 64 bytes

(print(=(loop as x from 1 to(setq n(read))count(=(rem n x)0))2))

Try it online!

57 bytes in Common Lisp REPL:

(=(loop as x from 1 to(setq n(read))count(=(rem n x)0))2)

Funky, 39 bytes

n=>{o=1for(i=2;i<n;i++)o=o&0<n%i o&n>1}

Try it online!

Taxi, 1519 1309 bytes

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

Try it online!

Un-golfed with comments:

[ Test for Primality ]
[ Inspired by: https://codegolf.stackexchange.com/q/57617 ]

[ Pickup stdin and triplicate it]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left 2nd right.
Pickup a passenger going to Cyclone.
Pickup a passenger going to The Underground.
Go to Zoom Zoom: north.

[a]
Go to Cyclone: west.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Divide and Conquer.

[ Store a copy of the original stdin ]
Go to Sunny Skies Park: north 1st right.

[ Iterate down to the next lowest number ]
[ If the input is 1, the switch will immediately output '0' ]
Go to The Underground: south 1st left 1st right 2nd left.
Switch to plan "1" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 3rd left 2nd left.
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to The Underground.

[ Divide the original by the current iteration and check if it's an integer ]
Go to Divide and Conquer: north 2nd right 2nd right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: east 1st left 1st left 2nd left.
Pickup a passenger going to Trunkers.
Pickup a passenger going to Equal's Corner.
Go to Trunkers: south 1st left.
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left.
Switch to plan "b" if no one is waiting.

[ Someone was waiting so it was an integer result ]
[ This is going to eventually happen when we divide by one ]
[ If the current iteration is 1, we want to return 1 as a truthy result ]
[ It it's anything higher than 1, we want to return 0 as a falsey result ]
Go to The Underground: north 3rd right 1st right 2nd left.
Switch to plan "z" if no one is waiting.

[1]
'0' is waiting at Writer's Depot.
[z]
'1' is waiting at Writer's Depot.
Go to Writer's Depot: north 3rd left 2nd left.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st right 2nd right 1st left.
[ No need to return to taxi garage or even switch to the end of the program ]
[ It will output to stderr because it can't drive in the next direction and terminate the program ]

[b]
[ No one was waiting so it was not an integer result ]
[ Continue on to the next iteration ]
Go to Sunny Skies Park: north.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north 1st right.
Switch to plan "a".

The only thing that felt golf-y when writing it was allowing it to error out instead of terminate properly.

Python 3, 57 bytes

k=int(input());print(all(k%j for j in range(2,k))and k>1)

I think it's pretty self-explanatory.

Pyth, 3 2 bytes

I can't see a simpler way of doing this. My ignorance continues to amaze me.

P_

Explanation (if it needs one):

P   Prime function: factorization if positive, isPrime if negative
 _  Negate the implicit input

Test suite

TI-BASIC (nspire), 15 bytes

f(n):=isPrime(n

Uses the CAS isPrime() builtin. The environment by default adds an extra parenthesis on the end of the input, making it f(n):=isPrime(n) when the function is defined in the interpreter.

Dyalog APL, 10 9 bytes

2=∘≢∘∪⍳∨⊢

I don't think this one has been posted.

TI-BASIC, 37 bytes

Prompt N
N=1
For(A,2,√(N
Ans+not(fPart(N/A
End
not(Ans

Prompts for N and displays 1 if N is prime or 0 otherwise.

Also in TI-BASIC:

• 12 bytes by Thomas Kwa
• 24 bytes by Zenohm

cQuents, 3 bytes

?pz

Try it online!

Explanation

?     Mode ? (query)
 p    Builtin: next prime after parameter
  z   Previous item in sequence
   )  Implicit closing parenthesis
      

Query mode returns true if the input is in the sequence, and false if it is not.

Add++, 14 17 bytes

D,f,@,P
+?
$f,x
O

Try it online!

10 bytes are boilerplate for the full program requirement.

Function, 7 bytes

D,f,@,P

Fairly basic, just defines a function that performs a primality test

Built-in, 1 byte

P

As functions and main code use both different memory models and different commands, this only works in function mode and so would be invalid.

QBIC, 21 20 3 bytes (nc)

Since the purpose of the challenge is to build a catalog, I feel it's important to keep the QBIC post up-to-date with the current state of the language:

­?µ:

Explanation:

?    PRINT
 µ   QBIC's prime test, returns -1 for primes, 0 otherwise
  :  Read a number from the command line, insert that here
     The function is closed automatically because of EOF.

Previously, at 20 bytes:

:[a|~a%b|\p=p+1}?p<3

Simple trial divider. Every time b (the loop counter) cleanly divides a (our prime-candidate), p is increased. Primes will end with p at 2 (or p=1 for a=1). This then prints -1 for primes, and 0 for non-primes, which are QBasic default values for true and false resp.

Original entry, 21 bytes. This prints 1 for primes, and 0 for others. This feels more 'natural' to me than QBasic's default -1/0. Also, this only does slightly less than a/2 divisions for primes (and quits when it detects a non-prime), instead of doing a divisions regardlessly.

:[2,a/2|~a%b=0|_Xp}?q

Explanation:

:       Get the input number, 'a'
[2,a/2| FOR(b=2, b<=(a/2), b++)
~a%b=0  IF a MOD b == 0     --> Clean division == no prime
|_Xp    THEN exit program, printing 'p' (which never gets set and is 0 by default)
}       Close all language constructs: IF/END IF, FOR/NEXT
?q      We've made it through the FOR loop without division, N is prime.
        In QBIC, 'q' is auto-initialised to 1, '?' prints it.

Ruby 16+15 bytes

require 'prime';p->e{e.prime?}

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
)

APL (NARS2000), 6 bytes

Function: 0∘π

Program: 0π⎕

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"

Alice, 12 11 bytes

/o|\ntdc
@i

Try it online!

Prints 1 for primes and 0 for composite numbers and 1. Here is an alternative solution that prints p-1 for primes instead:

/o|\tzt.
@i

Try it online!

Explanation

/   Send the IP southeast, switching to Ordinal mode.
i   Read all input as a string.
|   Reflect the IP back where it came from.
i   Try reading input again, but this just pushes "".
/   Send the IP west, switching back to Cardinal mode.
    The IP wraps around to the end of the line.
c   Convert the input to an integer and push its prime factors. Pushes nothing
    at all for input 1.
d   Get the stack depth. This is 1 iff the input is a prime.
t   Decrement to give 0 for primes.
n   Logical NOT. Now we have 1 for primes, 0 otherwise.
\   Send the IP southwest, switching to Ordinal mode.
o   Print the result as a string.
@   Terminate the program.

NO!, 34 bytes

This was taken from the NO! GitHub page. It isn't mine

NOOOOOOO?NOOOOOOOOOOO
NOOOOOOOO?no

Samau, 2 bytes

▌τ

Hex dump:

dd ab

Yes, it's 2 bytes. Samau uses CP737 as its default character encoding.

▌       read a number
 τ      test if it is a prime

τ uses the isCertifiedPrime function in the haskell package arithmoi. It's not a probabilistic algorithm.

There's also a 7-bytes answer if built-ins are not allowed:

▌;\│Σ2=

Hex dump:

dd 3b 5c b3 91 32 3d

Most mathematical functions in Samau automatically thread over lists.

▌           read a number, let's call it n
 ;          duplicate
  \         range from 1 to n
   |        return 1 for divisors of n, and 0 for the other numbers
    Σ       take the sum
     =2     if the sum is 2, then it's a prime

√ å ı ¥ ® Ï Ø ¿ , 3 bytes

Ipo

p is the primality test.

PHP, 43 39 54 44 43 bytes

improved my answer from stackoverflow:

for($i=$n=$argv[1];--$i&&$n%$i;);echo$i==1;

Run with -r. prints 1 if argument is prime, empty string else.

loops $i down from $n-1 until it finds a divisor of $n; $n is prime if that divisor is 1.

6 bytes extra for the 1 case. almost happy.

Haskell, 47 52 bytes

main=do n<-readLn;print$n>1&&all((>0).mod n)[2..n-1]

EDIT: I had failed to take 1 into account. Fixed!

Racket 75 bytes

(let p((c 2))(cond[(> c(sqrt n))#t][(= 0(modulo n c))#f][else(p(+ 1 c))]))

Ungolfed:

(define (f n)                 ; COMMENTS: 
  (let loop ((c 2))
    (cond
      [(> c (sqrt n)) #t]     ; if no divisor found till sq root of number, it must be a prime
      [(= 0 (modulo n c)) #f] ; if divisor found, it is not a prime
      [else (loop (add1 c))]  ; try with next number
      )))

Following version is longer but more efficient for checking larger numbers since it keeps & uses previously found prime numbers:

(λ(N)(define(p n(o'(2))(c 2))(cond[(> c n)o][(ormap(λ(x)(= 0(modulo c x)))o)
(p n o(+ 1 c))][else(p n(cons c o)(+ 1 c))]))(= N(car(p N))))

Ungolfed version:

(p=subfunction to build prime number list till n; o= list of prime numbers found; c=current number being checked)

(define f
  (λ (N) 
    (define (p n (o '(2)) (c 2))
      (cond
        [(> c n) o]
        [(ormap (lambda(x) (= 0 (modulo c x))) o)
                (p n o (add1 c)) ]
        [else (p n (cons c o) (add1 c))]))
    (= N (first (p N)))))

Testing:

(f 109)
(f 10)
(f 11)
(f 12)
(f 13)
(f 49)
(f 43)
(f 57)
(f 47)

Output:

#t
#f
#t
#f
#t
#f
#t
#f
#t

Valyrio, 14 bytes

s∫main [ipo]

Outputs 1 if the input is prime. Otherwise outputs 0.

Explanation

s∫ tells the interpreter to enter stack mode

main [ starts the main code block

i takes an input and evaluates it

p pushes 1 or 0 to the stack depending on primality

o outputs the top item on the stack

] ends the main code block

Maverick, 25 bytes

(1:(<>@-1)//$*)%<>@=<>@-1

Try it online!

This is a pretty fun language IMO. Infix and esoteric.

(1:(<>@-1)//$*)%<>@=<>@-1
 1:                         range from 1 to
   (<>@                     first command line arg (<> called with no args)
       -1)                  minus 1
          //$*              folded over multiplication
(             )%            modulus
                <>@         the input
                   =        does the above equal
                    <>@-1   the input minus 1? If so, yields prime

Clojure, 124

Full program, reading standard input and writing to standard output as required by the terms.

(let[n(read-string(first *command-line-args*))](print(and(> n 1)(=(reduce #(* %1(if(=(mod n %2)0)0 1))1(range 2 n))1))))

Obviously inefficient to test all the way up to n but trying to be clever with (range 2 (inc (int (Math/sqrt n)))) adds length.

Ungolfed version:

(let
    [n (read-string (first *command-line-args*))]
  (print
   (and
    (> n 1)
    (=
     (reduce #(* %1
                 (if (= (mod n %2) 0)
                   0
                   1)
                 )
             1
             (range 2 n)
             )
     1
     )
    )
   )
  )

Put in file prime.clj, execute as:

java -cp location-of-clojure.jar-in-your-system clojure.main prime.clj 1

E.g. in my system I get:

$ java -cp ../../repo-wide-libs/clojure.jar clojure.main prime.clj  1
false
$ java -cp ../../repo-wide-libs/clojure.jar clojure.main prime.clj  7
true
$ java -cp ../../repo-wide-libs/clojure.jar clojure.main prime.clj  8
false

Clojure, 98 bytes

(let[n(Integer/parseInt(read-line))](println(and(not= 1 n)(not(some #(=(rem n %)0)(range 2 n))))))

Uses some to check if the number has any divisors, then negates the result to indicate whether or not it's prime.

A simple function would have only been 59 bytes :(

(fn[n](and(not= 1 n)(not(some #(=(rem n %)0)(range 2 n)))))

Ungolfed:

(let [n (Integer/parseInt (read-line))]
  (println
    (and (not= 1 n) ; 1 is an unfortunate special case
         (not ; Negate to indicate primality
           (some #(= (rem n %) 0) ; Check if n has any divsors...
                 (range 2 n)))))) ; in the range of 2 to (n-1)

There's a previous Clojure answer, but this beats it by a little over 60 bytes

Japt, 1 byte

j

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

Japt, 8 bytes

o2 e@U%X

Try it online!

How it works

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

Ceylon, 107 112

That was my first try:

shared void p(){if(exists a=process.readLine(),exists c=parseInteger(a)){print(!(2:c-2).any((d)=>c%d<1));}}

This is a simple trial division of all numbers between 2 and c - 1, using the range operator : and the any method for iterating.

But this will also note 1 as prime. So here the corrected version:

shared void p(){if(exists a=process.readLine(),exists c=parseInteger(a)){print(1<c&&!(2:c-2).any((d)=>c%d<1));}}

That works for numbers up to 2^63-1 ... and takes quite long for larger primes (or composite numbers with large factors) – I think it took about half a minute to confirm 2147483647 (=2^31-1) as prime.

The formatted version:

shared void p() {
    if (exists a = process.readLine(),
        exists c = parseInteger(a)) {
        print(1 < c && !(2 : c - 2).any((d) => c % d < 1));
    }
}

I originally wrote the check as d.divides(c), but the modulo operator is so much shorter.

As a bonus, here is a variant for arbitrary size integers, though there is not really a point in using this due to the slowness.

import ceylon.math.whole {
    w=parseWhole,
    t=two,
    o=one
}
shared void q() {
    if (exists a = process.readLine(),
        exists c = w(a)) {
        print(c == t || !(t .. c - t).any((d) => c % d < o));
    }
}

The : range operator needs an Integer (the number of elements) as a second argument, so we use the .. operator, which takes the same type as the first argument, i.e. here a Whole, as second argument (the upper limit). 2..c-1 is the same as 2:c-2 for large c, but this becomes an empty list for two (and a non-empty list for one), so we need a different exception here than in the Integer version. It becomes mainly longer due to the imports.

The space-reduced version has length 153:

import ceylon.math.whole{w=parseWhole,t=two,o=one}shared void q(){if(exists a=process.readLine(),exists c=w(a)){print(c==t||!(t..c-o).any((d)=>c%d<o));}}

memes, 2 bytes

I decided to hop on the language train. Code:

}"

Explanation:

} //Takes next input.
" //Returns `True` or `False`, representing if the input is prime.

Mini-Flak, 202 bytes

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

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

Try it online

Explanation

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

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

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

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

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

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

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

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

Unary, 165192711826249169871716905363504385377479408598339493836 bytes

Well, basically 165192711826249169871716905363504385377479408598339493836 zeros. Here is a Java program that prints the actual program:

public class Main{
  public static void main(String[]args){
    for(BigInteger i = new BigInteger("165192711826249169871716905363504385377479408598339493836"),BigInteger j = BigInteger.ZERO;j.compareTo(i)!=0;j = j.add(BigInteger.ONE)){
      System.out.println("0");
    }
  }
}

This a port of this Brainfuck answer.

Dip, 1 byte

P

Pretty self-explanatory...

Batch, 121 bytes

set i=2
if %1%==2 exit /b
if %1%==1 echo 0
:b
set /a a=%1%%%i%
set /a i=%i%+1
if %i%==%1% exit /b
if %a%==0 echo 0
goto b

Outputs 0 if it's no prime. This works only for inputs input > 0.

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

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.

Logicode, 601 511 467 bytes

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

Oh my, that is a lot of code.

Here's a rundown of what each circuit does:

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

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

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

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

Logy, 82 bytes

f[X]->X<2&1|X*f[X-1];p[&1]->0<0;p[X]->f[X-1]%X==X-1;main[A]->print[p[atoi[A(1)]]];

I have no idea what I am doing.

Use Wilson's theorem.

Ungolfed code:

factorial[X] -> X < 2 & 1 | X*factorial[X - 1];
prime[&1] -> FALSE;
prime[X] -> factorial[X - 1]%X == X - 1;
main[Args] -> print[prime[atoi[Args(1)]]];

RProgN, 102 Bytes

 'i' asoc true i 1 - ] 1 > while [ 'a' asoc i a / i a // = if [ [ false else [ end a 1 - ] 1 > end [ [

Explanation

 'i' asoc           # Associate the implicit input with i
true i              # Push true to the stack, push i to the stack
1 -                 # Subtact 1 from the top of the stack
] 1 >               # Duplicate the top value of the stack, compare that it's larger than 1
while               # While the top of the stack contains a truthy value
    [               # Pop the top of the stack (The conditional in this case)
    'a' asoc        # Associate the top of the stack with a
    i a /           # Push i divided by a to the top of the stack
    i a // =        # Push i integeral divided by a to the top of the stack, compare the top and underneith the top for equality
    if              # if i/a = floor(i/a), essentially
        [ [ false   # Pop the conditional, and the 'true' we slipped in earlier, push false in in place of it
    else            #
        [           # Pop the conditional anyway
    end             #
    a 1 - ] 1 >     # Subtract 1 from a, duplicate it, and compare that it's larger than 1
end                 #
[ [                 # Pop the conditional, the value of a, which leaves only the bottom value we previously inserted, which is implicitly printed

RProgN doesn't have any method of input as of yet, as such, Any input needs to be written in pure form at the very start of the code, such that 23 'i' asoc .... An Extra byte is added to the score, because a space is required in front of any command.

Turtlèd, 490 487 451 bytes

Turtlèd does not support newlines in code... so oneliner fun!

golfed some bytes for not needing to support 0

Golfed some bytes removing useless code, and some other tricks

?#0#.:l( >;,u,[ :ll[*,l]d],u{*{*r}l' d{ l}[ (*.d)(0'1d)(1'2d)(2'3d)(3'4d)(4'5d)(5'6d)(6'7d)(7'8d)(8'9d)(9.l( .))]u[ r]lu}u2[#[ ;{ l}[ (0u.)(1u'1)(2u'2)(3u'3)(4u'4)(5u'5)(6u'6)(7u'7)(8u'8)(9u'9)dl]ur[ r]l[#[ r]l[ (0'9l( '#;))(1.;)(2'1;)(3'2;)(4'3;)(5'4;)(6'5;)(7'6;)(8'7;)(9'8;)]uuu[*r]{*l}u{*r}'*{*l}:;{ l}[ l]r]' uu[*r]{*r}d]l(*,(*@1)(1@0)'*)u{*' l}:;d[ (0'9l( '#l))(1.d)(2'1d)(3'2d)(4'3d)(5'4d)(6'5d)(7'6d)(8'7d)(9'8d)]r( u[ r]uu)][ [ l]r[ ' r]ul],)

Try it online!

I am most certainly not going to explain this with the annotations for each part of the code, at least not right now.

General explanation:

The program writes 0, takes integer input, if it is not one (if it is, it skips the rest of the code), it writes out two lines of asterisks, removing the zero that was written, one to compare for the prime checking, one to turn into a decimal string. It turns the lower one into a decimal string, then moves the decimal string up one. It writes out a single asterisk into a line above the other for each decrement of the upper decimal string. when goes below zero, the program moves the decimal string back up again, and keeps going on the upper line until it either aligns with the lower line, or goes past it. If it aligns, it sets the character variable to 1, if the character variable has not already been set to one. This is because it has no method to distinguish one when testing divisibility, so this makes it so it has to have more than one factor match. If it has been set to one, it sets it to zero. After it has tested all the numbers from n-1 to 1, it cleans up all the mess that it used to test the primality, then writes the character variable, which will be one if prime, else 0

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.

Ruby, 33 bytes

A little longer than other solutions, but doesn't require flags:

require'prime';p$*[0].to_i.prime?

Can be run putting in a file, say prime.rb:

ruby prime.rb 97

Or directly on the command line:

ruby -e "require'prime';p$*[0].to_i.prime?" 97

PHP, 70 65 bytes

for($i=2;$i<$n=$argv[1];$i++)if(is_int($n/$i)?1:0){echo 0;break;}

Empty output if the number is prime, print 0 if the number is not prime.

Not very original or best answer, but this is it...

Test online

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.

JavaScript (ES6), 54 bytes

for((x=prompt(a=i=1))>1||a--;++i<x;x%i?0:a=0);alert(a)

Outputs 1 for prime, 0 for non-prime. All four JS solutions so far were based on the regex, so I thought I'd be brave and try one without.

Nim, 70 56 bytes

import os,math
let x=1.paramStr.len
echo fac(x-1)^2mod x

Uses Wilson's theorem; that is, x is prime if (x - 1)!² mod x is 1.

Takes input in unary (any character) via the first command-line argument. Outputs 1 if the input is prime, and 0 otherwise. To test:

$ nim c prime.nim
$ ./prime 11111111
0
$ ./prime 1111111
1
$ ./prime 1
0

Note that according to the Nim os docs, this solution will not work on POSIX as paramStr isn't available for some reason.

WolframAlpha, 10 bytes

isprime(n)

R, 19 Bytes

 ->n;sum(!n%%1:n)==2

Starts with a right assign to n. i.e. precede the code with the desired n. then it merely checks primeness of n. Prints TRUE or FALSE implicitly

If you don't like right assign as an input method then for 24 bytes you get:

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

Which assigns within the operator.

If you want explicit answer printing, then for 28 bytes:

 p=function(n)sum(!n%%1:n)==2

PHP, 51 bytes

An alternative PHP answer, but required the GMP extension to be installed:

<?=gmp_strval(gmp_nextprime($argv[1]-1))==$argv[1];

Simply subtracts 1 from the input and compares the nextprime result against the input

CASIO-BASIC, 28 bytes

?->A:For 2->B To A:A Rmdr B=0=>B->A:Next

This prompts for a number, then outputs the number if it is prime, else zero.

I'm not really sure how this works. I originally thought it would output the value from the last assignment (stored in Ans), but then it would output the lowest factor of the number, not zero.

Note: -> and => are ASCII representations of one symbol each (the assign-to and conditional operators).

The size was calculated as the size of this program (60 bytes) minus the size of an empty program (32 bytes).

Python 3.5, 58 52 58 bytes

import math;n=int(input());print(math.factorial(n-1)**2%n)

I unassumed. Thanks Dennis.

I assumed something about the way the input would be given. Thanks daHugLenny.

import math;lambda n:print(math.factorial(n-1)**2%n)

reticular, 6 bytes

in@pp;

A four-byte function:

[@p]

Explanation

in@pp;
i       take input
 n      convert to number
  @p    check for primality
    p   print
     ;  terminate

HTML+CSS, 254+n_max*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 n_max checkboxes with the same name (n_max*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)

RPN, 16 bytes

lambda x isprime

This define a function checking the primality of it's argument.

Call like this:

<number> lambda x isprime eval

Jellyfish, 13 bytes

p|&*!<
 E   i

Try it online!

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

Explanation

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

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

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

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

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

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

Idris, 78 bytes

main:IO()
main=let S n=length!getLine in print$0<(pow(product[1..n])2`mod`S n)

This takes input as a unary string (it uses the string length as input).

Compile this with idris -O3 or you’ll spend forever in Nat-computey hell.

brainfuck, 62 bytes

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

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

Try it online!

Sesos, 28 24 bytes

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

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

How it works

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

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

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

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

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

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

Modulus computation

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

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

  v
  n     0     d     0     0     0

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

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

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

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

We achieve this as follows.

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

Primality test (WIP)

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

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

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

                     v
         n     0     d     0     0     0
   

   where d = n - 1.

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

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

3. Advance to the cell containing n % d.

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

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

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

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

                v            V                 
         0      0     n     d-1   0    0     0  
   

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

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

Sesos, 40 39 bytes

0000000: 16f0be afcf9c 37fcfe 8c19d7 c671d7 668ee3 f57b33  ......7......q.f...{3
0000015: 877bc6 662edb b961ba 8763bc 666e3c 66ec01         .{.f...a..c.fn<f..

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

Background

To identify primes, we use a corollary of Wilson's theorem:

How it works (WIP)

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

set numin
set numout

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

Sesos, 63 62 58 bytes

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

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

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

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

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

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.

brainfuck, 208 202 bytes

This is the code I wrote for my Sesos answer. See that answer for a detailed explanation.

This code assumes input fits in a single cell. Attempting to take input from an empty file must set the cell to zero. It works on an unbounded tape with no wrapping, including one that can go negative. It works for all positive numbers. Output will be a byte with a value of 0 or 1.

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

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

Excel, 41 bytes

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

Takes input from A1.

4 bytes saved thanks to @Joffan!

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.

C, 54 bytes

i;main(j){for(scanf("%d",&i);i%++j;);putchar(49^j<i);}

• Must be run without parameters, so j is initialized to 1.
• Reads from standard input.
• Prints 1 for primes, 0 for composites (no newline).
• Could save 2 bytes with unprintable output - I'm not sure if \x00 and \x01 qualify as falsy/truthy.

Fith, 30 bytes

*math* load line >int prime? .

This language isn't great for golfing...

This uses the prime? function in the *math* library. Here's a version using only builtins, which is pretty much what the library function does:

line >int -> x 2 x range { x swap mod } map all .

Explanation:

line           \ line of input
>int           \ cast to int
-> x           \ set x to the top of the stack
2 x            \ push 2, then x
range          \ range from [2, x)
{ x swap mod } \ anonymous function which calculates x mod its argument
map            \ map that function onto the generated range
all            \ return 1 if everything in the list is Boolean true, else 0
.              \ print the top of the stack

You may be able to tell that this language is just a little bit inspired by Forth. It also takes cues from PostScript, Python, and functional programming.

WistfulC, 381 bytes

if only int n were 0...
wish for "%d", &n upon a star
if n < 2 were true...
    wish "not prime" upon a star
    if wishes were horses...
*sigh*
if only int i were 2...
someday i will be n...
    if n % i were 0...
        wish "not prime" upon a star
        if wishes were horses...
    *sigh*
    if only i were i + 1...
*sigh*
wish "prime" upon a star
if wishes were horses...

Outputs prime if prime, not prime if not prime.

I went for entertainment value more than small size. Here's a golfed, (arguably) less funny version (286 bytes):

if only int n were 0...wish for "%d",&n upon a star
if n<2...wish "0" upon a star
if wishes were horses...*sigh*if only int i were 2...someday i==n...if !(n%i)...wish "0" upon a star
if wishes were horses...*sigh*if only i were i+1...*sigh*wish "1" upon a star
if wishes were horses...

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
$

Scratch, 17 blocks (currently glitchy)

demo

Self-explanatory...
Edit: I fixed 2 bugs. But, if you enter 1, it gets in an infinite loop...

UGL, 26 bytes

id?u:cuul^^/_c=?_=ocd$:_u:

Try it online!

How it works:

id?u:cuul^^/_c=?_=ocd$:_u:
id?u:                       int i = input(); if i==1: i=0;
     cuu                    int test = 2;
        l              _u:  while test != -1:
         ^^/_c=?                if i % test == 0:
                _=o                 print(i==test);
                   cd$              test = -1;

Unipants' Golfing Language, 53 47 bytes

i$cu^d^-l_u^^/%cu%?%d%:_?coc$d$$:__^d^-:_u?cuo:

Try it online!

(It has been implemented as a standard example in the interpreter.)

MATL, 2 bytes

Zp

Try it online!

Takes input implicitly. For positive input, function Zp outputs true (displayed as 1) if the number is prime, ans false (0) otherwise.

Fuzzy Octo Guacamole, 21 bytes

^-!.1C[d2ss.p*.+]s.Zm

Outputs 0 for false, 1 for true. Thanks to @xnor for the algorithm.

Explanation:

^-!.1C[d2ss.p*.+]s.Zm
^                      # Get Input
 -                     # Decrement
  !                    # Set for-loop counter
   .                   # Swap stacks
    1C                 # Set both stacks to [1].  (push 1 and copy to other stack)
      [         ]      # For loop for duration of input - 1
       d2              # Duplicate the top of stack and push 2 after
         ss            # Put them on the other stack, in reverse order.
           .           # Switches stacks
            p          # Power function. x^y (ToS^2)
             *         # Multiply
              .+       # Move back to the other stack and increment
                ]      # (repeat)
                 s.    # Move the ToS over and go with it
                   Z   # Reverse the stack.
                    m  # Modulus, x%y.
                       # (implicit output)

We start with each stack having 1. Let the bottom of one stack be n, the other bottom be P. We multiply P by n^2, and then increment n. Do this n-1 times. Then take P%n.

Sage, 22 bytes

lambda N:N in Primes()

Try it online

LiveCode 8, 708 bytes

on mouseUp
    ask ""
    put p(it) into field "a"
end mouseUp
function p n
    if n is 1 then return false
    repeat with i=2 to n-1
        if n mod i is  0 then return false
    end repeat
    return true
end p
        

This code can be placed inside any button. It will print true or false to a field named a. It should work for small-ish integers, but will probably freeze/crash on anything too large. Byte count is size of saved LiveCode stack with one button and one field and with this code in the button.

Molecule, 3 bytes

Inp

Explanation:

Inp
I   read input
 n  convert to number
  p primality test

Labyrinth, 21 bytes

?
:
}()"{
{: *}{:*{%!

Terminates with an error, with the error message going to STDERR.

Try it online!

Explanation

This uses the same approach based on Wilson's theorem as Sp3000's answer, but I managed to decompose his 3x3 loop into two 2x2 loops which is generally better for golfing Labyrinth.

Labyrinth primer:

• Labyrinth has two stacks of arbitrary-precision integers, main and aux(iliary), which are initially filled with an (implicit) infinite amount of zeros.
• The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.

Now we can look at the code. The program starts with a short linear (vertical) bit:

?   Read input N as an integer and push onto main.
:   Duplicate N.
}   Move one copy over to aux.

The IP is now at a junction, and in fact the small 2x2 block acts as a loop which is traversed in clockwise order:

(   Decrement N. If it hits zero, we exit the loop.
:   Duplicate N.
{}  Move a value over from aux and push it back. Together this does nothing.

So this loop leaves all the numbers from N-1 down to 0 on the main stack. Now there's the single ), which increments that 0 back up to 1, such that all the non-zero numbers on top of the stack will multiply together to (N-1)! (including the special case of 0! == 1).

The next 2x2 block is a loop which performs this multiplication and its traversed in counter-clockwise order. The tricky part is that we need to check the value below the product to see if we're done, otherwise we'd end up losing the product by multiplying it with an implicit 0 below.

"   No-op, does nothing.
*   Multiply the top two values on main.
}   Move the product over to aux, exposing the value below. If that's zero,
    we exit the loop.
{   Pull the product back onto main for the next iteration.

Now the main stack is empty and the aux stack contains (N-1)! on top of N. Time to wrap things up:

{   Pull (N-1)! over from aux.
:*  Duplicate and multiply, squaring the factorial.
{   Pull N over from aux.
%   Take modulo, computing (N-1)!^2 % N.
!   Output the result.

Now the IP hits a dead end and has to turn around. The next thing it tries to execute is % but that would now attempt to compute 0 % 0 which terminates with a division-by-zero error.

Racket, 31 bytes

(require math)(λ(n)(prime? n))

A standard library has a function for it. If we want to keep the import but write our own, we could do this for 51 bytes:

(require math)(λ(n)(equal?(list 1 n)(divisors n)))

On the other hand, if builtins were disallowed, for 64 55 bytes, thanks to @MatthewButterick, we can write our own:

(λ(n)(=(count(λ(i)(=(modulo n(+ i 1))0))(range n))2))

Old one, for 64:

(λ(n)(equal?'(1)(filter(λ(i)(zero?(modulo n i)))(range 1 n))))

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

Pyth, 2 bytes

P_

Try it here!

Pyth now has implicit input!

Pylongolf2, 4 bytes

cnz~

Explanations:

cnz~
c    read input
 n   convert to integer
  z  primality test (beta8+)
   ~ print it.

05AB1E, 1 byte

Code:

p

Explantation:

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

Try it online!

Factor, 56 bytes

Literally ungolfable.

USING: math.primes conv io ;
readln string>number prime?

Gogh, 1 byte

e

Run using:

$ ./gogh oi "e" <input>

The operator e pushes the primality of the TOS. Implicit input and output.

VHDL, 236 bytes

entity e is
port(n:natural;b:out bit);end;architecture a of e is
function p(n:natural)return bit is
begin
if n=1 then
return'0';end if;for i in 2 to n-1 loop
if n mod i=0 then
return'0';end if;end loop;return'1';end;begin
b<=p(n);end a;

The input n is an input port of the entity e; a natural number (starts at 0 for VHDL). b is an output port of entity e; a bit (meaning '1' or '0'). This works by the ever-famous method of trial division, with a special case for 1. This is what it looks like formatted nicely:

entity e is
    port(   n : in natural;
            b : out bit);
end;

architecture a of e is
    function p(n:natural) return bit is
    begin
      if n=1 then
          return '0';
      end if;
      for i in 2 to n-1 loop
          if n mod i=0 then
              return '0';
          end if;
      end loop;
      return'1';
    end;
begin
    b<=p(n);
end a;

Here's the testbench I used for verification:

entity m is
end;

architecture a of m is
    signal i_n : natural := 2;
    signal i_b : bit;

    type int_vector is array(natural range<>) of natural;

    constant primes : int_vector := (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97);

    function is_prime(n : natural) return boolean is
    begin
        for i in primes'range loop
            if n=primes(i) then
                return true;
            end if;
        end loop;
        return false;
    end;
begin
    x:entity work.e port map(n=>i_n, b=>i_b);
    process
    begin
        for i in 1 to primes'right loop
            i_n <= i;
            wait for 10 ns;
            if is_prime(i) then
                assert i_b='1';
            else
                assert i_b='0';
            end if;
        end loop;
        report "finished" severity error; -- error to stop simulation
    end process;
end a;

This is the result.

Reng v.1, 36 39 bytes

This tests if the input is a prime. (+3 bytes because I forgot to check if input = 1)

i:11#x   eqv0n~
x1+#x:x,?v$\
    ~nex$/

All because I forgot to implement member switching. I am rather proud of this, however, because it uses an interesting feature of Reng: you can redefine any character's meaning. In this case, we see constant redefinition.

i takes input, and 1 pushes 1. We also define x as 1 (1#x) and print zero and terminate if the input is 1 (eqv0n~). Then, the pointer is directed to the next line, x1+#x:x,?v$\. (The last character is a NOP for this instance.)

For the first iteration, 1+ increments x, yielding 2. This is where our trial division starts. #x defines x to be the top element of the stack, in this case, 2. : duplicates the TOS, the input element, and x puts down its value, 2 in this case. , is the modulus operator, and yields i % x. If this is zero, we are directed downwards by v. Otherwise, we drop the modulus and redo the line again.

When we are directed downward by v, we meet / which executes the line ~nex$, equivalent in a left-to-right form to $xen~. $ drops a value, x lays down x, and e checks for equality. If they are equal (in the case that x is the input), this is 1. Otherwise, this is 0.

Test cases

The programs pictured are still valid, but fail to handle 1 correctly, unlike the program above.

Is 5 a prime?

Yes!

Is 169 a prime?

No!

Pyke, 2 bytes

_P

If the P function is given a negative number, it returns whether it's prime or not.

Lambda Calculus, 615 bytes

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))

Inspired by the turing machine solution, here is a Lambda Calculus solution! You can test this code in this lambda evaluator, or in this one. The second one stops every 400 reductions so its more stable on big inputs (>11), but the first one is by far the nicest. Just paste the code in the text box and type a number behind it.

For example

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))
4

gives

\x y. y  ;false

And

(\p.(\g.(\x.g(x x))(\x.g(x x)))(\f n d.((\n.n(\x.(\x y.y))(\x y.x))((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))(\x y.x)(((\g.(\x.g(x x))(\x.g(x x)))(\f n m.((\m n.(\l r.l r(\x y.y))((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))m n)((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m) m n))n m))n m)(\x y.x)(((\m n.(\n.n(\x.(\x y.y))(\x y.x))((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)m n))n m)(\x y.y)(f((\m n.n(\n f x.n(\g h.h(g f))(\u.x)(\u.u))m)n m)m)))n d)(\x y.y)(f n((\n f x.n(\g h.h(g f))(\u.x)(\u.u))d))))p((\n f x.n(\g h.h(g f))(\u.x)(\u.u))p))
5

gives

\x y. x ;true

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.

Oracle SQL 11.2, 73 bytes

SELECT SUM(DECODE(MOD(:1,LEVEL),0,1,0))-2 FROM DUAL CONNECT BY LEVEL<=:1;

Return 0 if prime, any other value is false

F#, 99 88 bytes

[<EntryPoint>]
let f a= 
 let i=int a.[0]
 Seq.forall((%)i>>(<)0)[2..i-1]|>printfn"%b";0