Code:

#!/usr/bin/python3
'''
>>> # doctest python3 -m doctest thisfile.py
>>> main()
True
'''
import sys, pprint
def prime_generator():
'''
return the next prime number
>>> prime = prime_generator()
>>> [next(prime) for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
'''
primes = [2, 3]
for prime in primes:
yield prime
# most of the primes are n*6 plus or minus 1.
a = 0
while True:
a += 6
for i in (-1, 1):
b = a + i
if not any(not (b % prime) for prime in primes):
primes.append(b)
yield b
def prime_factor(a:int)->list:
factors = []
for prime in prime_generator():
if a == 1:
return factors # return is in a significantly nasty spot.
d, m = divmod(a, prime)
while not m: # in other words, a % prime == 0
factors.append(prime)
a = d
d, m = divmod(a, prime)
def all_factors(n:int)->[tuple, tuple]:
factorizations = set(((),))
for factor in prime_factor(n):
partial_factorizations = factorizations
# sets reduce redundancy for optimization
factorizations = set()
for factorization in partial_factorizations:
a = list(factorization)
# a partial factorization along with the next prime
t = a + [factor]
t.sort()
factorizations.add(tuple(t))
for (i, f) in enumerate(a):
# a partial factorization with each factor in turn multiplied by the next prime
t = a[:i] + [factor * f] + a[i+1:]
t.sort()
factorizations.add(tuple(t))
return sorted(factorizations)
def main():
pprint.pprint(all_factors(60), stream = sys.stderr)
return all_factors(210) == [
(2, 3, 5, 7),
(2, 3, 35),
(2, 5, 21),
(2, 7, 15),
(2, 105),
(3, 5, 14),
(3, 7, 10),
(3, 70),
(5, 6, 7),
(5, 42),
(6, 35),
(7, 30),
(10, 21),
(14, 15),
(210,)]

Tweet This+ 1 thisPost To Linkedin