#1
  1. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,792
    Rep Power
    508

    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 04:32 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo