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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
#1

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

05.04.2011, 22:50. Просмотров 1044. Ответов 12
Метки нет (Все метки)

Мучают меня днем ночью задача:

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

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

Даны три целых числа. Найти количество положительных и количество отрицательных чисел - C++
Даны три целых числа. Найти количество положительных и количество отрицательных чисел в исходном наборе. Ввод чисел и вывод результата...

Даны три целых числа. Найти количество положительных и количество отрицательных чисел в исходном наборе - C++
Помогите решить 4 задачи на C++.

дано натуральное число N. Определить,во сколько раз произведение цифр числа больше суммы цифр.Найти количество чётных цифр в записи числа!! - C++
дано натуральное число N. Определить,во сколько раз произведение цифр числа больше суммы цифр.Найти количество чётных цифр в записи числа!!...

Найти количество делителей натурального числа, больших K - C++
Помогите пожалуйста надо написать программу которая: Найти количество делителей натурального числа, больших К (К вводится).

Найти количество делителей натурального числа N. больших К - C++
Найти количество делителей натурального числа N больших К. в с++

Требуется найти количество делителей n-значного числа (n > 20) - C++
Написал программу, но выдает неправильные ответы. Когда вводишь длинное число, почти всегда дает 2, хотя делителей много и много больше....

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

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

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

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

Цитата Сообщение от Overmind024 Посмотреть сообщение
Факториза́цией натурального числа называется его разложение в произведение на натуральные множителей больше одного.
Их, понятно, может быть много.
0
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' простых делителей не вошедших в в данный набор.
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
06.04.2011, 19:32 #11
Vladimir., да, факторизация - разложение числа на простые сомножители. Но ТСа интересует разложение числа на сомножители вообще, не обязательно на простые, и это разложение он тоже назвал (ошибочно) факторизацией. И вариантов такой факторизации может быть несколько.
0
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
06.04.2011, 21:49  [ТС] #12
silent_1991, полностью прав. но назвал не я а тот кто составлял олимпиадное задание.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если все, то это только перебором всех вариантов.
не вариант так есть ограничение по времени.
0
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.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2011, 22:14
Привет! Вот еще темы с ответами:

Найти количество цифр в десятичной записи числа - C++
На C++ нужны программки Дано число N, 1: Найти количество цифр в десятичной записи числа 2: количество цифр в десятичной записи...

Найти количество положительных делителей натурального числа n - C++
Задано натуральное число n. Нужно вывести одно число - количество положительных делителей числа n.

Найти количество участков на которых числа возрастают и вывести их - C++
Масив задан рандомным количеством рандомных чисел через список. Нужно вывести на экран количество участков на которых эти числа возрастают....

Найти количество элементов массива меньших заданного числа - C++
Доброго времени суток уважаемые форумчане. Пожалуйста напишите программный код исходя из ниже предоставленного условия. Вводится...


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

Или воспользуйтесь поиском по форуму:
13
Yandex
Объявления
06.04.2011, 22:14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru