Необходимо найти число на промежутке от 1 до N, имеющее максимальное количество делителей. Если таки чисел несколько, вывести наименьшее. N может быть порядка 10^16, поэтому простой перебор не пойдет. Есть идеи?

задан 13 Авг '14 10:43

@DarkGenius, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(14 Авг '14 23:56) Deleted
10|600 символов нужно символов осталось
3

Должно иметь вид $%2^a\cdot 3^b\cdot 5^c\cdot...$%, причем в записи подряд простые, без пропусков (иначе будет не наименьшее), причем показатели $%a >= b>=c>=...$% - натуральные числа, либо $%0$%. Число делителей тогда равно $%(a+1)\cdot (b+1)\cdot (c+1)\cdot ...$% . Может стоит попробовать оценить это произведение показателей, но так, чтобы число было меньше $%10^{16}$%?

ссылка

отвечен 13 Авг '14 11:01

Да, именно такой способ выглядит наиболее подходящим для решения этой задачи. Перебор здесь так или иначе должен присутствовать, но вариантов немного из-за того, что неизвестные находятся в показателях степеней. Для проверки того, находится ли число в нужных пределах, можно прологарифмировать нервенство. Получится $%a\lg2+b\lg3+c\lg5+\cdots\le\lg N\le16$%. Все такие наборы легко перебираются.

(13 Авг '14 11:23) falcao

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

(13 Авг '14 12:02) DarkGenius

@DarkGenius: нам надо узнать, у какого числа больше всего делителей. Для этого надо сравнивать эти количества для разных чисел, пользуясь формулой. Если действовать другим способом, то есть проверять, у каких чисел списка есть делитель 2, делитель 3 и так далее, то операций будет слишком много, так как сами делители могут принимать очень большие значения. Без рзложения на множители, которое предложила использовать @Lyudmyla, тут обойтись вряд ли возможно.

(13 Авг '14 13:00) falcao

@falcao : Вы предлагаете считать число делителей для каждого числа от 1 до N?

(13 Авг '14 13:16) DarkGenius

@DarkGenius: как раз я предлагаю этого не делать, потому что количество операций будет очень большим. А в том способе, который предложила @Lyudmila, перебираемых вариантов совсем немного.

(13 Авг '14 13:22) falcao

@falcao: не совсем понимаю. Нужно перебрать все возможные сочетания степеней, запоминая число делителей для каждого сочетания?

(14 Авг '14 6:04) DarkGenius

@DarkGenius: нужно перебирать все наборы показателей степеней a,b,c,... с указанными в решении свойствами. Число делителей вычисляется по формуле. Потом среди всех значений определяем наибольшее. Сами значения можно не запоминать, а помнить только самое большое из них на момент просмотра.

(14 Авг '14 16:39) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×590
×122

задан
13 Авг '14 10:43

показан
1677 раз

обновлен
14 Авг '14 23:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru