velociraptors

def prime_factorization(inputvalue, sieve = True, primes = None):
    """
    Takes an Integer argument and returns a the prime factorization as a list.
    e.g. prime_factorization(45) => [3, 3, 5]
    
    Optional arguments are 'sieve' and 'primes'; default values are 'True' and
    'None' respectively. Setting sieve to 'False' commits the user to providing
    a set of primes as a list.
    e.g. prime_factorization(45, sieve=False, primes=[3]) => [3, 3]
    """

velociraptors

# Think of the array in this manner:
#          _    i -->   _
# ARRAY = |00            |  In the top level list, indices are i
#         |  11          |  In the nested lists, indices are j
#      j  |    22        |
#      |  |      33      |
#      V  |        44    |
#         |_         55 _|

velociraptors

from time import time

def euler_sieve(n):
    # source: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    # Create a candidate list within which non-primes will
    # marked as None, noting that only candidates below
    # sqrt(n) need be checked. 
    candidates = range(n+1)
    fin = int(n**0.5)