Fun with primality testing

[Emile van Sebille]

Well, *that* was fun.  I've never used regular expressions,
and had been meaning to read the how-to, so this was a good
excuse.

In working this out, I modified the code to see if I could
follow how things changed, and when I thought I understood,
I tried:
  if not re.match(r'(11+)\1\1+$', '1'*n):
thinking: it's got to match three times anyway.

What bothered me was that '+' would grab the whole thing,
then start backing off to find the match.  I have visions
of that happening byte by byte.  Now I'm wondering if the
additional match helps or hurts?  I've timed it, but not
much difference.  The single match is marginally faster.

However, making the first group less greedy, makes it
twice as fast:
  if not re.match(r'(11+?)\1+$', '1'*n):

and special casing the range helps too:
  for n in [2]+range(3,1000,2):

Maybe-I-could-have-used-these-for-y2k-mods?-ly y'rs,

Emile van Sebille
emile at fenx.com
-------------------


----- Original Message -----
From: François Pinard <pinard at iro.umontreal.ca>
To: <python-list at python.org>
Sent: Friday, May 12, 2000 4:16 PM
Subject: Fun with primality testing


> Hi, people.
>
> For your mere enjoyment!  Here is Python code which prints primes
below 1000.
> At the local Perl mongers meeting, someone showed this nicety to me.
>
>
> import re
> for n in range(2, 1000):
>     if not re.match('(11+)\\1+$', '1'*n):
>         print n
>
> --
> François Pinard   http://www.iro.umontreal.ca/~pinard
>
>
>
> --
> http://www.python.org/mailman/listinfo/python-list
>