Разбиения на различные множители

Question

Дано натуральное число N. Требуется найти число способов представить его в виде произведения попарно различных множителей больших 1 Вывести одно число - количество способов представить число N в виде произведения попарно различных множителей больших 1. У меня получилось написать программу для вычисления всех простых множителей числа, а что делать с ней дальше, я не знаю))

n = int(input())
arr = []
while n > 1:
    i = 2
    f = 0
    while 1:
        if n%i == 0:
            n = n // i
            arr.append(i)
            f = 1
            break
        else:
            i += 1
    if f == 1:
        continue
print(arr)

В примере было число 48 и вывод 48, 2*24, 3*16, 4*12, 6*8, 2*3*8, 2*4*6.

Answer 1

Можно так:

def distinctfivisors(n, start, l):
    if n == 1:
        print(l)
    else:
        for i in range(start, n+1):
            if n % i == 0:
                distinctfivisors(n // i, i + 1, l + [i])

distinctfivisors(72, 2, [])

>>>
[2, 3, 12]
[2, 4, 9]
[2, 36]
[3, 4, 6]
[3, 24]
[4, 18]
[6, 12]
[8, 9]
[72]

Чисто для подсчёта:

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

БЛОГ НА HUSL

Разбиения на различные множители

Ответы (1 шт):