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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
movielucky
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 13
#1

Найти делители "длинного" числа - C++

15.07.2014, 11:03. Просмотров 1851. Ответов 24
Метки нет (Все метки)

Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2014, 11:03
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти делители "длинного" числа (C++):

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений - C++
Здравствуйте, помогите написать две программы. 1) Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива. - C++
Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива. ...

Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол" - C++
кто то напишите пожалуйста, вот программа: наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные...

Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей"; - C++
Помогите пожалуйста с задачей. Могу сделать ее просто, но надо через ООП и у меня не получается. Дано натуральное число N (N<20),...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

24
Sergio Leone
2461 / 1106 / 403
Регистрация: 07.06.2014
Сообщений: 3,259
15.07.2014, 23:30 #16
Цитата Сообщение от dogg12 Посмотреть сообщение
Тогда подобный вопрос должен стоять явно не в разделе для начинающих)
Так автор этого вопроса явно не видит в нём никаких проблем


кстати, он создал дублирующую тему в разделе Java. Ему неважно, на C++ ему напишут программу или на Java. Главное, чтобы она нашла все делители его числа. Он и не подозревает, что скорее наше солнце погаснет, чем программа досчитает до конца.
0
andreyfreelans
64 / 30 / 6
Регистрация: 21.02.2011
Сообщений: 1,841
15.07.2014, 23:37 #17
Это у нас с вами "простые компьютеры", может человек работает в каком-нибудь супер-пупер мощном вычислительным центре, где большое количество навороченных ЭВМ справятся с такой задачей. Обычно подобные вопросы в таких местах и решают. Люди в НИИ работают над этим годами, а тут на форуме спрашивают... Человечество прогрессирует так сказать)
0
Psilon
Master of Orion
Эксперт .NET
5932 / 4831 / 636
Регистрация: 10.07.2011
Сообщений: 14,439
Записей в блоге: 5
Завершенные тесты: 4
15.07.2014, 23:44 #18
Sergio Leone, Да ладно, кто-то же должен изобретать bogo sort и подобные алгоритмы

movielucky, предлагаю находить хэш от строки из 12 тыс символов, после этого обработать его как-нибудь (умножить/разделить и т.п.) и распечатать как вывод. Если преподаватель засомневается, попросите его перепроверить результат. Пятерка вам гарантированна!

Добавлено через 4 минуты
dogg12, самый мощный компьютер в мире имеет производительность около 20 петафлопс. Принимая допущения выше, 106000/1020... На самом деле, тут не особо важна мощностью компьютера. Компьютер с мощностью 1 флопс проверит за 106000 секунд, а супер-компьютер, который имеет триллион квадралионов флопсов (1012 *1015) проверит число за 105973 секунд (при этом такая производительность сегодня даже в самых смелых мечтах не видится, это в миллион раз мощнее самого мощного суперкомпьютера современности). Так что не принципиально, на кор ай семь или зеоне считается, или на интел 8087, тепловая смерть вселенной наступит намного раньше
0
zer0mail
2445 / 2079 / 205
Регистрация: 03.07.2012
Сообщений: 7,557
Записей в блоге: 1
16.07.2014, 18:10 #19
Ищи простые делители с кратностью.
0
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
25277 / 16925 / 5343
Регистрация: 22.10.2011
Сообщений: 29,941
Записей в блоге: 6
16.07.2014, 18:19 #20
zer0mail, сколько времени твоей программе понадобится, чтобы найти делители числа:
Код
146783911423364576743092536350764769178885886396876485026777655885608637226256065354828356063571819406295041
?
1
zer0mail
2445 / 2079 / 205
Регистрация: 03.07.2012
Сообщений: 7,557
Записей в блоге: 1
16.07.2014, 19:24 #21
У Вы уверены, что число в задании не специально подобрано так, чтобы их можно было найти за разумное время?

Добавлено через 50 минут
Например, для 10094000 (это более 12тыс знаков) мой подход легко найдет все делители

Не исключаю также, что в задании нужно было найти все простые делители.
0
NEbO
591 / 458 / 49
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
Завершенные тесты: 3
16.07.2014, 20:36 #22

Не по теме:

... тем временем movielucky открыл десятую пачку поп-корна ...


по поводу алгоритма -- представьте число в виде простых делителей, как в школе делали. есть такая штука как решето эратосфена, еще щас нагуглил какие-то другие решета, например http://ru.wikipedia.org/wiki/%D0%A0%...B8%D0%BD%D0%B0
возможно, оно также представимо в разреженном виде (пока не вникал), тогда можно будет контролировать рост памяти.
все делители получаются перемножением простых (подождемс еще пару больших взрывов), но и так вы их количество даже тупо на все винчестеры мира не запишите. Более того, если бы винчестер представлял из себя атом, и эти атомы заполняли бы всю обозримую вселенную, и в каждом таком атоме помещалось бы по экзабайту, к примеру, вам понадобилось бы еще штук 2^10000 таких вселенных.
люди, займитесь делом, чесслово. докажите лучше гипотезу Римана, вам еще и лям баксов за это дадут

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

Не по теме:

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

Код
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

1
zer0mail
2445 / 2079 / 205
Регистрация: 03.07.2012
Сообщений: 7,557
Записей в блоге: 1
16.07.2014, 21:09 #23
Че их искать - число простое
1
NEbO
591 / 458 / 49
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
Завершенные тесты: 3
16.07.2014, 21:33 #24
ну логично, иначе б задача была нерешаемая чем докажете?)))
0
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
25277 / 16925 / 5343
Регистрация: 22.10.2011
Сообщений: 29,941
Записей в блоге: 6
16.07.2014, 22:52 #25
Цитата Сообщение от NEbO Посмотреть сообщение
чем докажете?
2521-1, ключевое слово - Мерсенн
2
16.07.2014, 22:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 22:52
Привет! Вот еще темы с ответами:

Многократное "длинное" деление (длинного на короткое) - C++
В общем есть задача на перевод с одной системы счисления в другие, где нужно использовать длинную арифметику (деление длинного на...

Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку - C++
Здравствуйте. Задача следующая: Найти все целые числа из промежутка от a до b, у которых количество делителей равно k. К примеру я взял...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс "вентилятор" содержащий в себе классы:...


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

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

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