primes.py

### Various function implementations to calculate a list of prime numbers

def naive_primes(n):
    """Naively find all prime numbers up to n"""
    primes = []
    if n < 2:
        # 1 is not a prime number
        return primes
    for i in xrange(2,n):
        is_prime = True
        for j in xrange(2,i):
            if i % j == 0:
                is_prime = False
        if is_prime:
            primes.append(i)

    return primes

def naive_bounded_primes(n):
    """
    Find all prime numbers up to n applying a few optimizations over
    the naive approach. Namely, only search up to sqrt(i) for each potential
    prime, and limit the overall search to odd numbers.
    """
    import math

    if n < 2:
        return []

    primes = [2]
    for i in xrange(3,n,2):
        is_prime = True
        upper_bound = int(math.sqrt(i)) + 1
        for j in xrange(3, upper_bound, 2):
            if i % j == 0:
                is_prime = False
        if is_prime:
            primes.append(i)

    return primes

def naive_sieve_primes(n):
    """
    Find all the prime numbers up to n, utilizing the property that any non-prime
    numbers must be divisible by a prime number (Sieve of Eratosthenes).
    Unfortunately this method is pretty slow due to the new set creation.
    """
    import math

    if n < 2:
        return []

    primes = [2]
    for i in range(3,n,2):
        upper_bound = int(math.sqrt(i)) + 1
        if True in {i % prime == 0 for prime in primes}:
            # this number was divisible by one of our primes, so it is not itself prime
            continue
        else:
            primes.append(i)

    return primes

def faster_sieve_primes(n):
    """
    Find all the prime numbers up to n, via an iterative Sieve of Eratosthenes
    implementation that doesn't create additional garbage, and is therefore faster.
    """
    if n < 2:
        return []

    potential_primes = [True] * n
    potential_primes[0] = False
    potential_primes[1] = False

    for i, is_prime in enumerate(potential_primes):
        if is_prime:
            for j in xrange(i*i, n, i):
                # remove factors of this prime number
                # can start at i*i because numbers less than that have already
                # been removed since they are factors of earlier primes
                potential_primes[j] = False

    return [i for i,is_prime in enumerate(potential_primes) if is_prime]


### Test Correctness
N = 50
ANSWER = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

assert naive_primes(N) == ANSWER
assert naive_bounded_primes(N) == ANSWER
assert naive_sieve_primes(N) == ANSWER
assert faster_sieve_primes(N) == ANSWER


### Test Performance
M = 10000

%timeit naive_primes(M)
# => 1 loops, best of 3: 3.24 s per loop

%timeit naive_bounded_primes(M)
# => 100 loops, best of 3: 12.4 ms per loop

%timeit naive_sieve_primes(M)
# => 1 loops, best of 3: 266 ms per loop

%timeit faster_sieve_primes(M)
# => 100 loops, best of 3: 2.19 ms per loop