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:

Post a Comment