Skip to content

Instantly share code, notes, and snippets.

@velociraptors
velociraptors / gist:942719
Created April 26, 2011 17:37
Recursively calculates the prime factorization of any given number
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]
"""
# 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 _|
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)