public
Last active

A Python solution to Project Euler Problem 3

  • Download Gist
factors.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
def factors(num):
"""Generates the factors for num.
By PEZ, from a description by BradC over at Stackoverflow.com
http://stackoverflow.com/questions/439814#439850
"""
 
from math import sqrt
 
def _candidates():
"""Generates the sequence 2, then all odd ints starting with 3"""
c = 2
yield c
c += 1
while True:
yield c
c += 2
 
start = num
candidates = _candidates()
candidate = candidates.next()
sqrt_num = sqrt(num)
while candidate < sqrt_num:
while num % candidate == 0:
yield candidate
num /= candidate
sqrt_num = sqrt(num)
if candidate > sqrt_num:
yield num
return
candidate = candidates.next()
if num < start:
yield num
 
if __name__=='__main__':
# The number 600851475143 takes 0.002 secs to factor on my MacBook
from timeit import Timer
t = Timer("print list(factors(600851475143))", "from __main__ import factors")
print "%.5f" % t.timeit(1)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.