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

@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, семиклассники не учат производные. Когда же производные начинают учить - их таки да, выводят без всяких таблиц для каждой функции.

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@Alex_ZeeKer 0 / 0 / 0 Регистрация: 17.11.2019 Сообщений: 11

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

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

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

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

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