APM: Primality regexp

[Tim McDaniel]

On Thu, 11 Sep 2008, Keith Howanitz <howanitz at gmail.com> wrote:
> Wayne - please send me the prime number regex you told us about.

I'm Wayne only in my heroin-induced wildest dream, but Googling for
     "prime number" "regular expression" perl
got, among its hits, <http://pages.cs.wisc.edu/~psilord/blog/9.html>
But the regular expression appears to miss the edge cases.  The real
test appears to be this:
     ('1' x $the_number_to_be_tested) !~ /^1?$|^(11+?)\1+$/

The short explanation:
- the left side of the | handles 0 or 1

- the right side of the | factors the number.  It tests each possible
   factor via the magic of backtracking.  It first tries 11 (meaning
   "2"), because +? is the non-greedy-matching operator.  That side of
   the expression tries to match 11 followed by one or more exact
   repetitions of 11 (with nothing left over).  That attempt matches
   only if the string is divisible by 2.

   If it fails, the regexp parser backtracks to 11+? and tries again,
   with one more character: it attempts to match with 111 (== 3).

   If that fails, 1111.
   11111.
   111111.
   ...

-- 
Tim McDaniel, tmcd at panix.com