Primality Test Using Regex

Out of all possible ways to check primality of a number, let us go a bit extreme and use regex to check primality, And as expected, this method is incredibly expensive, while not useful, we can just admire it's beauty

Primality Test Using Regex

Regular Expression to check Primality


That's it, Regex is powerful, it's much more than simple string matching, while this is computationally expensive, we can still admire it's simplicity.

How does Primality Regex Work?


The first part of the regex says, "any character, zero or one times". So basically, is there zero or one character-- or, per what I mentioned above, n == 0 || n == 1. If we have the match, then return the negation of that. This corresponds with the fact that zero and one are NOT prime.


The second part of the regex is a little trickier, relying on groups and backreferences. A group is anything in parentheses, which will then be captured and stored by the regex engine for later use. A backreference is a matched group that is used later on in the same regex.

The group captures 1 character, then 1 or more of any character. (The + character means one or more, but ONLY of the previous character or group. So this is not "two or four or six etc. characters", but rather "two or three etc." The +? is like +, but it tries to match as few characters as possible. + normally tries to gobble the whole string if it can, which is bad in this case because it prevents the backreference part from working.)

The next part is the backreference: That same set of characters (two or more), appearing again. Said backreference appears one or more times.

Why is it computationally expensive?

Complexity of Primality Regex

From empirical data it appears to be O(n²)

This is to be expected since the regular expression checks all possible divisors to see if any of them occurs a whole number of times in the string.

Not only this, Regex is also space inefficient, there is every reason to not use it, but, just admire it's beauty.