# 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

```