Найдите такое число от 1 до n включительно, для
которого в разложении на простые множители количество множителей максимально.
Если таких чисел несколько, выведите наибольшее из них.
Например, для n = 7 ответом
будет число 6, так как оно является наибольшим
числом, разложение которого на простые множители включает два множителя: 2 и 3.
Вход. Одно
целое число n (1 ≤ n ≤ 231 − 1).
Выход. Выведите
одно искомое число.
|
Пример входа |
Пример выхода |
|
7 |
6 |
разложение на множители
Для того чтобы число, не превышающее n, имело максимальное количество делителей, его следует
представить в виде произведения как можно меньших простых чисел.
Например, попробуем искать его в виде 2k. Найдем наибольшее
k, для
которого 2k ≤ n.
Количество делителей числа 2k равно d(2k) = k + 1.
Затем рассмотрим число 2k-1 * 3. Количество
его делителей равно d(2k-1 * 3) = k * 2, что
больше, чем k + 1.
Таким образом:
·
Если 2k-1 * 3
≤ n, то
искомым числом будет 2k-1 * 3;
·
В противном случае ответом будет 2k.
Отдельно рассмотрим случай n = 1. Для этого значения ответом будет 1.
Пример
Пусть n = 100.
Наибольшей степенью двойки, не большей 100, будет 26 = 64. Число 64
имеет d(64) = 6 + 1 = 7
делителей.
Теперь рассмотрим число 25 * 3 = 96. Количество
его делителей равно:
d(96) = (5 + 1) * (1 + 1) = 6 * 2 = 12
Так как число 96 не превышает 100, оно будет искомым
для n = 100.
Реализация алгоритма
Читаем
входное число n.
cin >> n;
Ищем наибольшее p = 2k, такое что
p ≤ n.
p = 1;
while (p * 2 <= n)
p = p * 2;
Далее вычислим p1 = 2k-1 * 3 = p / 2 * 3.
p1 = p / 2
* 3;
Находим ответ res. Если n = 1, то
ответом будет 1.
if (p1 <= n) res = p1; else res = p;
if (n == 1) res = 1;
Выводим ответ.
cout << res << endl;
Python реализация
Читаем
входное число n.
n = int(input())
Ищем наибольшее p = 2k, такое
что p ≤ n.
p = 1
while p * 2 <= n:
p *= 2
Далее вычислим p1 = 2k-1 * 3 = p / 2 * 3.
p1 = (p // 2) * 3
Находим ответ res. Если n = 1, то
ответом будет 1.
if p1 <= n: res = p1
else: res = p
if n == 1: res = 1
Выводим ответ.
print(res)