Mastering Regular Expressions 2nd Ed.

[Michael Hudson]

Michael Hudson <mwh at python.net> writes:

> "David LeBlanc" <whisper at oz.net> writes:
> 
> > I may be wrong about this, but I don't think regular expressions
> > qualify as turing complete. No branching for one thing...
> 
> Somewhere you can find a (perl) regexp that matches prime but not
> composite numbers,

I found it here:

    http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

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
... 
>>> isprime(10)
0
>>> isprime(13)
1

(you can see I got the above description slightly wrong)

Cheers,
M.

-- 
  Well, you pretty much need Microsoft stuff to get misbehaviours
  bad enough to actually tear the time-space continuum.  Luckily 
  for you, MS Internet Explorer is available for Solaris.
                              -- Calle Dybedahl, alt.sysadmin.recovery