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

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

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

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

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

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

Печатает очень большие числа в колонке "Y"" C++
C++ Найти все делители числа P
Найти все делители натурального числа n C++
Найти все делители натурального числа N C++
Найти все делители числа 1234 C++
C++ Необходимо найти и записать в стек числа, в состав которых входит 1 символ "*"
Найти в строке слово, начинающееся буквой "а" и оканчивающееся буквой "я" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2308 / 1934 / 192
Регистрация: 03.07.2012
Сообщений: 6,923
Записей в блоге: 1
16.07.2014, 19:24     Найти делители "длинного" числа #21
У Вы уверены, что число в задании не специально подобрано так, чтобы их можно было найти за разумное время?

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

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

Не по теме:

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


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

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

Не по теме:

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

Код
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

zer0mail
2308 / 1934 / 192
Регистрация: 03.07.2012
Сообщений: 6,923
Записей в блоге: 1
16.07.2014, 21:09     Найти делители "длинного" числа #23
Че их искать - число простое
NEbO
587 / 455 / 49
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
Завершенные тесты: 1
16.07.2014, 21:33     Найти делители "длинного" числа #24
ну логично, иначе б задача была нерешаемая чем докажете?)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 22:52     Найти делители "длинного" числа
Еще ссылки по теме:

Найти слово, начинающееся буквой "а" и оканчивающееся буквой "я" C++
C++ Многократное "длинное" деление (длинного на короткое)
Класс "Комплексные числа". Отсортировать массив по возрастанию модуля комплексного числа C++
C++ Найти делители натурального числа
Функции: для каждого числа последовательности найти количество цифр "5" C++

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

Или воспользуйтесь поиском по форуму:
volvo
Супер-модератор
 Аватар для volvo
22346 / 14523 / 4118
Регистрация: 22.10.2011
Сообщений: 25,723
Записей в блоге: 3
16.07.2014, 22:52     Найти делители "длинного" числа #25
Цитата Сообщение от NEbO Посмотреть сообщение
чем докажете?
2521-1, ключевое слово - Мерсенн
Yandex
Объявления
16.07.2014, 22:52     Найти делители "длинного" числа
Ответ Создать тему
Опции темы

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