Интересные числа
На занятиях математического кружка Сережа узнал об интересных числах — это числа, которые имеют простые делители только 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 само является интересным.
Задача на Codeforces (контест gym/103385, задача 5, © Codeforces.com)