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.
Comments (8)
Jj on March 19, 2007:
Uhm.. I'm probably missing something, but when you say
"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."
This means that you'll never know if the number is prime, since it will never find a divisor?
James Tauber on March 20, 2007:
You know the number is prime because the regex will fail to find a match.
DangDude on April 17, 2007:
I don't read reddit; why is this not a regular expression? I guess I'm asking, what's the difference between a regex and a regular expression? I thought "regex" was just a common contraction for "regular expression".
Calvin Spealman on April 17, 2007:
It is surprising what people will come up with under the influence of drugs and alcohol. I can't think of anything else that would account for this!
JMC on April 17, 2007:
I'm not sure what the guy on reddit meant, but you are definitely using a regular expression, as indicated by the "import re" line.
Jacob Holm on April 17, 2007:
It is not a regular expression in the formal language theory sense, because it contains a backreference.
mp3 indir on Dec. 25, 2007:
It is surprising what people will come up because it contains a backreference
Last Modified: March 19, 2007
Author: James Tauber
Neil K on March 18, 2007:
It's not mine, it's Abigail's.