primes.py

import time
from math import sqrt

def sieve(stop):
    stop += 1
    counter = 0
    num_list = range(2, stop)
    for i in num_list:
        counter += 1
        if i:
            args = (i * 2, stop, i)
            for j in range(*args):
                counter += 1
                idx = j - 2
                num_list[idx] = False
    primes = [n for n in num_list if n]
    return primes, counter

def trial_div(stop, lim_sqrt=False):
    counter = 0
    start, step = 3, 2
    args = start, stop, step
    primes = [2]
    for n in range(*args):
        counter += 1
        prime = True
        for p in primes:
            # assume prime is True
            counter += 1
            # limit trial division to known primes < sqrt(n)
            if lim_sqrt:
                if not p <= sqrt(n):
                    break
                if n % p == 0:
                    prime = False
            # trial divide each candidate by all known primes
            else:
                if n % p == 0:
                    prime = False
        # if the prime flag wasn't changed
        if prime:
            primes.append(n)
    return primes, counter

def prime_wrapper(stop, f, arg=None):
    then = time.time()
    if arg:
        primes, steps = f(stop, arg)
    else:
        primes, steps = f(stop)
    now = time.time()
    elapsed = str(now - then)[:8]
    return primes, steps, elapsed

def format_output(name, stop, primes, steps, elapsed):
    return '\n'.join(
        ('------------------------------',
        "%s" % name,
        "",
        "primes found: %s" % len(primes),
        "steps taken: %s" % steps,
        "running time: %ss" % elapsed,
        "",
        )
    )

if __name__ == '__main__':
    import sys
    sep = '##################################################'

    prime_funcs = ((sieve, None, 'sieve'),
                   (trial_div, True, 'trial division (sqrt limited)'),
                   (trial_div, None, 'trial division'))

    max_prime_list = [1000, 5000, 10000, 25000, 50000, 100000, 250000]

    if len(sys.argv) > 1 and sys.argv[1].isdigit():
        max_prime_list = [int(sys.argv[1])]

    for max_prime in max_prime_list:
        print sep
        print "Primes from 2 to %s" % max_prime
        print 
        for prime_func, arg, name in prime_funcs:
            stats = prime_wrapper(max_prime, prime_func, arg)
            print format_output(name, max_prime, *stats)