# Is this number a prime?

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

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

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

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

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

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

### Input

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

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

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

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

### Output

Output has to be written to STDOUT or closest alternative.

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

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

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

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

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

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

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

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

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

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

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

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

### Catalog

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

## Language Name, N bytes

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

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

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

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

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

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

• Is there a reason for the full program requirement, rather than allowing the full range of default input types? E.g. answering with a function that takes its input as an argument, is currently disallowed? codegolf.meta.stackexchange.com/questions/2447/… Commented Dec 12, 2017 at 6:21
• @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. Commented Dec 12, 2017 at 12:51
• Could a case be made for locking this challenge and posting a new, less restrictive one? Commented Jun 25, 2018 at 12:59
• @Shaggy Seems like a question for meta. Commented Jun 25, 2018 at 13:44
• Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. Commented Jun 25, 2018 at 13:45

# hello, world!, 13

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

# Hexagony, 29 bytes

.?'.).@@/'/.!.>+=(<.!)}($>(<% The readable version of this code is: . ? ' . ) . @ @ / ' / . ! . > + = ( < . ! ) } ($ > ( <
% . . . .
. . . .

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

## Initialization:

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

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

## Special Case n=1:

Print a 0 and terminate

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

## The loop

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

. . . .
) . . . /
' / . . . >
. . . . . . .

. . . .
. . . @ .
. . . ! . .
. . . < . . )
. . $. . < . . . . . . . . . ## Case a%n=0: Print the 0 and terminate (The instruction pointer is running SW and loops to the top to the @ . . . . . . @ . . . . . . . > . . . . . ! . . . . . . . . . . . . . . . . • Holy crap, that's one impressive first post. :) I'll put up the bounty right now (I'll award it in 7 days, to draw some more attention to your answer). Welcome to PPCG! Commented Sep 20, 2015 at 15:17 • Great answer! +1 for "The readable version of this code is: <...>" :-) Commented Sep 21, 2015 at 7:05 # Hexagony, 2189258 55 bytes Notice: This answer has been solidly beaten with a side-length 4 solution by Etoplay. )}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[ The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as Sp3000's Labyrinth answer. After starting out with a hexagon of size 10, I managed to compress it down to size 5. However, I was able to reuse some duplicate code and there are still quite a bunch of no-ops in the code, so size 4 might just be possible. ## Explanation To make sense of the code, we first need to unfold it. Hexagony pads any source code to the next centred hexagonal number with no-ops (.), which is 61. It then rearranges the code into a regular hexagon of the corresponding size: ) } ? } . = ( . . ] = } = ' . } . } ~ . / % * . . & . = & { . < . . . . . . = | > ( < . . } ! = . . . & @ \ [ . . . . . . This is quite heavily golfed with crossing and overlapping execution paths and multiple instruction pointers (IPs). To explain how it works, let's first look at an ungolfed version where control flow doesn't go through the edges, only one IP is used and the execution paths are as simple as possible: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . ! . . . . . . . . . . . . . . . . % . . . . . . . . . . . . . . . . . ' . . . . . . . . . . . . . . . . . . & . . . . . . . . . . . . . . . . . . . { . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . = . . . . . . . . . . . . . . . . . . . . . . } . . . . . . . . . . . . . ) } ? } = & { < . . & . . . . . . . . . . . . . . . . . . . . . > ( < . . . . . . . . . . . . . . . . . . . . = . . } . . . . . . . . . . . . . . . . . . } . . . = . . . . . . . . . . . . . . . . | . . . . | . . . . . . . . . . . . . . . * . . . ) . . . . . . . . . . . . . . . = . . & . . . . . . . . . . . . . . . > } < . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Side note: the above code starts with executing the first line, which is full of no-ops. Then, when the IP hits the north east edge, it wraps to the left-most corner (the )), where the actual code begins. Before we start, a word about Hexagony's memory layout. It's a bit like Brainfuck's tape on steroids. In fact, it's not a tape, but it's a hexagonal grid itself (an infinite one), where each edge has an integer value, which is initially 0 (and as opposed to standard Brainfuck, the values are signed arbitrary-precision integers). For this program, we'll be using four edges: We'll compute the factorial on edge A, count down our input on edge C and store another copy of the input (for the modulo) on edge D. B is used as a temporary edge for computations. The memory pointer (MP) starts out on edge A and points north (this is important for moving the MP around). Now here is the first bit of the code: )}?}=&{ ) increments edge A to 1 as the basis of the factorial. } makes the MP take a right-turn, i.e. move to edge C (pointing north-east). Here we read the input as an integer with ?. Then we take another right-turn to edge D with }. = reverses the MP, such that it points at the vertex shared with C. & copies the value from C (the input) into D - the value is copied from the left because the current value is non-positive (zero). Finally, we make the MP take a left-turn back to C with {. Next, < is technically a branch, but we know that the current value is positive, so the IP will always turn right towards the >. A branch hit from the side acts as a mirror, such that the IP moves horizontally again, towards the (, which decrements the value in C. The next branch, < is actually a branch now. This is how we loop from n-1 down to 1. While the current value in C is positive, the IP takes a right-turn (to execute the loop). Once we hit zero, it will turn left instead. Let's look at the loop "body". The | are simple mirrors, the > and < are also used as mirrors again. That means the actual loop body boils down to }=)&}=*}= } moves the MP to edge B, = reverses its direction to face the vertex ABC. ) increments the value: this is only relevant for the first iteration, where the value of B is still zero: we want to ensure that it's positive, such that the next instruction & copies the right neighbour, i.e. A, i.e. the current value of the factorial computation, into B. } then moves the MP to A, = reverses it again to face the common vertex. * multiplies both neighbours, i.e. edges B and C and stores the result in A. Finally, we have another }= to return to C, still facing the vertex ABC. I hope you can see how this computes the factorial of n-1 in A. So now we've done that, the loop counter in C is zero. We want to square the factorial and then take the modulo with the input. That's what this code does: &}=*{&'%!@ Since C is zero, & copies the left neighbour, i.e. the factorial in A. }=* moves to B and stores the product of the two copies of the factorial (i.e. the square) in B. { moves back to C, but doesn't reverse the MP. We know that the current value is now positive, so & copies input from D into C. ' the MP backwards to the right, i.e. onto A. Remember, the square of the factorial is in B and the input is in C. So % computes (n-1)!^2 % n, exactly what we're looking for. ! prints the result as an integer (0 or 1) and @ terminates the program. Okay, but that was the ungolfed version. What about the golfed version? You need to know two more things about Hexagony: 1. The edges wrap around. If the IP hits an edge of the hexagon, it jumps to the opposite edge. This is ambiguous when the IP hits a corner straight on, so hitting a corner also acts as a branch: if the current value is positive, the IP jumps to the grid edge to its right, otherwise to the one to its left. 2. There are actually 6 IPs. Each of them starts in a different corner, moving along the edge in the clockwise direction. Only one of them is active at a time, which means you can just ignore the other 5 IPs if you don't want them. You can switch to the next IP (in clockwise order) with ] and to the previous one with [. (You can also choose a specific one with #, but that's for another time.) There are also a few new commands in it: \ and / are mirrors like |, and ~ multiplies the current value by -1. So how does the ungolfed version translate to the golfed one? The linear set up code )}?}=&{ and the basic loop structure can be found here: ) } ? } . -> . . . . . . . . . . . . . . . . . . . . . -> . = & { . < . . . . . . . . > ( < . . . . . . . . . . . . . . . . . . Now the loop body crosses the edges a few times, but most importantly, the actual computation is handed off to the previous IP (which starts at the left corner, moving north east): ) . . . . = . . . ] . } = . . } . . ~ . / . * . . . . . . . . . . . . . . . = . > ( < . . } . = . . . & . \ [ . . . . . . After bouncing off the branch towards south east, the IP wraps around the edge to the two = in the top left corner (which, together, are a no-op), then bounces off the /. The ~ inverts the sign of the current value, which is important for subsequent iterations. The IP wraps around the same edge again and finally hits [ where control is handed over to the other IP. This one now executes ~}=)&}=*} which undoes the negation and then just runs the ungolfed loop body (minus the =). Finally it hits ] which hands control back to the original IP. (Note that next time, we execute it this IP, it will start from where it left off, so it will first hit the corner. We need the current value to be negative in order for the IP to jump back to the north west edge instead of the south east one.) Once the original IP resumes control, it bounces off the \, executes the remaining = and then hits > to feed into the next loop iteration. Now the really crazy part: what happens when the loop terminates? ) . . . . . ( . . ] = . . ' . } . } . . . % * . . & . . . . . . . . . . . . = | . . < . . } ! . . . . & @ . . . . . . . . The IP moves north east form the < and wraps around to the north east diagonal. So it ends up on the same execution path as the loop body (&}=*}]). Which is actually pretty cool, because that is exactly the code we want to execute at this point, at least if we add another =} (because }=} is equivalent to {). But how does this not actually enter the earlier loop again? Because ] changes to the next IP which is now the (so far unused) IP which starts in the top right corner, moving south west. From there, the IP continues along the edge, wraps to the top left corner, moves down the diagonal, bounces off the | and terminates at @ while executing the final bit of linear code: =}&)('%!@ (The )( is a no-op of course - I had to add the ( because the ) was already there.) Phew... what a mess... • Nice! How new is this? Also, you may wish to create an esolangs page whenever you get a stable release Commented Sep 12, 2015 at 21:33 • @mbomb007 I implemented the language two days ago (and designed it over two or three days before that). And yes, I'll definitely add an esolangs page, but I think the spec isn't 100% stable yet (there are still 3 unassigned commands for instance). Once I feel that it's more stable, I'll add it to both esolangs and our meta post. Commented Sep 12, 2015 at 21:36 • Under the expanded hex is it wraps to the left-most corner (the 1). What 1 are you talking about there? Commented Sep 13, 2015 at 4:15 • @mbomb007 fixed. The ) used to be a 1. Commented Sep 13, 2015 at 6:54 • +1 just for the level of detail in your explanation of how it works. If more languages came with an example that detailed more people could use them :D Commented Oct 22, 2015 at 1:25 # Pyth, 4 bytes }QPQ Prints True or False. • I know that this is old but now you can also do that like this: P_Q and save 1 byte. Commented Feb 19, 2016 at 20:23 • It's now possible with P_ – Blue Commented Jul 22, 2016 at 18:27 • @drobilc You can cut the Q, as an EOF when the function is expecting an argument, it uses the input Commented Sep 11, 2017 at 3:27 • If we're adding solutions that now work, /P is an alternate 2 byte option. Commented Feb 1, 2020 at 0:06 ## Retina, 16 bytes ^(?!(..+)\1+$)..

Try it online!

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

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

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

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

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

# HTML+CSS, 254+nmax*28 bytes

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

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

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

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

1. Getting Input

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

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

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

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

<input type=checkbox name=i>

Followed by the submit element (34 bytes):

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

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

• Wouldn't it be shorter to do main=interact$\n-> ...? Commented Sep 20, 2015 at 6:57 • Counterintuitively, no! Consider that you'd need interact...read in there somewhere, which makes it a lot longer than just readLn. Often do notation can be more concise than you might expect, especially when the alternative is a lambda. – lynn Commented Sep 20, 2015 at 20:34 # 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 ) • You might want to edit the Brachylog 2 version of this into the post, too, now that the syntax is a byte shorter. – user62131 Commented May 11, 2017 at 16:10 • @ais523 True, done. Commented May 11, 2017 at 16:15 • Does the Brachylog 2 answer postdate the challenge? Commented May 12, 2017 at 16:30 • @ScottMilner Yes, but this is explicitely allowed in this challenge: "Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge" Commented May 12, 2017 at 16:34 # Labyrinth, 29 bytes 1 ? : } +{%!@ (:'( } { :** Reads an integer from STDIN and outputs ((n-1)!)^2 mod n. Wilson's theorem is pretty useful for this challenge. The program starts at the top-left corner, beginning with 1 which multiplies the top of the stack by 10 and adds 1. This is Labyrinth's way of building large numbers, but since Labyrinth's stacks are filled with zeroes, the end effect is as though we just pushed a 1. ? then reads n from STDIN and : duplicates it. } shifts n to the auxiliary stack, to be used at the end for the modulo. ( then decrements n, and we are ready to begin calculating the squared factorial. Our second : (duplicate) is at a junction, and here Labyrinth's control flow features come into play. At a junction after an instruction is executed, if the top of the stack is positive we turn right, for negative we turn left and for zero we go straight ahead. If you try to turn but hit a wall, Labyrinth makes you turn in the other direction instead. For n = 1, since the top of the stack is n decremented, or 0, we go straight ahead. We then hit a no-op ' followed by another decrement ( which puts us at -1. This is negative, so we turn left, executing + plus (-1 + 0 = -1), { to shift n back from the auxiliary stack to the main and % modulo (-1 % 1 = 0). Then we output with ! and terminate with @. For n > 1, at the second : we turn right. We then shift } our copied loop counter to the auxiliary stack, duplicate : and multiply twice **, before shifting the counter back { and decrementing (. If we're still positive we try to turn right but can't, so Labyrinth makes us turn left instead, continuing the loop. Otherwise, the top of the stack is our loop counter which has been reduced to 0, which we + add to our calculated ((n-1)!)^2. Finally, we shift n back with { then modulo %, output ! and terminate @. I said that ' is a no-op, but it can also be used for debugging. Run with the -d flag to see the state of the stack every time the ' is passed over! • Squaring the factorial is a really cool trick :) – lynn Commented Sep 11, 2015 at 18:06 • @Mauris Thanks! I need to give credit where it is due though - I first saw the trick used by xnor here Commented Sep 11, 2015 at 18:16 • Yay, the first Labyrinth answer not written by me! :) Commented Sep 11, 2015 at 18:48 # Bash + GNU utilities, 16 • 4 bytes saved thanks to @Dennis • 2 bytes saved thanks to @Lekensteyn factor|awk NF==2 Input is one line taken from STDIN. Output is empty string for falsey and non-empty string for truthy. E.g.:$ ./pr.sh <<< 1
$./pr.sh <<< 2 2: 2$ ./pr.sh <<< 3
3: 3
$./pr.sh <<< 4$
• Cool, learned about another coreutil. Your can strip two characters by counting the number of fields: factor|awk NF==2 Commented Sep 18, 2015 at 11:03
• @Lekensteyn - thanks - for some reason I missed your comment before :) Commented May 24, 2016 at 19:30
• I was going to post something somewhat similar, only longer and without AWK. Nicely done. Commented Feb 6, 2017 at 19:16

# Java, 126 121 bytes

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

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

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

In expanded form:

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

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

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

## JavaScript, 39 36 bytes

Saved 3 bytes thanks to ETHproductions:

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):

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

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

# R, 37 29 bytes

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

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

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

Saved 8 bytes thanks to flodel!

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

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

• >:^] should be the official Stack Cats logo Commented Jun 24, 2016 at 23:28

# Brain-Flak, 112 108 bytes

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

Try it online!

## How it works

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

We start by decrementing n as follows.

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

### n = 1

If n = 1 is zero, the while loop

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

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

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

n > 1

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

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

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

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

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

# TI-BASIC, 12 bytes

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

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

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

assume that the input can be stored in your data type

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

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

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

# Ruby, 15 + 8 = 23 bytes

p$_.to_i.prime? Sample run: bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015 false • Heheh, I knew there would be a builtin in Ruby somewhere, but I couldn't be bothered to look for it, so I answered in C. +1. Commented Sep 11, 2015 at 15:01 • @steveverrill, I knew it because was a big help for Project Euler. Commented Sep 11, 2015 at 15:03 # TI-BASIC, 24 bytes Note that TI-Basic programs use a token system, so counting characters does not return the actual byte value of the program. Upvote Thomas Kwa's answer, it is superior. :Prompt N :2 :While N≠1 and fPart(N/Ans :Ans+1 :End :N=Ans Sample: N=?1009 1 N=?17 1 N=?1008 0 N=?16 0 Now returns 0 if not a prime, or 1 if it is. • Isn't the square root just an optimisation that you don't actually need for the program to be correct? Commented Sep 11, 2015 at 15:24 • Why would you need to divide by two? Commented Sep 11, 2015 at 15:29 • I always love TI-BASIC answers. Commented Feb 27, 2018 at 1:05 • Why choose Prompt over Input? They're the same number of bytes, and when it's a single variable Input would be more idomatic... Commented Dec 28, 2019 at 23:17 • @HelloGoodbye Because the UI is better for free, if I recall my reasoning correctly. Commented Feb 8, 2020 at 1:44 ## C++ template metaprogramming. 166131 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". # PARI/GP, 21 bytes print(isprime(input)) Works for ridiculously big inputs, because this kind of thing is what PARI/GP is made for. • isprime does an APR-CL primality proof, so does slow down quite a bit as inputs get very large. ispseudoprime(input) does an AES BPSW probable prime test, which will be much faster for over 100 digits. Still no known counterexamples after 35 years. Version 2.1 and earlier of Pari, from pre-2002, uses a different method that can easily give false results, but nobody should be using that. Commented Sep 11, 2015 at 18:30 • Why not i->isprime(i) or just isprime, that's shorter? Commented Aug 30, 2020 at 17:50 • @JeppeStigNielsen The challenge says: “Write a full program that …” – lynn Commented Aug 31, 2020 at 16:46 • OK, that might be the correct interpretation, if you insist on reading with input() and writing with print(...). However, I thought a function like foo(x, y) = { z=bar(x); if(y, return(y*z)); z } or something was a "full program" in PARI/GP. It is not usual to do input() and print(...), more common to use return values (functional language). Commented Sep 1, 2020 at 1:51 # Python 3, 59 bytes Now uses input() instead of command line arguments. Thanks to @Beta Decay n=int(input()) print([i for i in range(1,n)if n%i==0]==[1]) • Take input using input() would be much shorter Commented Sep 11, 2015 at 17:02 • 52 bytes: n=m=int(input()), print(all(n%m for m in range(2,n))) Commented Sep 16, 2015 at 5:38 • Are you serious. Spend 25 extra characters for a lame quadratic speedup? Here we hate bytes. We spend every hour,minute, and second of our lives getting rid of the nineteenth byte. (Just kidding. But we don't do time optimizations that increase program length.) Commented Mar 20, 2016 at 4:15 • Use n%i<1 instead. Commented Oct 17, 2016 at 15:52 • @SwimBikeRun, you're correct. Mine is only an improvement on John Lyon though it doesn't meet requirements for n < 2. Sorry for the confusion. Commented Aug 7, 2020 at 16:43 # C, 67 bytes i,n;main(p){for(scanf("%d",&i),n=i;--i;p=p*i*i%n);putchar(48+p%n);} Prints !1 (a falsey value, by Peter Taylor's definition) 0 if (n-1)!^2 == 0 (mod n), and 1 otherwise. EDIT: After some discussion in chat, puts("!1"+p%n) seems to be considered a bit cheaty, so I've replaced it. The result is one byte longer. EDIT: Fixed for big inputs. ## Shorter solutions 56 bytes: As recommended in the comments by pawel.boczarski, I could take input in unary by reading the number of command line arguments: p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);putchar(48+p%n);} invoking the program like$ ./a.out 1 1 1 1 1
1                        <-- as 5 is prime

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

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

import Data.Numbers.Primes

Nothing much to explain.

• The same score can be achieved (although very inefficiently) without external libraries, using Wilson's theorem: main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1 – lynn Commented Sep 11, 2015 at 17:31 • We can even do shorter: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0 is 49 bytes.
– lynn
Commented Sep 11, 2015 at 18:06
– nimi
Commented Sep 11, 2015 at 21:16

## Python 2, 44

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

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

# Regex (.NET), 604517499469 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:

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

The challenges faced here are:

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

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

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

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

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

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

This regex takes advantage of the (?<name1-name2>pattern) syntax for golf reasons, using it as an equivalent for (?<-name2>)(?<name1>). It makes sure to only do this when the cursor is at the beginning of the input string, so that only empty values are pushed onto \k<name1>. This is used in two places, and I currently do not know why the first instance is working, instead of throwing the above-described exception; it seems to be that at least some of the \1 empties it pops would have been captured from elsewhere than the beginning of the string. The (?<-2>\2)(?<3>) does in fact throw this exception if an attempt is made to convert it from (?=.*$((?<-2>\2)(?<3>)|){9}) to (?<=((?<3-2>\2)|){9}^.*). As far as I know there's no debugger for .NET regex, so it may be tricky to get to the bottom of this. When interpreting the explanation below, remember that lookbehinds in .NET, (?<=...) and (?<!...), are evaluated from right to left – so read those from bottom to top, one quantified token at a time. When entering a lookahead inside a lookbehind, go back to reading from top to bottom. ^ # Read decimal number into C1, in unary-coded decimal ( # Read this digit, adding it to C1 (?=[6-9] (?<1>){6}|) # C1 digit += 6, if digit is in [ 6789] (?=[3-59](?<1>){3}|) # C1 digit += 3, if digit is in [ 345 9] (?=[258] (?<1>){2}|) # C1 digit += 2, if digit is in [ 2 5 8 ] (?=[147] (?<1>) |) # C1 digit += 1, if digit is in [ 1 4 7 ] . # C1: push separator )+$
# C1 now has least-significant digit on top, separator above
(?<!
(?= # Assert C1==0; since it must have the same number of separators as
# there are digits in the input, if once we remove that number of
# captures from it, it has nothing remaining, its value was zero.
(?<-1>.)+
(?(1)^)
)
\11 # Assert the quotient is not a power of 10 (all we really want is to
# assert the quotient != 1, but that would be more complex to do);
# discarding the powers of 10 other than 1 is harmless, because in those
# cases where the remainder is zero, twice the divisor will yield half
# the quotient and the remainder will still be zero.
(?= # Calculate the remainder of division, letting C1 = C1 % C2:
# C2 now has most-significant digit on top, separator above
(                                      # C2
(?<=
(?=
# C1 now has least-significant digit on top, separator above
(?=                        # C3 = reverse(C2)
(                      # C3
(?<-2>)            # C2: pop separator
(?=
.*( (?<-2>\2) (?<3>) | ){9} ) . # C3: push separator )+ # Don't let C2 grow to be longer in digits than the # input number (?(2)^) ) # C3 now has least-significant digit on top, separator above # mutually align C1 with C3: C5 = reverse(C1), giving it its # least-significant portion with no C3 digits to subtract (?> (?<-1>) # C1: pop separator (.) # C5: push separator (?<= ( # I'm not currently sure why "(?<5-1>\1)" can be # used here as a shorthand for "(?<-1>\1)(?<5>)" # but I think it has something to do with the # fact that this mutually-align loop will only # do a nonzero number of iterations after C2 has # been padded with at least one leading zero, # meaning C1 will have already been rewritten by # reversing C5, i.e. we won't be dealing with # the original capture of C1. (?<5-1>\1) | ){9} ^.* ) )* # \9 = borrow flag = unset = 0 (clear) # C5 = reverse(C1 - C3); C2 = reverse(C3) (?<2> . # C2: push separator at the end of each # iteration (?<= ( # C5 digit = C1 digit (?<5>) (?<-1>\1) | ){9} ( (?<-1>\1){10} # C1 digit -= 10 | # or... () # \9 borrow flag = set ) ( # C1 digit -= C3 digit; # C2 digit = C3 digit # Using "(?<2-1>)" as a shorthand for # "(?<-1>(?<2>))" works here because it is # guaranteed to pull only from the captures # pushed by "(?<1>){10}", which is always done # at the beginning of the string. (?<2-1>) (?<-3>\3) | ){9} (?<-9> # if \9 borrow flag is set, # unset it... (?<-1>) # ...and C1 digit -= 1 )? (?<1>){10} # C1 digit += 10 (?<-3>) # C3: pop separator (?<-1>) # C1: pop separator (?<5>^.*) # C5: push separator ) )+
(?!\9)       # Assert borrow is 0 (clear)
(?(3)^)      # Assert C3 has been emptied, and thus
# completely processed (and by implication,
# so has C1 been)
# C2 now has most-significant digit on top, separator above
# C5 now has most-significant digit on top, separator below
(?<=                       # C1 = reverse(C5)
(?<-5>
(?=
(?<1>
(?=.*$\5) | . ) ) . )* ){10} # C1 now has least-significant digit on top, separator above (\12)? # \11 = set if \12 is already set () # \12 = set | # or do nothing ){9} # This digit of the quotient can range from # 0 to 9 (but we don't have to save the # quotient, just the remainder) ^.* ) . # pad C2 with one more leading zero )* ) (?<-13>){3} # Assert C2 >= 2, unless C2 has a leading zero, using C13 as a # disposable copy of C2. The only numeric value of C2 without a # leading zero that puts only 2 captures on it is C2 == 1. # Values of C2 with leading zero(s) will cause the long division # algorithm to give an incorrect result, but never a false # positive of getting a remainder of zero, so this only results # in a little slowdown, testing invalid divisors. # C2 now has most-significant digit on top, separator above ^ (?<-14> # C13 = C2 = arbitrary number (a divisor to test) (?(14)| ((?<2> (.)? # \14 = set optionally, ending incrementing of digit and # pushing a separator onto C2; due to the outer # loop being "(?<-14>)", if it still isn't set by # the last iteration of this loop, it will be. )) ){10} )+ .* # allow C2 to have fewer digits than the input | ^1 # exclude 1, which is non-composite but also non-prime ) As per the challenge rules, this does not bother to avoid matching $$\0\$$. But this can be fixed by changing |^1 to |^0*1? or |^[01], at a cost of 3 bytes. ### Speed-improved version, 525495 483 bytes ^((?=[6-9](?<1>){6}|)(?=[3-59](?<1>){3}|)(?=[258](?<1>){2}|)(?=[147](?<1>)|).)+$(?<!(?=(?<-1>.)+(?(1)^))\11(?=((?<=(?=(?=((?<-2>)(?=.*$((?<-2>\2)(?<3>)|){9}).)+(?(2)^))(?>(?<-1>)(.)(?<=((?<5-1>\1)|){9}^.*))*(?<2>.(?<=((?<5>)(?<-1>\1)|){9}((?<-1>\1){10}|())((?<2-1>)(?<-3>\3)|){9}(?<-9>(?<-1>))?(?<1>){10}(?<-3>)(?<-1>)(?<5>^.*)))+$(?!\9)(?(3)^)(?<=(?<-5>(?=(?<1>(?=.*$\5)|.)).)*){10}(\12)?()|){9}^.*).)*)(?<-13>){2}\13(?<-13>)^(?<-14>(?(14)|((?<2>(.)?))){10}(?<-15>))+(?<15>)(.)*|^1) Try it online! Try it online! - primes matched in unary, for comparison This version limits its divisor search to $$\\lceil{n\over 2}\rceil\$$ digits, where $$\n\$$ is the number if digits in the input. This is guaranteed to go at least as high as the square root of the input number. It can test all the numbers up to $$\3333\$$ on TIO in 59 seconds. Only the section that differs is explained below: # Assert C2 >= 2, using C13 as a disposal copy of C2: # The only numeric value of C2 without a leading zero that puts only 2 # captures on it is C2 == 1 (?<-13>){2} \13 (?<-13>) # C2 now has most-significant digit on top, separator above ^ (?<-14> # C13 = C2 = arbitrary number (a divisor to test) (?(14)| ((?<2> (.)? # \14 = set optionally, ending incrementing of digit and # pushing a separator onto C2; due to the outer # loop being "(?<-14>)", if it still isn't set by # the last iteration of this loop, it will be. )) ){10} (?<-15>) )+ (?<15>) # C15 += 1 (.)* # allow C2 to have fewer digits than the input; # C15 += number digits skipped Try it on regex101 - This is 540 503 491 bytes, as regex101 does it own validation on regexes instead of leaving that up to the engine in question, and does not currently support the (?<name1-name2>) syntax. ## Regex (.NET), 692449396 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
)
^.*
)
)*
)
# 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
)
• This is witchcraft! Commented May 3, 2023 at 3:17

# Snails, 122

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

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

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

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

Annotated code:

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