# CC0 This work has been marked as dedicated to the public domain.
# https://creativecommons.org/publicdomain/zero/1.0/

# This script is not very efficient.
# There is much room for optimization in a language like C.
# One source of inefficiencies is the over-use of sets.
# These could simply be replaced with arrays and the set
# constraints enforced with linear search.
# You may be thinking, "linear search is o(n)!"
# Because the `n` in question is very small, it really shouldn't matter much
# and should still be faster than the overhead involved in a hash-set


def prime_factors(n):
    factors = []
    i = 2
    # This could be optimized by storing a list of primes.
    # And then only divide by known primes
    while n > 1:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 1
    return factors


def unique_items(lst):
    return list(set(lst))


def remove_one_of_each(container, remove):
    for item in remove:
        if item in container:
            container.remove(item)
    return container


def cartesian_product(a):
    result = set()

    # Recursively find cartesian product (of all lengths possible)
    # of items in list. Scan through list `a`. At each index, branch
    # either by taking the product, or skipping.
    def descend(i, prod):
        if i < len(a):
            descend(i + 1, prod)
            descend(i + 1, prod * a[i])
        result.add(prod)

    for i, item1 in enumerate(a):
        descend(i + 1, item1)

    return result


def multiply_each_value(a, b):
    result = set()

    for item1 in a:
        for item2 in b:
            result.add(item1 * item2)
    return result


def advance_state(prime_factors, p_last, found_factors):
    #  Find the all unique factors and their cartesian
    #  products in `prime_factors` to create `p`
    p = unique_items(prime_factors)
    p = set(p).union(cartesian_product(p))
    # Remove one of each unique factor from `prime_factors`.
    prime_factors = remove_one_of_each(prime_factors, unique_items(prime_factors))

    if p_last is not None:
        new_p = multiply_each_value(p, p_last)
        new_p = new_p.difference(found_factors)
    else:
        new_p = p
    found_factors = found_factors.union(new_p)

    return [prime_factors, new_p, found_factors]


def factorize(n):
    prime_factors_init = prime_factors(n)

    state = [prime_factors_init, None, set()]
    while len(state[0]):
        state = advance_state(*state)

    return state[2].union([1])


print(sorted(factorize(720)))