Форум программистов, компьютерный форум CyberForum.ru

Найти количество факторизаций числа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
05.04.2011, 22:50     Найти количество факторизаций числа #1
Мучают меня днем ночью задача:

Найти количество факторизаций числа. Если кто не знает
Факториза́цией натурального числа называется его разложение в произведение на натуральные множителей больше одного.
Например:
число 30
2*3*5
6*5
10*3
15*2
порядок роли не играет.
(диапазон 2 000 000)

Пытался свести к комбинаторике, не получается.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2011, 22:50     Найти количество факторизаций числа
Посмотрите здесь:

Даны три целых числа. Найти количество положительных и количество отрицательных чисел в исходном наборе C++
C++ Определить количество цифр числа,найти предпоследнюю цифру
Найти количество делителей натурального числа, больших K C++
Найти количество элементов массива, больших заданного числа C++
C++ Циклы. Найти количество цифр данного числа, больших a
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Subgrando
40 / 40 / 3
Регистрация: 28.01.2011
Сообщений: 175
05.04.2011, 22:56     Найти количество факторизаций числа #2
Тоже интересно узнать решение.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2011, 07:37     Найти количество факторизаций числа #3
Цитата Сообщение от Overmind024 Посмотреть сообщение
Найти количество факторизаций числа.
Именно количество факторизаций или просто одну любую?
Если все, то это только перебором всех вариантов.
Если одну, то перебором до первого разложения.)

Вообще, насколько мне известно, проблема факторизации больших чисел пока не имеет решения.)

2000000 число маленькое, поэтому тупо перебором.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.04.2011, 09:09     Найти количество факторизаций числа #4
Цитата Сообщение от Deviaphan Посмотреть сообщение
Вообще, насколько мне известно, проблема факторизации больших чисел пока не имеет решения
Слышу звон да не знаю где он. Перебрать простые делители люди пока не додумались чтоли?
На данный момент всего лишь неизвестно, имеет ли задача полиномиальное решение.

2000000 действительно маленькое число - разложение на простые множители находим перебором.
А вот дальше простым перебором нельзя - долго будет. Комбинаторика, думать надо.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2011, 09:44     Найти количество факторизаций числа #5
Цитата Сообщение от Хохол Посмотреть сообщение
Слышу звон да не знаю где он.
Да, именно так. Только краем уха слышал.)
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.04.2011, 09:48     Найти количество факторизаций числа #6
Хотя фиг знает, тут простых делителей-то не более 20 штук. Может и простым перебором нормально написать получится.
МаксимМВ
C/C++
90 / 90 / 5
Регистрация: 01.07.2010
Сообщений: 281
06.04.2011, 10:22     Найти количество факторизаций числа #7
ну решу попробую
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 13:52     Найти количество факторизаций числа #8
улыбнули =) без обид.
Найти количество факторизаций числа.
я Вам и без компьютера ответ скажу - одна.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.04.2011, 18:40     Найти количество факторизаций числа #9
Vladimir., а вот и нет, в условии было специально дано локальное определение:

Цитата Сообщение от Overmind024 Посмотреть сообщение
Факториза́цией натурального числа называется его разложение в произведение на натуральные множителей больше одного.
Их, понятно, может быть много.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 19:26     Найти количество факторизаций числа #10
Факторизацией натурального числа называется его разложение в произведение простых чисел. Она будет уникальной для каждого натурального числа с точностью до порядка следования сомножителей.
Если это не так - пруфлинк пожалуйста.
=========================

как найти то, что хочет посчитать топикстартер:
  1. разложить число http://www.cyberforum.ru/cgi-bin/latex.cgi?N на простые сомножители (пусть n штук, множество простых сомножителей http://www.cyberforum.ru/cgi-bin/latex.cgi?X)
  2. перебрать все наборы из k элементов множества http://www.cyberforum.ru/cgi-bin/latex.cgi?X (иначе http://www.cyberforum.ru/cgi-bin/latex.cgi? C^k_n ) для всех возможных k (произведение элементов входящих в сочетание будет натуральным делителем числа http://www.cyberforum.ru/cgi-bin/latex.cgi?N.)
  3. для каждого такого набора повторить шаг 2 на подмножестве http://www.cyberforum.ru/cgi-bin/latex.cgi?X' простых делителей не вошедших в в данный набор.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.04.2011, 19:32     Найти количество факторизаций числа #11
Vladimir., да, факторизация - разложение числа на простые сомножители. Но ТСа интересует разложение числа на сомножители вообще, не обязательно на простые, и это разложение он тоже назвал (ошибочно) факторизацией. И вариантов такой факторизации может быть несколько.
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
06.04.2011, 21:49  [ТС]     Найти количество факторизаций числа #12
silent_1991, полностью прав. но назвал не я а тот кто составлял олимпиадное задание.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если все, то это только перебором всех вариантов.
не вариант так есть ограничение по времени.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2011, 22:14     Найти количество факторизаций числа
Еще ссылки по теме:

C++ Найти количество четных цифр заданного натурального числа
Найти количество четных цифр заданного натурального числа C++
Найти количество различных цифр данного натурального числа C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 22:14     Найти количество факторизаций числа #13
"господа, я свалял большого дурака" (с).
========
Предложеный мной алгоритм ошибочен так как даёт не количество разложений N на натуральные сомножители, а лишь ограничение сверху. Так для числа 8 алгоритм пройдет по разложениям 8 = 2*2*2 = 2*4 = 4*2 и вернёт 3. Хотя очевидно, что второе и третье разложения идентичны и правильный ответ 2.
Yandex
Объявления
06.04.2011, 22:14     Найти количество факторизаций числа
Ответ Создать тему
Опции темы

Текущее время: 17:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru