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

@nukee93 · Регистрация: 09.10.2020

Студворк — интернет-сервис помощи студентам

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

@Gdez · 09.10.2020, 19:27

nukee93, В задаче "попарно", а в примере есть 3.
Так как нужно?

@nukee93 · 09.10.2020, 19:30 **[ТС]**

Попарно РАЗЛИЧНЫХ, а не пары

@eaa · 09.10.2020, 19:35

nukee93,
Нормально задачу напишите. Входные/выходные данные какие?

@nukee93 · 09.10.2020, 19:39 **[ТС]**

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

@art_em_ · 09.10.2020, 19:41

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

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

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

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

В первой строке содержится одно натуральное число 2 \leq N \leq 10^{12}2≤ N ≤10
12
.

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

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

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

Sample Input:

48
Sample Output:

7

@Gdez · 09.10.2020, 19:50

nukee93, тогда может так :
Находишь первый множитель. Формируешь список. Для второго множителя то же самое с проверкой - есть ли уже такой набор.
Например, 48 . Ищешь до sqrt(48) -> до 6. Первый -> 2
[2,24]. Добавляешь в множество
24 - ищешь множитель<sqrt(24) и > 2 -> 3 -> [3,8]. Формируешь [2,3,8]. Добавляешь в множество
8 -> множитель <sqrt(8) и > 3 - нет.
Снова 48. Следующий -> 3
[3,16]. Добавляешь в множество
16 -> множитель <sqrt(16) и > 3 -> нет.
И так далее...

@eaa · 09.10.2020, 21:36

факторизацию можно так переписать:

Python
1
2
3
4
5
6
7
8
9
10
11
n = 48
i = 2
f = []
while i*i <= n:
    if n % i == 0:
        n //= i
        f.append(i)
    else:
        i += 1
f.append(n)
print(f)

nukee93, ваш код вообще не понятен.

@art_em_ · 10.10.2020, 11:22

И код не тот
Там надо количество таких разложений а не само разложение

@eaa · 10.10.2020, 12:10

а сколько каноническим разложением числа на простые множители существует?

Новые блоги и статьи Все статьи Все блоги /
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Данные берутся из. . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	09.10.2020, 19:27
	nukee93, В задаче "попарно", а в примере есть 3. Так как нужно? 0

@nukee93 0 / 0 / 0 Регистрация: 09.10.2020 Сообщений: 4
	09.10.2020, 19:30 [ТС]
	Попарно РАЗЛИЧНЫХ, а не пары 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.10.2020, 19:35
	nukee93, Нормально задачу напишите. Входные/выходные данные какие? 0

@nukee93 0 / 0 / 0 Регистрация: 09.10.2020 Сообщений: 4
	09.10.2020, 19:39 [ТС]
	Формат входных данных В первой строке содержится одно натуральное число больше или равное двум. Формат выходных данных Вывести одно число - количество способов представить число N в виде произведения попарно различных множителей больших 1. 0

@art_em_ 0 / 1 / 0 Регистрация: 09.10.2020 Сообщений: 8
	09.10.2020, 19:41
	Задача E. Разбиения на различные множители Эта задача формулируется предельно кратко. Дано натуральное число N. Требуется найти число способов представить его в виде произведения попарно различных множителей больших 1. Формат входных данных В первой строке содержится одно натуральное число 2 \leq N \leq 10^{12}2≤ N ≤10 12 . Формат выходных данных Вывести одно число - количество способов представить число N в виде произведения попарно различных множителей больших 1. Пояснение к примеру. Имеется 7 различных способов представить число 48 в виде произведения (в том числе и вырожденного) попарно различных множителей больших 1: 48, 224, 316, 412, 68, 238, 246. Sample Input: 48 Sample Output: 7 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	09.10.2020, 19:50
	nukee93, тогда может так : Находишь первый множитель. Формируешь список. Для второго множителя то же самое с проверкой - есть ли уже такой набор. Например, 48 . Ищешь до sqrt(48) -> до 6. Первый -> 2 [2,24]. Добавляешь в множество 24 - ищешь множитель<sqrt(24) и > 2 -> 3 -> [3,8]. Формируешь [2,3,8]. Добавляешь в множество 8 -> множитель <sqrt(8) и > 3 - нет. Снова 48. Следующий -> 3 [3,16]. Добавляешь в множество 16 -> множитель <sqrt(16) и > 3 -> нет. И так далее... 0

@art_em_ 0 / 1 / 0 Регистрация: 09.10.2020 Сообщений: 8
	10.10.2020, 11:22
	И код не тот Там надо количество таких разложений а не само разложение 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	10.10.2020, 12:10
	а сколько каноническим разложением числа на простые множители существует? 0