Fun with primality testing

Tim Peters tim_one at email.msn.com
Sat May 13 06:56:27 CEST 2000


[François Pinard]
> 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

Well, the thing is, the Perl folk usually write that as a one-liner.  Then
they can show that Python is wordier and slower, while pretending to be
clearer without actually succeeding <wink>:

import re
composite_matcher = re.compile(r"""
    (               # it's composite if
        (?: prime ){2,}   # something >= 2
    )
    \1+     # matches 2 or more times in all
    $       # exactly
""", re.VERBOSE).match

for n in range(2, 1000):
    if not composite_matcher("prime" * n):
        print n

parsing-is-as-powerful-as-anything-ly y'rs  - tim






More information about the Python-list mailing list