Find a number
between 1 and n (inclusive) that has the maximum number of prime factors
in its factorization. If there are multiple such numbers, print the largest
one.
For example, for n
= 7 the answer is 6, as it is the largest number whose prime factorization
includes two factors: 2 and 3.
Input. One integer n
(1 ≤ n ≤ 231 − 1).
Output. Print the desired
number.
|
Sample input |
Sample output |
|
7 |
6 |
factorization
Algorithm
analysis
To ensure that a number not exceeding n has the
maximum number of divisors, it should be represented as the product of the
smallest possible prime numbers.
For example, consider numbers of the form 2k. Find the largest k such
that 2k ≤ n. The
number of divisors of 2k is given
by d(2k) = k + 1.
Next, examine the number 2k-1 * 3. The
number of its divisors is d(2k-1 * 3) = k * 2, which
is greater than k + 1.
Thus:
·
If 2k-1 * 3
≤ n, the
desired number is 2k-1 * 3;
·
Otherwise, the answer is 2k.
Finally, consider the special case when n = 1. For this value, the answer is 1.
Example
Let n = 100. The
largest power of 2 not exceeding 100 is 26 = 64. The number 64 has d(64) = 6 + 1 = 7 divisors.
Now, consider the number 25
* 3 = 96. The number of its divisors is:
d(96) = (5 + 1) * (1 + 1) = 6 * 2 = 12
Since 96 does not exceed 100, it will be the desired
number for n = 100.
Algorithm implementation
Read the input value of n.
cin >> n;
Find the largest p = 2k such that p ≤ n.
p = 1;
while (p * 2 <= n)
p = p * 2;
Next, compute p1 = 2k-1 * 3 = p / 2 * 3.
p1 = p / 2
* 3;
Determine the result res. If n = 1, the
result will be 1.
if (p1 <= n) res = p1; else res = p;
if (n == 1) res = 1;
Print the answer.
cout << res << endl;
Python implementation
Read the input value of n.
n = int(input())
Find the largest p = 2k such that p ≤ n.
p = 1
while p * 2 <= n:
p *= 2
Next, compute p1 = 2k-1 * 3 = p / 2 * 3.
p1 = (p // 2) * 3
Determine the result res. If n = 1, the
result will be 1.
if p1 <= n: res = p1
else: res = p
if n == 1: res = 1
Print the answer.
print(res)