408942: GYM103385 5 Интересные числа

На занятиях математического кружка Сережа узнал об интересных числах — это числа, которые имеют простые делители только 2, 3 и 5. Теперь он хочет узнать наибольшее интересное число, не превосходящее числа $$$n$$$.

Программа получает на вход целое число $$$n$$$ ($$$2 \leq n \leq 10^{17}$$$).

Обратите внимание, что значение $$$n$$$ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Программа должна вывести одно целое число — максимальное интересное число, не превосходящее $$$n$$$.

Решения, правильно работающие при $$$n \leq 10^4,$$$ будут оцениваться в 30 баллов.

Решения, правильно работающие при $$$n \leq 10^8,$$$ будут оцениваться в 50 баллов.

7

6

100

100

Первые интересные числа — это 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30,....

Поэтому в первом примере максимальное интересное число, не превосходящее 7 — это 6.

Во втором примере число 100 разлагается на множители, как $$$100 = 2^2 \cdot 5^2$$$, поэтому число 100 само является интересным.