temchik_ggg Ответов: 2

Число факторизаций числа.

Task. Splits into different multipliers

This task is formulated very briefly.

Given a natural number N. you need to find the number of ways to represent it as a product of pairwise different factors greater than 1.

The format of the input data

The first line contains a single natural number 2 < = N < = 10^12 .

Output format

Output a single number - the number of ways to represent the number N as a product of pairwise different factors greater than 1.

Explanation for example. There are 7 different ways to represent the number 48 as a product (including a degenerate one) of pairwise different multipliers. 1: 48, 2 * 24, 3 * 16, 4 * 12, 6 *8, 2 * 3 * 8, 2 * 4 * 6.


Что я уже пробовал:

Я пытался написать алгоритм и искал математическую формулу.

Greg Utas

"Попарно неравные"? Так что это исключается 2*2*12 например?

Я не понимаю почему 2*6*4 и еще 4*6*2 и то и другое должно быть учтено.

А как насчет 2*24?

Вы также сказали больше 1, так что 48(*1) не должны считаться.

temchik_ggg

Извините, что я ошибся, вот исправленный вопрос.

Задача. Разбивается на разные множители

Эта задача сформулирована очень кратко.

Дано натуральное число N. вам нужно найти количество способов представить его как произведение попарно различных множителей больше 1.

Формат входных данных

Первая строка содержит единственное натуральное число 2 < = N < = 10^12 .

Выходной формат

Выведите одно число - количество способов представления числа N в виде произведения попарно различных множителей больше 1.

Например, объяснение. Существует 7 различных способов представления числа 48 в виде произведения (в том числе вырожденного) попарно различных множителей. 1: 48, 2 * 24, 3 * 16, 4 * 12, 6 *8, 2 * 3 * 8, 2 * 4 * 6.

Richard MacCutchan

Начните с числа, разделенного на 2. Это первый (возможный) фактор. Как Патрис предлагает ниже, используйте функцию modulo, чтобы увидеть, является ли это допустимым фактором. Затем сделайте то же самое для каждого значения ниже этого значения вплоть до 2.

2 Ответов

Рейтинг:
2

Patrice T

Как заметил Грег в комментарии, ваш пример не имеет никакого смысла.

В случае целочисленной факторизации операция выполняется по модулю.
Модуль дает напоминание о целочисленном делении. Когда модуль равен 0, вы получаете коэффициент.
Операция по модулю - Википедия[^]

CPallini

5.

Patrice T

Спасибо

temchik_ggg

Извините, что я ошибся, вот исправленный вопрос.

Задача. Разбивается на разные множители

Эта задача сформулирована очень кратко.

Дано натуральное число N. вам нужно найти количество способов представить его как произведение попарно различных множителей больше 1.

Формат входных данных

Первая строка содержит единственное натуральное число 2 < = N < = 10^12 .

Выходной формат

Выведите одно число - количество способов представления числа N в виде произведения попарно различных множителей больше 1.

Например, объяснение. Существует 7 различных способов представления числа 48 в виде произведения (в том числе вырожденного) попарно различных множителей. 1: 48, 2 * 24, 3 * 16, 4 * 12, 6 *8, 2 * 3 * 8, 2 * 4 * 6.

Patrice T

Воспользуйся Улучшить вопрос чтобы обновить ваш вопрос.
Чтобы каждый мог обратить внимание на эту информацию.

Рейтинг:
0

temchik_ggg 

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

num = int(input())
ans = algorithm(num)
print(ans)

Richard MacCutchan

Ваше начальное значение должно быть n/2, что является максимально возможным фактором. И ваш цикл должен отсчитываться от этого значения до 2, которое является наименьшим.