Fun with primality testing

François Pinard pinard at iro.umontreal.ca
Sun May 14 00:30:32 CEST 2000


"Emile van Sebille" <emile at fenx.com> écrit:

> I tried:
>   if not re.match(r'(11+)\1\1+$', '1'*n):
> thinking: it's got to match three times anyway.

I guess the above would not work when you test a number which is the square
of a prime number.

> What bothered me was that '+' would grab the whole thing, then start
> backing off to find the match.

Indeed.  I'm curious about how gurus will optimise `pcre' for such cases. :-)

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard






More information about the Python-list mailing list