Possible Duplicate:
How to determine if a number is a prime with regex?
This page claims that this regular expression discovers non-prime numbers (and by counter-example: primes):
/^1?$|^(11+?)\1+$/
How does this find primes?
Asked
Active
Viewed 2.1k times
68
-
11This is **not** a dup. It's a different regexp and a different technique, and has better answers, to boot. – bmargulies Jul 22 '10 at 22:03
-
2@bmargulies: This *is* a dupe. The regex is the same, given the input restrictions on this question and that Java's String.matches method matches the regex against the entire string (so ^ and $ are implied), which it apparently does. – Jul 22 '10 at 22:57
-
1@Rog - the upvoted answers over there never mention unary. – bmargulies Jul 22 '10 at 23:33
-
@bmargulies: If you believe you can provide a better or more complete answer to that question, please, do so. I'd flag this question for merging, but the *superficial* differences in question text mean the answers need some editing (as is often the case), even though the questions are identical once you remove those superficial differences. – Jul 23 '10 at 04:43
-
@Rog at this point I'll just trust the diamonds to merge cleverly. – bmargulies Jul 23 '10 at 11:08
1 Answers
107
I think the article explains it rather well, but I'll try my hand at it as well.
Input is in unary form. 1 is 1, 2 is 11, 3 is 111, etc. Zero is an empty string.
The first part of the regex matches 0 and 1 as non-prime. The second is where the magic kicks in.
(11+?) starts by finding divisors. It starts by being defined as 11, or 2. \1 is a variable referring to that previously captured match, so \1+ determines if the number is divisible by that divisor. (111111 starts by assigning the variable to 11, and then determines that the remaining 1111 is 11 repeated, so 6 is divisible by 2.)
If the number is not divisible by two, the regex engine increments the divisor. (11+?) becomes 111, and we try again. If at any point the regex matches, the number has a divisor that yields no remainder, and so the number cannot be prime.
