find all multiplicands and multipliers for a number
Marko Rauhamaa
marko at pacujo.net
Sun Apr 12 09:17:15 CEST 2015
wolfram.hinderer at googlemail.com:
> I get other results on 3.2.3:
>
> n % 0 raises ZeroDivisionError.
> After fixing that by using range(2, n) it takes about three times as
> long as the original version, which is what I'd expect.
You're right. I got wrong results because I ran a wrong command!
The range(2, n) version is 3 times slower than the candidates() version.
And in fact, the sqrt optimization now makes the original version 20%
faster:
========================================================================
#!/usr/bin/env python3
import itertools, time, math
def candidates():
yield 2
yield 3
for i in itertools.count(5,6):
yield i
yield i+2
def fac(n):
bound = int(math.sqrt(n))
for c in candidates():
if c > bound:
yield n
break
if n%c == 0:
yield c
n //= c
while n%c == 0:
yield c
n //= c
bound = int(math.sqrt(n))
t0 = time.time()
print(list(fac(2**111+1)))
print(time.time() - t0)
========================================================================
Marko
More information about the Python-list
mailing list