Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A Python solution to Project Euler Problem 3
def factors(num):
"""Generates the factors for num.
By PEZ, from a description by BradC over at
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 =
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
candidate =
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment