Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
flyce32
0 / 0 / 1
Регистрация: 24.05.2015
Сообщений: 128
1

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

04.12.2015, 20:40. Просмотров 1027. Ответов 9

Всем привет! Столкнулся с такой проблемой, у меня дано число n http://www.cyberforum.ru/cgi-bin/latex.cgi?\leq 10 ^ 18. Для использования моего алгоритма, мне нужно быстро найти максимальный делитель числа, но быстрее чем за корень (то есть 10^9, что примерно 10^9 / 10^7 секунд - 100 секунд) сделать не могу. Если есть алгоритмы быстрее, расскажите про них пожалуйста.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.12.2015, 20:40
Ответы с готовыми решениями:

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

Нахождение наименьшего нечетного натурального делителя k (k≠1) любого заданного натурального числа n
Помогите с этой задачой: Подпрограммы Составить функцию для нахождения...

нахождение максимального числа dev C++
дана строка char с произвольными данными, например "21,5 10,3 12 74"...

Нахождение максимального и минимального числа
Здравствуйте. Помогите найти максимальное и минимальное число #include...

Массив. Нахождение максимального числа, повторяющегося более 1 раза.
Все привет!) Есть программа. Возможно ли здесь создать определенный массив, а...

9
Голубь Вася
5 / 5 / 3
Регистрация: 02.08.2015
Сообщений: 62
04.12.2015, 23:17 2
Что такое максимальный делитель числа?
Самое большое число, на которое данное делиться без остатка?
Тогда для любого n максимальный делитель будет равен n, так как n / n = 1.
0
IrineK
Заблокирован
05.12.2015, 01:11 3
Можно искать наименьший простой делитель.
С помощью какого-нибудь решета.
0
flyce32
0 / 0 / 1
Регистрация: 24.05.2015
Сообщений: 128
14.12.2015, 18:43  [ТС] 4
Это то понятно, но решето на число, например http://www.cyberforum.ru/cgi-bin/latex.cgi?{(1e9+7)}^{2} это не сработает, потому что наименьший делитель простой - 1e9+7, а решето до него не сделать.
0
Dimension
Dimension
574 / 444 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
14.12.2015, 19:09 5
а есть ссылка на задачу?
0
IrineK
Заблокирован
14.12.2015, 19:41 6
Цитата Сообщение от flyce32 Посмотреть сообщение
это не сработает
Так запускайте параллельные процессы - кто первый.
0
zer0mail
2454 / 2090 / 217
Регистрация: 03.07.2012
Сообщений: 7,581
Записей в блоге: 1
14.12.2015, 19:45 7
Ищешь минимальный простой делитель, потом делишь исходное на это простое и уже для него ищешь простой делитель. И т. д. Если делителей много, то перебирать гораздо меньше, чем 10^9. Все можно сделать в одном цикле.
0
_Ivana
3236 / 1867 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
15.12.2015, 01:16 8
А если число простое, то точно так же бежать до корня Присоединяюсь к вопросу о полной задаче - может там это и не надо.
0
zer0mail
2454 / 2090 / 217
Регистрация: 03.07.2012
Сообщений: 7,581
Записей в блоге: 1
15.12.2015, 10:13 9
Цитата Сообщение от _Ivana Посмотреть сообщение
А если число простое, то точно так же бежать до корня
Да, но вряд ли эта задача на уровне "взломать RSA" Во всяком случае, для простого числа мой вариант не хуже исходного, а не для простых - лучше, порой не несколько порядков
0
flyce32
0 / 0 / 1
Регистрация: 24.05.2015
Сообщений: 128
15.12.2015, 20:16  [ТС] 10
Я лучше сделаю решето до ~ http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}, пройдусь, проверю, если не найду его, то следует, что делители больше, чем http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}, и запускаю метод Ферма, а потом просто удаляю из массива множителей наименьший, и считаю произведение. Только теперь задача, написать метод Фермы, единственный код, где я его нашёл это на emaxx, но попробую написать сам.
0
15.12.2015, 20:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2015, 20:16

Быстрое вычисление наибольшего общего делителя для unsigned long long int
Даны два числа типа unsigned long long int, в них могут оказаться любые...

Нахождение делителя
Всем привет. Имеется простое число 2^32 +1. У числа имеется 2 делителя, которые...

Нахождение наибольшего общего делителя
Borland C++ Найти наибольший общий делитель двух натуральных чисел a и b.


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

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

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