Разложить большое число на множители

@Alex_ZeeKer · Регистрация: 17.11.2019

Задача такова: на вход подается очень большое число(больше 11 знаков), нужно при помощи длинной арифметики разложить его на простые множители. Сам я с длинной арифметикой не сталкивался и не знаю как реализовать свой алгоритм.

Байт · 27.11.2019, 13:31

Сообщение от Alex_ZeeKer

я с длинной арифметикой не сталкивался и не знаю как реализовать

Где-то я слышал такую фразу - "Каждый уважающий себя программист (или собирающийся себя уважать) хоть раз в жизни делал свою собственную маленькую длинку"
Можно, конечно, взять готовый пакет. Но имхо, интереснее сделать самому. Это не очень сложно. Надо просто вспомнить, как в начальных классах школы учили складывать, умножать и делить "столбиком". Вы ведь навярняка это умеете. А теперь попробуйте объяснить свое умение туповатенькому, но исполнительному роботу.
Тут очень важно выбрать правильное представление, чтобы в дальнейшем не завязнуть в не имеющих отношения деталях.

@Renji · 27.11.2019, 14:23

Сообщение от Alex_ZeeKer

Задача такова: на вход подается очень большое число(больше 11 знаков)

Берите 64-битовый long long и не морочьте голову (18 знаков точно потянет).

@Alex_ZeeKer · 27.11.2019, 14:48 **[ТС]**

Уже пробовал, препод не зачел, мол, надо через строки)

@bedvit · 27.11.2019, 16:47

Быстрый алгоритмы поиска простых/всех делителей натурального числа (в т.ч. факторизация натурального числа)С++

Байт · 27.11.2019, 19:27

Сообщение от Renji

и не морочьте голову

Это точно

Добавлено через 6 минут
Ибо голова нам дана не для того чтобы думать, а чтобы быстренько подъискать готовые решения, пусть даже совершенно неадекватные. А вдруг удастся обмануть и пройти пару первых тестов?
Увы!

Сообщение от Alex_ZeeKer

пробовал, препод не зачел,

Но это ничего! Может быть прохезает в другом случае.
Но главное - дать дельный совет.

Добавлено через 8 минут

Сообщение от Alex_ZeeKer

очень большое число(больше 11 знаков)

Вот тут неплохо бы указать верхнюю границу. Так как ежели знаков более чем 2000000000, то надо будет другую технику применять. А уж ежели еще в 1000 раз больше, то совсем другую организацию решения задачи. Если увеличит этот предел еще в 1000 раз, то придется сдаться. В данное время все компьютеры мира эту задачу не решат.

@Renji · 27.11.2019, 21:28

Сообщение от Байт

Ибо голова нам дана не для того чтобы думать, а чтобы быстренько подъискать готовые решения, пусть даже совершенно неадекватные. А вдруг удастся обмануть и пройти пару первых тестов?

О чем думать то предлагается?
1) Решаем задачу методом перебора множителей. Экспоненциальная сложность, на 128-битовых числах алгоритм скорее всего просто зависнет. Так нафига нам поддерживать больше 64 бит?
2) Решаем задачу каким-то навороченным способом с субэкспоненциальной сложностью. Да, да, вот прям сейчас сядем изобретать с нуля готовые алгоритмы из учебника высшей математики. Давайте еще с семиклассников потребуем чтоб понятие производной и интеграла сами вывели. А то ишь, развелось халявщиков, таблицу производных и первообразных им подавай.

Как ни крути, а задача именно на то чтобы найти и закодить готовое решение. Ну вот такой препод топикстартеру попался.

Байт · 27.11.2019, 23:17

Сообщение от Renji

Как ни крути,

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

Байт · 28.11.2019, 11:06

Пришел в голову любопытный подход к факторизации.
Составляем произведение нескольких первых простых, например 210. Находим остаток деления исследуемого числа на 210. Этот остаток проверяем на делимость на 2, 3, 5, 7 ...
Далее берем произведение следующих нескольких простых P = 11*13*17*19. Делим на него....
Общее количество операций этот подход не уменьшает. Даже увеличивает. Линейно. Но уменьшает количество длинных операций.
И если K - наибольшее представимое в целом типе, то для анализа чисел < K² такой подход должен неплохо работать...
Я прекрасно понимаю, что это не те числа, факторизация которых может представлять промышленный интерес...

@Kuzia domovenok · 28.11.2019, 11:11

Renji, семиклассники не учат производные. Когда же производные начинают учить - их таки да, выводят без всяких таблиц для каждой функции.

@Alex_ZeeKer 0 / 0 / 0 Регистрация: 17.11.2019 Сообщений: 10
		1
	Разложить большое число на множители 27.11.2019, 13:05. Показов 2027. Ответов 9 Метки нет (Все метки) Задача такова: на вход подается очень большое число(больше 11 знаков), нужно при помощи длинной арифметики разложить его на простые множители. Сам я с длинной арифметикой не сталкивался и не знаю как реализовать свой алгоритм. __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	27.11.2019, 13:31	2
	Сообщение от Alex_ZeeKer я с длинной арифметикой не сталкивался и не знаю как реализовать Где-то я слышал такую фразу - "Каждый уважающий себя программист (или собирающийся себя уважать) хоть раз в жизни делал свою собственную маленькую длинку" Можно, конечно, взять готовый пакет. Но имхо, интереснее сделать самому. Это не очень сложно. Надо просто вспомнить, как в начальных классах школы учили складывать, умножать и делить "столбиком". Вы ведь навярняка это умеете. А теперь попробуйте объяснить свое умение туповатенькому, но исполнительному роботу. Тут очень важно выбрать правильное представление, чтобы в дальнейшем не завязнуть в не имеющих отношения деталях. 1

@Renji 2758 / 1912 / 569 Регистрация: 05.06.2014 Сообщений: 5,561
	27.11.2019, 14:23	3
	Сообщение от Alex_ZeeKer Задача такова: на вход подается очень большое число(больше 11 знаков) Берите 64-битовый long long и не морочьте голову (18 знаков точно потянет). 0

@Alex_ZeeKer 0 / 0 / 0 Регистрация: 17.11.2019 Сообщений: 10
	27.11.2019, 14:48 [ТС]	4
	Уже пробовал, препод не зачел, мол, надо через строки) 0

@bedvit 1024 / 227 / 21 Регистрация: 20.05.2016 Сообщений: 971 Записей в блоге: 19
	27.11.2019, 16:47	5
	Быстрый алгоритмы поиска простых/всех делителей натурального числа (в т.ч. факторизация натурального числа)С++ 1

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	27.11.2019, 19:27	6
	Сообщение от Renji и не морочьте голову Это точно Добавлено через 6 минут Ибо голова нам дана не для того чтобы думать, а чтобы быстренько подъискать готовые решения, пусть даже совершенно неадекватные. А вдруг удастся обмануть и пройти пару первых тестов? Увы! Сообщение от Alex_ZeeKer пробовал, препод не зачел, Но это ничего! Может быть прохезает в другом случае. Но главное - дать дельный совет. Добавлено через 8 минут Сообщение от Alex_ZeeKer очень большое число(больше 11 знаков) Вот тут неплохо бы указать верхнюю границу. Так как ежели знаков более чем 2000000000, то надо будет другую технику применять. А уж ежели еще в 1000 раз больше, то совсем другую организацию решения задачи. Если увеличит этот предел еще в 1000 раз, то придется сдаться. В данное время все компьютеры мира эту задачу не решат. 0

@Renji 2758 / 1912 / 569 Регистрация: 05.06.2014 Сообщений: 5,561
	27.11.2019, 21:28	7
	Сообщение от Байт Ибо голова нам дана не для того чтобы думать, а чтобы быстренько подъискать готовые решения, пусть даже совершенно неадекватные. А вдруг удастся обмануть и пройти пару первых тестов? О чем думать то предлагается? 1) Решаем задачу методом перебора множителей. Экспоненциальная сложность, на 128-битовых числах алгоритм скорее всего просто зависнет. Так нафига нам поддерживать больше 64 бит? 2) Решаем задачу каким-то навороченным способом с субэкспоненциальной сложностью. Да, да, вот прям сейчас сядем изобретать с нуля готовые алгоритмы из учебника высшей математики. Давайте еще с семиклассников потребуем чтоб понятие производной и интеграла сами вывели. А то ишь, развелось халявщиков, таблицу производных и первообразных им подавай. Как ни крути, а задача именно на то чтобы найти и закодить готовое решение. Ну вот такой препод топикстартеру попался. 0

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	27.11.2019, 23:17	8
	Сообщение от Renji Как ни крути, Доводы ваши чрезвычайно убедительны. И прозорливость того, что нужно неразумному преподу от бедолаги ТС выше всяких похвал. Цитировать не буду. Стартовый топик у вас перед глазами. 0

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	28.11.2019, 11:06	9
	Пришел в голову любопытный подход к факторизации. Составляем произведение нескольких первых простых, например 210. Находим остаток деления исследуемого числа на 210. Этот остаток проверяем на делимость на 2, 3, 5, 7 ... Далее берем произведение следующих нескольких простых P = 111317*19. Делим на него.... Общее количество операций этот подход не уменьшает. Даже увеличивает. Линейно. Но уменьшает количество длинных операций. И если K - наибольшее представимое в целом типе, то для анализа чисел < K² такой подход должен неплохо работать... Я прекрасно понимаю, что это не те числа, факторизация которых может представлять промышленный интерес... 0

@Kuzia domovenok 3980 / 3250 / 909 Регистрация: 25.03.2012 Сообщений: 12,084 Записей в блоге: 1
	28.11.2019, 11:11	10
	Renji, семиклассники не учат производные. Когда же производные начинают учить - их таки да, выводят без всяких таблиц для каждой функции. 0

Опции темы