Skip to content

Instantly share code, notes, and snippets.

@alexalemi
Created August 11, 2011 22:48
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alexalemi/1141000 to your computer and use it in GitHub Desktop.
Save alexalemi/1141000 to your computer and use it in GitHub Desktop.
Alternative Prime Factors
from itertools import chain
def factors2(n):
result = []
# test 2 and all of the odd numbers
# xrange instead of range avoids constructing the list
for i in chain([2],xrange(3,n+1,2)):
s = 0
while n%i == 0: #a good place for mod
n /= i
s += 1
result.extend([i]*s) #avoid another for loop
if n==1:
return result
print factors2(200)
@alexalemi
Copy link
Author

Inspired by the Glowing Python post here: http://glowingpython.blogspot.com/2011/07/prime-factor-decomposition-of-number.html

This version uses xrange and modulo and extend to get some time speedups.

E.g.

In [2]: timeit factors(1234567)
1 loops, best of 3: 674 ms per loop

In [3]: timeit factors2(1234567)
1000 loops, best of 3: 1.69 ms per loop

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment