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

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

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

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

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

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

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

Найти все трехзначные числа: "Само число и сумма цифр этого числа делятся на одно и то же число P" - C++
Помогите решить задачу :Найти все целые 3-х знатные числа,удовлетворяющие условию:Само число и сумма цифр этого числа делятся на одно и то...

Функции: для каждого числа последовательности найти количество цифр "5" - C++
Вводится последовательность из N целых чисел. Для каждого числа последовательности найти количество цифр 5 (функцией оформить определение...

Необходимо найти и записать в стек числа, в состав которых входит 1 символ "*" - C++
Необходимо написать алгоритм поиска в строке чисел. Условие: дан набор символов - строка произвольного размера. "Слова" в строке разделены...

Печатает очень большие числа в колонке "Y"" - C++
#include<stdio.h> #include<iostream> void variant_1(){ double Xn,Xk,dX,y,b,a,c; printf("Enter Xn, Xk, dX, a, b...

Класс "Комплексные числа". Отсортировать массив по возрастанию модуля комплексного числа - C++
Создать массив из 10 значений типа комплекс и отсортировать его по возрастанию модуля комплексного числа. Сказали через цикл вызывать...

Найти в строке слово, начинающееся буквой "а" и оканчивающееся буквой "я" - C++
дана строка. найти какое-нибудь слово, начинающееся буквой а и оканчивающееся буквой я. если таких слов нет, то сообщить об этом ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2330 / 1956 / 192
Регистрация: 03.07.2012
Сообщений: 7,013
Записей в блоге: 1
16.07.2014, 19:24     Найти делители "длинного" числа #21
У Вы уверены, что число в задании не специально подобрано так, чтобы их можно было найти за разумное время?

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

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

Не по теме:

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


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

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

Не по теме:

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

Код
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

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

Найти делители натурального числа - C++
Создать список делителей введенного с клавиатуры натурального числа и вывести его на экран. Вот пример программы со списком и основная...

Найти все делители числа P - C++
Помогите студентке пожалуйста сделать задачу. Требуется найти все делители числа Р. Задачу я решила, но препод сказал сделать с...

Найти слово, начинающееся буквой "а" и оканчивающееся буквой "я" - C++
дана строка. найти какое-нибудь слово, начинающееся буквой а и оканчивающееся буквой я. если таких слов нет, то сообщить об этом

Найти все делители числа 1234 - C++
Найти все делители числа 1234

Найти все делители натурального числа n - C++
Всем Привет ! Нужно написать прогу с использованием пользовательских функций. И пожалуйста облегчите мне задачу ) укажите строки с...


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

Или воспользуйтесь поиском по форуму:
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
23234 / 15225 / 4423
Регистрация: 22.10.2011
Сообщений: 27,070
Записей в блоге: 4
16.07.2014, 22:52     Найти делители "длинного" числа #25
Цитата Сообщение от NEbO Посмотреть сообщение
чем докажете?
2521-1, ключевое слово - Мерсенн
Yandex
Объявления
16.07.2014, 22:52     Найти делители "длинного" числа
Ответ Создать тему
Опции темы

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