find all multiplicands and multipliers for a number

[Marko Rauhamaa]

Paul Rubin <no.email at nospam.invalid>:

> This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> laptop (64 bit linux):

Converted to Python3:
========================================================================
#!/usr/bin/env python3

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)
========================================================================

This is slightly faster:

========================================================================
#!/usr/bin/env python3

import time

def fac(n):
    for c in range(n):
        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)
========================================================================


Marko