find all multiplicands and multipliers for a number
Paul Rubin
no.email at nospam.invalid
Sat Apr 11 02:08:50 EDT 2015
Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
> It may be a bit slow for very large numbers. On my computer, this takes 20
> seconds:
> py> pyprimes.factors.factorise(2**111+1)
> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
laptop (64 bit linux):
import itertools, time
def candidates():
yield 2
yield 3
for i in itertools.count(5,6):
yield i
yield i+2
def fac(n):
for c in candidates():
if c*c > n:
yield n
break
while n%c == 0:
yield c
n /= c
t0 = time.time()
print list(fac(2**111+1))
print time.time() - t0
More information about the Python-list
mailing list