Быстрое нахождение максимального делителя числа

@flyce32 · Регистрация: 24.05.2015

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

Всем привет! Столкнулся с такой проблемой, у меня дано число n $https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq$ 10 ^ 18. Для использования моего алгоритма, мне нужно быстро найти максимальный делитель числа, но быстрее чем за корень (то есть 10^9, что примерно 10^9 / 10^7 секунд - 100 секунд) сделать не могу. Если есть алгоритмы быстрее, расскажите про них пожалуйста.

@Голубь Вася · 04.12.2015, 23:17

Что такое максимальный делитель числа?
Самое большое число, на которое данное делиться без остатка?
Тогда для любого n максимальный делитель будет равен n, так как n / n = 1.

@IrineK · 05.12.2015, 01:11

Можно искать наименьший простой делитель.
С помощью какого-нибудь решета.

@flyce32 · 14.12.2015, 18:43 **[ТС]**

Это то понятно, но решето на число, например $https://www.cyberforum.ru/cgi-bin/latex.cgi?{(1e9+7)}^{2}$ это не сработает, потому что наименьший делитель простой - 1e9+7, а решето до него не сделать.

@Dimension · 14.12.2015, 19:09

а есть ссылка на задачу?

@IrineK · 14.12.2015, 19:41

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

это не сработает

Так запускайте параллельные процессы - кто первый.

zer0mail · 14.12.2015, 19:45

Ищешь минимальный простой делитель, потом делишь исходное на это простое и уже для него ищешь простой делитель. И т. д. Если делителей много, то перебирать гораздо меньше, чем 10^9. Все можно сделать в одном цикле.

@_Ivana · 15.12.2015, 01:16

А если число простое, то точно так же бежать до корня

Присоединяюсь к вопросу о полной задаче - может там это и не надо.

zer0mail · 15.12.2015, 10:13

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

А если число простое, то точно так же бежать до корня

Да, но вряд ли эта задача на уровне "взломать RSA"

Во всяком случае, для простого числа мой вариант не хуже исходного, а не для простых - лучше, порой не несколько порядков

@flyce32 · 15.12.2015, 20:16 **[ТС]**

Я лучше сделаю решето до ~ $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ , пройдусь, проверю, если не найду его, то следует, что делители больше, чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ , и запускаю метод Ферма, а потом просто удаляю из массива множителей наименьший, и считаю произведение. Только теперь задача, написать метод Фермы, единственный код, где я его нашёл это на emaxx, но попробую написать сам.

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@flyce32 0 / 0 / 1 Регистрация: 24.05.2015 Сообщений: 128

	Быстрое нахождение максимального делителя числа 04.12.2015, 20:40. Показов 7062. Ответов 9 Метки c++, быстродействие, Делители, максимального, Нахождение (Все метки) Всем привет! Столкнулся с такой проблемой, у меня дано число n $https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq$ 10 ^ 18. Для использования моего алгоритма, мне нужно быстро найти максимальный делитель числа, но быстрее чем за корень (то есть 10^9, что примерно 10^9 / 10^7 секунд - 100 секунд) сделать не могу. Если есть алгоритмы быстрее, расскажите про них пожалуйста. 0

@Голубь Вася 5 / 5 / 3 Регистрация: 02.08.2015 Сообщений: 62
	04.12.2015, 23:17
	Что такое максимальный делитель числа? Самое большое число, на которое данное делиться без остатка? Тогда для любого n максимальный делитель будет равен n, так как n / n = 1. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	05.12.2015, 01:11
	Можно искать наименьший простой делитель. С помощью какого-нибудь решета. 0

@flyce32 0 / 0 / 1 Регистрация: 24.05.2015 Сообщений: 128
	14.12.2015, 18:43 [ТС]
	Это то понятно, но решето на число, например $https://www.cyberforum.ru/cgi-bin/latex.cgi?{(1e9+7)}^{2}$ это не сработает, потому что наименьший делитель простой - 1e9+7, а решето до него не сделать. 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	14.12.2015, 19:09
	а есть ссылка на задачу? 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	14.12.2015, 19:45
	Ищешь минимальный простой делитель, потом делишь исходное на это простое и уже для него ищешь простой делитель. И т. д. Если делителей много, то перебирать гораздо меньше, чем 10^9. Все можно сделать в одном цикле. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	15.12.2015, 01:16
	А если число простое, то точно так же бежать до корня Присоединяюсь к вопросу о полной задаче - может там это и не надо. 0

@flyce32 0 / 0 / 1 Регистрация: 24.05.2015 Сообщений: 128
	15.12.2015, 20:16 [ТС]
	Я лучше сделаю решето до ~ $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ , пройдусь, проверю, если не найду его, то следует, что делители больше, чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ , и запускаю метод Ферма, а потом просто удаляю из массива множителей наименьший, и считаю произведение. Только теперь задача, написать метод Фермы, единственный код, где я его нашёл это на emaxx, но попробую написать сам. 0

Опции темы