Python Primality Regex

Via Simon Willison I discovered this wonderful method of testing primality with a regex by Abigail by way of Neil Kandalgaonkar.

Of course, I couldn't resist porting it to Python, so here it is:

import re
def is_prime(num):
    return not re.match(r"^1?$|^(11+?)\1+$", "1" * num)

although the magic is all in the regex which is copied verbatim from the Perl.

Firstly, the num is turned into a string of 1s so 0 = "", 1 = "1", 2 = "11, 3 = "111" and so on.

The ^1?$ just matches the 0 or 1 case to ensure they don't come up prime. The main part of the regex is the ^(11+?)\1+$.

It basically says match a group of 2 or more 1s repeated one or more times. If the string matches a group of 2 1s repeated one or more times, it's divisible by 2. If the string matches a group of 3 1s repeated one or more times, it's divisible by 3 and so on.

So this regex basically tries to see if the number is divisible by 2, then 3, then 4, etc., stopping with a match once a divisor is found.

And you can find what the lowest divisor was: it's simply the length of the first match group.

UPDATE: I've added Abigail to the credits, per Neil's comment below.

UPDATE: I've removed the phrase "regular expression" as, as pointed out by a commenter on reddit, it's not actually a regular expression.