pyregexprimes.py

import re
import time

comp_re = re.compile(r'^1?$|^(11+?)\1+$')

def regex_prime(args):
    primes = [2]
    for n in xrange(*args):
        if not re.match(comp_re, str(1) * n):
            primes.append(n)
    return primes

def trial_div(args):
    primes = [2]
    for n in range(*args):
        prime = True
        for p in primes:
            if not p*p <= n:
                break
            if n % p == 0:
                prime = False
        if prime:
            primes.append(n)
    return primes

def prime_time(f, args, typ):
    then = time.time()
    nums = f(args)
    now = time.time()
    return ' '.join(["%s took" % typ, str(now - then)[:8], "seconds"])

if __name__ == '__main__':
    import sys
    if len(sys.argv) > 1:
        limit = int(sys.argv[1]) + 1
    else:
        limit = 1001
    args = (3, limit, 2)

    print prime_time(regex_prime, args,  'regex')
    print prime_time(trial_div, args, 'trial div')