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

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

27.11.2019, 13:05. Показов 2027. Ответов 9
Метки нет (Все метки)

Задача такова: на вход подается очень большое число(больше 11 знаков), нужно при помощи длинной арифметики разложить его на простые множители. Сам я с длинной арифметикой не сталкивался и не знаю как реализовать свой алгоритм.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.11.2019, 13:05
Ответы с готовыми решениями:

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

Разложить число на простые множители
Дано натуральное число n. Напечатать разложение этого числа на простые множители. Реализовать два...

Разложить число на простые множители
Я для этого написал программу : #include <stdio.h> #define MAXN 1000 int main(){ ...

Разложить натуральное число на простые множители
Разложить натуральное число на простые множители.(Нужно максимально простое решение, для новичков)

9
Диссидент
Эксперт C
27192 / 16949 / 3745
Регистрация: 24.12.2010
Сообщений: 38,132
27.11.2019, 13:31 2
Цитата Сообщение от Alex_ZeeKer Посмотреть сообщение
я с длинной арифметикой не сталкивался и не знаю как реализовать
Где-то я слышал такую фразу - "Каждый уважающий себя программист (или собирающийся себя уважать) хоть раз в жизни делал свою собственную маленькую длинку"
Можно, конечно, взять готовый пакет. Но имхо, интереснее сделать самому. Это не очень сложно. Надо просто вспомнить, как в начальных классах школы учили складывать, умножать и делить "столбиком". Вы ведь навярняка это умеете. А теперь попробуйте объяснить свое умение туповатенькому, но исполнительному роботу.
Тут очень важно выбрать правильное представление, чтобы в дальнейшем не завязнуть в не имеющих отношения деталях.
1
2758 / 1912 / 569
Регистрация: 05.06.2014
Сообщений: 5,561
27.11.2019, 14:23 3
Цитата Сообщение от Alex_ZeeKer Посмотреть сообщение
Задача такова: на вход подается очень большое число(больше 11 знаков)
Берите 64-битовый long long и не морочьте голову (18 знаков точно потянет).
0
0 / 0 / 0
Регистрация: 17.11.2019
Сообщений: 10
27.11.2019, 14:48  [ТС] 4
Уже пробовал, препод не зачел, мол, надо через строки)
0
Диссидент
Эксперт C
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
2758 / 1912 / 569
Регистрация: 05.06.2014
Сообщений: 5,561
27.11.2019, 21:28 7
Цитата Сообщение от Байт Посмотреть сообщение
Ибо голова нам дана не для того чтобы думать, а чтобы быстренько подъискать готовые решения, пусть даже совершенно неадекватные. А вдруг удастся обмануть и пройти пару первых тестов?
О чем думать то предлагается?
1) Решаем задачу методом перебора множителей. Экспоненциальная сложность, на 128-битовых числах алгоритм скорее всего просто зависнет. Так нафига нам поддерживать больше 64 бит?
2) Решаем задачу каким-то навороченным способом с субэкспоненциальной сложностью. Да, да, вот прям сейчас сядем изобретать с нуля готовые алгоритмы из учебника высшей математики. Давайте еще с семиклассников потребуем чтоб понятие производной и интеграла сами вывели. А то ишь, развелось халявщиков, таблицу производных и первообразных им подавай.

Как ни крути, а задача именно на то чтобы найти и закодить готовое решение. Ну вот такой препод топикстартеру попался.
0
Диссидент
Эксперт C
27192 / 16949 / 3745
Регистрация: 24.12.2010
Сообщений: 38,132
27.11.2019, 23:17 8
Цитата Сообщение от Renji Посмотреть сообщение
Как ни крути,
Доводы ваши чрезвычайно убедительны. И прозорливость того, что нужно неразумному преподу от бедолаги ТС выше всяких похвал. Цитировать не буду. Стартовый топик у вас перед глазами.
0
Диссидент
Эксперт C
27192 / 16949 / 3745
Регистрация: 24.12.2010
Сообщений: 38,132
28.11.2019, 11:06 9
Пришел в голову любопытный подход к факторизации.
Составляем произведение нескольких первых простых, например 210. Находим остаток деления исследуемого числа на 210. Этот остаток проверяем на делимость на 2, 3, 5, 7 ...
Далее берем произведение следующих нескольких простых P = 11*13*17*19. Делим на него....
Общее количество операций этот подход не уменьшает. Даже увеличивает. Линейно. Но уменьшает количество длинных операций.
И если K - наибольшее представимое в целом типе, то для анализа чисел < K2 такой подход должен неплохо работать...
Я прекрасно понимаю, что это не те числа, факторизация которых может представлять промышленный интерес...
0
3980 / 3250 / 909
Регистрация: 25.03.2012
Сообщений: 12,084
Записей в блоге: 1
28.11.2019, 11:11 10
Renji, семиклассники не учат производные. Когда же производные начинают учить - их таки да, выводят без всяких таблиц для каждой функции.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.11.2019, 11:11
Помогаю со студенческими работами здесь

Разложить заданное число на простые множители
Ребята помогите реализовать задачу: разложить заданное число на простые множители.

Разложить число на множители используя рекурсию
Нужно сделать программу вот условия : Разложить на множители число при помо рекурсии. В массиве...

Разложить число на простые множители через массив
разложить сложное число на простые множители, через массив.

Разложить на множители число с помощью рекурсии, найти НОД
Разложить на множители число с помощью рекурсии. В массиве целых чисел , которые являются собой...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru