Saturday, December 4, 2010

Puzzle 3 without cheating

I am about 2800 times slower than the cheat I downloaded. But I get the right answer, and in a tolerable time (30 seconds). Pure brute forcing this seems like it would take much longer.


from sys import argv
from math import sqrt
from time import time

# PRIME GENERATOR

def nextprime():
""" generate next prime """

myprimes = [2]
candidate = 3
yield 2
while True:
factors = factorize(candidate,myprimes)
if len(factors.keys()) == 1:
myprimes.append(candidate)
yield candidate
candidate += 2

def primesupto(upto):
""" collect primes from the generator"""

result = []
primes = nextprime()
p = None
while not p or p < upto:
if p:
result.append(p)
p = primes.next()
return result

def factorize(target,allprimes=None,verbose=False):
""" get factors of an integer

this works but is very slow if the primes aren't cached """

factors = {}
upto = int(sqrt(target))
residual = target
prime = nextprime()

if allprimes:
prime = allprimes.__iter__()

while True: # get factors and multiplicities up to sqrt(N)
try:
factor = prime.next()
except StopIteration:
break
if factor > upto:
break
while not residual % factor:
residual /= factor
factors[factor] = factors.get(factor,0) + 1

if residual > 1: # if anything is left it is the sole prime factor > sqrt(N)
factors[residual] = 1

return factors

if __name__ == "__main__":
target = int(argv[1]) # get target from command line
upto = sqrt(target)
starttime = time()
allprimes = primesupto(upto)
print max(factorize(int(argv[1]),allprimes).keys())
endtime = time()
print endtime - starttime


Update:

Best answer, wow!


from time import time
from sys import argv

n = int(argv[1])
d = 3

starttime = time()
while (d * d < n):
if n % d == 0: n /= d
else: d += 2
endtime = time()
print n
print endtime - startime


Runs in 0.7 msec. I feel like a complete idiot now. Oh well, it was interesting anyway.

No comments: