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