Skip to content

Instantly share code, notes, and snippets.

@prongs
Last active December 18, 2015 01:39
Show Gist options
  • Save prongs/5705065 to your computer and use it in GitHub Desktop.
Save prongs/5705065 to your computer and use it in GitHub Desktop.
Efficient code for factorization in python. Using Sieve of Eratosthenes
from math import sqrt
from itertools import count
from collections import defaultdict
# Sieve of Eratosthenes
# Modified from the Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/
def prime_candidates(begin=5, end=None):
"""Returns all prime candidates between begin and end(>=begin and <end). If end is None, it behaves like end = infinity. A prime candidate is either 2, 3 or a number of the form 6k-1 or 6k+1.
"""
cur = begin
if cur % 2 == 0:
if cur == 2:
yield 2
cur += 1
if cur % 6 == 3:
if cur == 3:
yield 3
cur += 2
elif cur % 6 == 1:
yield cur
cur += 4
gen = count(cur, step=6) if not end else xrange(cur, end, 6)
for n in gen:
yield n
yield n + 2
def gen_primes(mx=1000000000):
""" Generate all prime numbers (strictly) below mx
"""
mx_sqrt = int(sqrt(mx)) + 1
D = {}
yield 2
yield 3
for q in prime_candidates():
if q >= mx:
return
if q not in D:
yield q
if q < mx_sqrt:
D[q * q] = [q]
else:
for p in D[q]:
qp = q + p
while qp % 6 not in [1, 5]:
qp += p
if qp < mx:
D.setdefault(qp, []).append(p)
del D[q]
def factorize(n):
"""Returns factorization of n as a dictionary. If n is prime, returns None. Keys are the primes, corresponding values are their powers in the factorization. So a return value of {a:b, c:d} means n = (a^b)*(c^d) with a, c primes.
"""
res = defaultdict(lambda: 0)
for p in gen_primes(mx=n):
while n % p == 0:
n = n // p
res[p] += 1
if n == 1:
return dict(res)
if __name__ == '__main__':
print factorize(10), factorize(100), factorize(365), factorize(5)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment