Back after a long time…saw something strange today and think it deserves a post. I was cranking through Problem 47 on Project Euler. As I was optimizing the solution, the optimization actually increased run time – and I’m at a loss to explain it. So here goes:
def problem_47(maxlen = 4):
found = False
i = 2*3*5*7 + 1
while not found:
# facs = [len([j for j in uniq(prime_fac(i+k))]) for k in
xrange(0,maxlen)]
d = 4
for t in range(i+3, i-1 , -1):
k = len(list(uniq(prime_fac(t))))
if k < 4:
i = t + 1
break
else:
d -= 1
if d ==0:
found = True
print list(xrange(i, i + maxlen))
# if i % 1000 == 0:
# print iThe run time is about 1m2s.
Now, if I try to optimize it such that I break (line 10) when I find the first number from the end that has less than 4 prime factors, the run time should be lesser (or at least the same). Right?
Turns out Wrong… now the thing takes more than 3m to run. What is going wrong?
If any of you have a clue, drop me a comment.
