Множники#8362

Множники (Розбір)

Для того, щоб число, яке не перевищує $n$ , мало максимальну кількість дільників, його слід уявити у вигляді добутку як можна менших простих чисел.

Наприклад, спробуємо шукати його у вигляді $2^{k}$ 2^k. Знайдемо найбільше $k$ , для якого $2^{k} \leq n$ 2^k \le n. Кількість дільників числа $2^{k}$ 2^k дорівнює $d (2^{k}) = k + 1$ d(2^k) = k + 1.

Потім розглянемо число $2^{k - 1} \cdot 3$ 2^{k - 1} \cdot 3. Кількість його дільників дорівнює $d (2^{k - 1} \cdot 3) = k \cdot 2$ d(2^{k - 1} \cdot 3) = k \cdot 2, що більше, ніж $k + 1$ k + 1.

Таким чином:

Якщо $2^{k - 1} \cdot 3 \leq n$ 2^{k - 1} \cdot 3 \le n, то шуканим числом буде $2^{k - 1} \cdot 3$ 2^{k - 1} \cdot 3;
В протилежному випадку відповіддю буде $2^{k}$ 2^k.

Окремо розглянемо випадок $n = 1$ n = 1. Для цього значення відповіддю буде $1$ .

Приклад

Нехай $n = 100$ n = 100. Найбільшою степеню двійки, не більшою $100$ , буде $2^{6} = 64$ 2^6 = 64. Число $64$ має $d (64) = 6 + 1 = 7$ d(64) = 6 + 1 = 7 дільників.

Тепер розглянемо число $2^{5} \cdot 3 = 96$ 2^5 \cdot 3 = 96. Кількість його дільників дорівнює:

d (96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

d(96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

Оскільки число $96$ не перевищує $100$ , воно буде шуканим для $n = 100$ n = 100.

Реалізація алгоритму

Читаємо вхідне число $n$ .

scanf("%d",&n);

Шукаємо найбільше $p = 2^{k}$ p = 2^k, таке що $p \leq n$ p \le n.

p = 1;
while (p * 2 <= n)
  p = p * 2;

Далі обчислимо $p 1 = 2^{k - 1} \cdot 3 = p /2 \cdot 3$ p1 = 2^{k - 1} \cdot 3 = p / 2 \cdot 3.

p1 = p / 2 * 3;

Знаходимо відповідь $r es$ . Якщо $n = 1$ n = 1, то відповіддю буде $1$ .

if (p1 <= n) res = p1; else res = p;
if (n == 1) res = 1;

Виводимо відповідь.

printf("%d\n",res);

Python реалізація

Читаємо вхідне число $n$ .

n = int(input())

Шукаємо найбільше $p = 2^{k}$ p = 2^k, таке що $p \leq n$ p \le n.

p = 1
while p * 2 <= n:
  p *= 2

Далі обчислимо $p 1 = 2^{k - 1} \cdot 3 = p /2 \cdot 3$ p1 = 2^{k - 1} \cdot 3 = p / 2 \cdot 3.

p1 = (p // 2) * 3

Знаходимо відповідь $r es$ . Якщо $n = 1$ n = 1, то відповіддю буде $1$ .

if p1 <= n: res = p1
else: res = p
if n == 1: res = 1

Виводимо відповідь.

print(res)