Skip to content

Instantly share code, notes, and snippets.

@velociraptors
Created April 26, 2011 17:37
Show Gist options
  • Save velociraptors/942719 to your computer and use it in GitHub Desktop.
Save velociraptors/942719 to your computer and use it in GitHub Desktop.
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]
"""
if inputvalue in [0, 1, -1]:
print("only an asshole tries to find the prime factorization of 0 or 1")
return
negative = False
if inputvalue < 0:
negative = True
if sieve:
candidates = prime_sieve(abs(inputvalue))
else:
candidates = primes
factors = []
for prime in candidates:
if not inputvalue % prime:
factors.append(prime)
outvalue = inputvalue / prime
break
outvalue = 1
if outvalue != 1:
factors += prime_factorization(outvalue, sieve = False, primes = candidates)
if negative:
factors.insert(0, -1)
return factors
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment