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

@movielucky · Регистрация: 14.12.2013

Author24 — интернет-сервис помощи студентам

Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?

zer0mail · 16.07.2014, 19:24

У Вы уверены, что число в задании не специально подобрано так, чтобы их можно было найти за разумное время?

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

Не исключаю также, что в задании нужно было найти все простые делители.

NEbO · 16.07.2014, 20:36

Не по теме:

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

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

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

Не по теме:

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

Код

6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

zer0mail · 16.07.2014, 21:09

Че их искать - число простое

NEbO · 16.07.2014, 21:33

ну логично, иначе б задача была нерешаемая

чем докажете?)))

@volvo · 16.07.2014, 22:52

Сообщение от NEbO

чем докажете?

2⁵²¹-1, ключевое слово - Мерсенн

zer0mail 2664 / 2239 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	16.07.2014, 21:09	23
	Че их искать - число простое 1

@movielucky 0 / 0 / 0 Регистрация: 14.12.2013 Сообщений: 13
		1
	Найти делители "длинного" числа 15.07.2014, 11:03. Показов 4156. Ответов 24 Метки нет (Все метки) Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику? 0

zer0mail 2664 / 2239 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	16.07.2014, 19:24	21
	У Вы уверены, что число в задании не специально подобрано так, чтобы их можно было найти за разумное время? Добавлено через 50 минут Например, для 1009⁴⁰⁰⁰ (это более 12тыс знаков) мой подход легко найдет все делители Не исключаю также, что в задании нужно было найти все простые делители. 0

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	16.07.2014, 20:36	22
	Не по теме: ... тем временем movielucky открыл десятую пачку поп-корна ... по поводу алгоритма -- представьте число в виде простых делителей, как в школе делали. есть такая штука как решето эратосфена, еще щас нагуглил какие-то другие решета, например http://ru.wikipedia.org/wiki/%... 0%BD%D0%B0 возможно, оно также представимо в разреженном виде (пока не вникал), тогда можно будет контролировать рост памяти. все делители получаются перемножением простых (подождемс еще пару больших взрывов), но и так вы их количество даже тупо на все винчестеры мира не запишите. Более того, если бы винчестер представлял из себя атом, и эти атомы заполняли бы всю обозримую вселенную, и в каждом таком атоме помещалось бы по экзабайту, к примеру, вам понадобилось бы еще штук 2^10000 таких вселенных. люди, займитесь делом, чесслово. докажите лучше гипотезу Римана, вам еще и лям баксов за это дадут Добавлено через 14 минут Не по теме: кстати, если вам интересно, вот более интересный пример, и его уже действительно реально решить. найдите все делители числа Код 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 1

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	16.07.2014, 21:33	24
	ну логично, иначе б задача была нерешаемая чем докажете?))) 0

@volvo Супер-модератор 32835 / 21172 / 8148 Регистрация: 22.10.2011 Сообщений: 36,432 Записей в блоге: 8
	16.07.2014, 22:52	25
	Сообщение от NEbO чем докажете? 2⁵²¹-1, ключевое слово - Мерсенн 2