### Thread: all factorizations of a number

1. #### all factorizations of a number

function all_factors attempts to efficiently compute all factorizations of the input number
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,)]```
Last edited by b49P23TIvg; May 13th, 2017 at 05:32 PM.