Home Original page

Mastering Regular Expressions 2nd Ed.

Jeff Epler jepler at unpythonic.net
Fri Jul 26 14:25:59 EDT 2002 
Michael Hudson <mwh at python.net> writes:
> > Somewhere you can find a (perl) regexp that matches prime but not
> > composite numbers,
> 
Michael Hudson <mwh at python.net> continues:
> I found it here:
> 
>     http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
[...]
> (you can see I got the above description slightly wrong)
> 
> and think it's sufficiently clever to post a link to.
> 
> Here's it at work in Python:
> 
> >>> def isprime(num, prog=re.compile(r"^1?$|^(11+?)\1+$")):
> ...  return prog.match('1'*num) is None

You can use the zero-length negative lookahead assertion (?!...) to make
the RE match on primes (and not match on composites), of course.

The expression becomes
    r"^(?!1?$|^(11+?)\1+$)"

This is clearly cooler than the RE that matches multiples of 3 written
in binary... I'm not sure this is it, but I think it may be.
    (0|1(01*0)*1)+
of course, this RE is actually a good old-fashioned RE, so it still has
some allure.

Jeff
More information about the Python-list mailing list