Задача
Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.
Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.
Входные данные
Одно целое число $n$ $(1 ≤ n ≤ 2^{31}- 1)$.
Выходные данные
Вывести одно искомое число.
Тесты
| № | Ввод | Вывод |
| 1 | 1 | 1 |
| 2 | 10 | 8 |
| 3 | 100 | 96 |
| 4 | 363 | 256 |
| 5 | 2147483647 | 1610612736 |
Код программы с использованием цикла
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> using namespace std; int main() { long long int n, a = 2, b = 3; cin >> n; if (n <= 3) cout << n; else { while (a * 2 <= n) a *= 2; while (b * 2 <= n) b *= 2; cout << max(a, b); } return 0; } |
Код программы с использованием условных операторов
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <cmath> using namespace std; int main() { long long n; cin >> n; if (n <= 3) cout << n; else { long long pow, a = 2, b = 3; pow = log(n) / log(2); a = a << (pow - 1); b = b << (pow - 1); if (a <= n && b <= n) cout << max(a, b); else if (a > n) cout << b; else cout << a; } return 0; } |
Решение
Для решения данной задачи нам необходимо понять, что чем меньше простой множитель, тем больше таких множителей может содержать в себе искомое число, значит наше число состоит только из двоек или из двоек и одной тройки.
Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.
Условные операторы
Для начала с помощью логарифма найдем максимальный показатель степени двойки, содержащейся в заданном числе. Заметим, что нас интересует только целая часть полученного результата.
Далее возьмём двойку и тройку (как наименьшие возможные простые множители искомого числа) и сдвинем их битово влево на показатель степени двойки минус один, так как эта первая степень уже заложена в самих 2 и 3. Сдвигать нужно для того, чтоб повысить степень двойки в нашем числе, тем самым увеличив количество простых множителей.
Из двух полученных в результате наших действий чисел выберем наибольшее не превосходящее входные данные.
Цикл
Создадим две переменные равные двум и трём и будем увеличивать их вдвое до тех пор, пока полученное число не превосходит заданное.
Из полученных двух чисел выберем наибольшее, как этого требует условие задачи.
Ссылки
Решение задачи на Ideone циклом
Решение задачи на Ideone условными операторами