Given a natural number n, we want to know in how many ways we may express these numbers as product of other numbers.

For example the number
```python
 18 = 2 x 9 = 3 x 6 = 2 x 3 x 3 # (we do not consider the product 18 x 1), (3 ways) 
```

See this example a bit more complicated,
```python
60 = 2 x 30 = 3 x 20 =  4 x 15 = 5 x 12 = 6 x 10 = 2 x 2 x 15 = 2 x 3 x 10 = 2 x 5 x 6 =  3 x 4 x 5 = 2 x 2 x 3 x 5 (10 ways)
```
We need the function ```prod_int_part()```, that receives a number n, and ouputs the amount of total different products with all the products of max length sorted in this way:

1) each product will be expressed in a list of its factors in incresing order from left to right

2) if there is more than one list-product, these lists should be ordered by the value of the first term, if two lists have the same term equal thay should be ordered by the value of the second term.

Let's see some cases:
```python
prod_int_part(18) == [3, [2, 3, 3]]

prod_int_part(60) == [10, [2, 2, 3, 5]
```

If we have only one list-product with the maximum length, there is no use to have it with two nested braces, so the result will be like this case:
```python
prod_int_part(54) == [6, [2, 3, 3, 3]]
```

Now, let's see examples when ```n``` cannot be partitioned:
```python
prod_int_part(37) == [0, []]

prod_int_part(61) == [0, []]
```
Enjoy it!!

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Mathematics

Starter code: def prod_int_part(n):
	

Solutions:
def prod_int_part(n, min_=2):
	(total, fac) = (0, [])
	for d in range(min_, int(n ** 0.5) + 1):
		if not n % d:
			(count, sub) = prod_int_part(n // d, d)
			total += count + 1
			if not count:
				sub = [n // d]
			if not fac:
				fac = [d] + sub
	return [total, fac]


def allmult(n):
	l = list(range(2, n))
	l = l[:len(l) // 2 + 1]
	m = set()
	for (i, n1) in enumerate(l):
		for n2 in l[i:]:
			if n1 * n2 == n:
				m.add((n1, n2))
	return m

def addPart(n, s):
	news = set()
	for t in s:
		newt = tuple(sorted(t + (n,)))
		news.add(newt)
	return news

def is_mult(l, num):
	m = 1
	for n in l:
		m *= n
	return m == num

def lastPart(newpart, n):
	lastpart = newpart.copy()
	for nums in newpart:
		nums = list(nums)
		great = max(nums)
		nums.remove(great)
		for mult in map(list, allmult(great)):
			mult.extend(nums)
			part = tuple(sorted(mult))
			if is_mult(part, n):
				lastpart.add(part)
	return lastpart

def prod_int_part(n):
	part = allmult(n)
	newpart = part
	for (n1, n2) in part:
		newpart = newpart.union(addPart(n1, allmult(n2)))
		newpart = newpart.union(addPart(n2, allmult(n1)))
	lastpart = lastPart(lastPart(newpart, n), n)
	return [len(lastpart), list(max(lastpart, key=len))] if lastpart else [0, []]


def partition(n, s=2):
	if n <= 1:
		return []
	if n < 4:
		return [[n]]
	ans = []
	while True:
		while n % s != 0:
			s += 1
		if s > n ** 0.5:
			break
		l = [s]
		p = partition(n / s, s)
		for i in p:
			x = sorted(l + i)
			if not x in ans:
				ans += [x]
		ans += [l + [n / s]]
		s += 1
	return ans

def prod_int_part(n):
	p = partition(n)
	return [len(p), min(p) if p else []]


div = lambda n: [[i, n // i] for i in range(2, int(n ** 0.5) + 1) if not n % i]

def prod_int_part(n):
	(li, parts) = (div(n), set())

	def recur(li, s=[]):
		parts.add(tuple(sorted(s)))
		for i in li:
			recur(div(i[1]), s + i if not s else s[:-1] + i)
	recur(li)
	return [len(parts) - 1, list(max(parts, key=len))]


def product_way(n, start=2):
	result = 0
	for i in range(start, n // 2 + 1):
		if n % i == 0 and i <= n / i:
			result += 1 + product_way(n // i, i)
	return result

def prod_int_part(n):
	x = product_way(n, 2)
	y = []
	m = n
	for i in range(2, n // 2 + 1):
		if n % i == 0:
			while m % i == 0:
				m /= i
				y.append(i)
	return [x, y]


def prod_int_part(n):
	ans = []
	stack = [(n, 2, [])]
	while stack:
		(v, m, divs) = stack.pop()
		for i in range(m, int(v ** 0.5) + 1):
			if v % i == 0:
				stack.append((v // i, i, divs + [i]))
				ans.append(divs + [i, v // i])
	return [len(ans), sorted(ans)[0]] if ans else [0, []]


product_numbers = {1: [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95], 2: [8, 27], 3: [12, 18, 20, 28, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, 99], 4: [16, 30, 42, 66, 70, 78, 81], 6: [24, 32, 40, 54, 56, 88], 8: [36, 72], 10: [60, 64, 84, 90], 11: [48, 80], 18: [96]}
is_prime = lambda number: all([number % i for i in range(2, number)])
PRIMES = [i for i in range(2, 100) if is_prime(i) == True]

def prod_int_part(n):
	assert n <= 100
	a = number_of_products(n)
	b = prime_factorization(n)
	return [a, b]

def number_of_products(n):
	for number in product_numbers:
		if n in product_numbers[number]:
			return number
	return 0

def prime_factorization(number):
	if number in PRIMES:
		return []
	result = []
	prime_factors = [prime for prime in PRIMES if number % prime == 0]
	for factor in prime_factors:
		while number % factor == 0:
			result.append(factor)
			number = number // factor
	return result


from math import sqrt

def non_unique_partitions(n, floor=2):
	count = 0
	for i in range(floor, int(sqrt(n)) + 1):
		if n % i == 0:
			count += 1 + non_unique_partitions(n // i, i)
	return count

def factorize_without_n(n):
	fac = []
	for i in range(2, n):
		while n % i == 0:
			fac.append(i)
			n = n // i
	return fac

def prod_int_part(n):
	return [non_unique_partitions(n), factorize_without_n(n)]


import itertools
import collections

def factorize(n):
	factors = []
	if n <= 1:
		return [n]
	for i in range(2, n + 1):
		if n <= 1:
			break
		while n % i == 0:
			factors.append(i)
			n /= i
	return factors

def prod_int_part(n):
	fac = factorize(n)
	x = len(fac) - 1
	for i in range(x):
		fac.append('/')
	perms = set(list(itertools.permutations(fac)))
	all_perm_factors = []
	for perm in perms:
		perm_factors = []
		prod = 1
		for i in range(len(perm)):
			if perm[i] != '/':
				prod *= perm[i]
			elif perm[i] == '/':
				perm_factors.append(prod)
				prod = 1
		perm_factors.append(prod)
		perm_counter = collections.Counter((x for x in perm_factors if x != 1))
		if not perm_counter in all_perm_factors:
			all_perm_factors.append(perm_counter)
	l = factorize(n)
	if len(l) == 1:
		del l[0]
	return [len(all_perm_factors) - 1, l]