2014-04-02 16:56:35 +00:00
|
|
|
from math import floor, sqrt
|
|
|
|
|
try:
|
|
|
|
|
long
|
|
|
|
|
except NameError:
|
|
|
|
|
long = int
|
2013-06-05 21:47:54 +00:00
|
|
|
|
2014-04-02 16:56:35 +00:00
|
|
|
def fac(n):
|
2015-02-20 00:35:01 -05:00
|
|
|
step = lambda x: 1 + (x<<2) - ((x>>1)<<1)
|
2014-04-02 16:56:35 +00:00
|
|
|
maxq = long(floor(sqrt(n)))
|
|
|
|
|
d = 1
|
2020-02-17 23:21:07 -08:00
|
|
|
q = 2 if n % 2 == 0 else 3
|
2014-04-02 16:56:35 +00:00
|
|
|
while q <= maxq and n % q != 0:
|
|
|
|
|
q = step(d)
|
|
|
|
|
d += 1
|
2020-02-17 23:21:07 -08:00
|
|
|
return [q] + fac(n // q) if q <= maxq else [n]
|
2013-04-10 23:57:08 -07:00
|
|
|
|
2014-04-02 16:56:35 +00:00
|
|
|
if __name__ == '__main__':
|
|
|
|
|
import time
|
|
|
|
|
start = time.time()
|
|
|
|
|
tocalc = 2**59-1
|
|
|
|
|
print("%s = %s" % (tocalc, fac(tocalc)))
|
|
|
|
|
print("Needed %ss" % (time.time() - start))
|
