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.
The original post had 8 comments I'm in the process of migrating over.