Тимур считает, что все задачи по программированию можно решить перебором. Казалось бы, чего сложного, например, перебрать все возможные пары различных натуральных чисел $$$(a, b)$$$ не более некоторого $$$n$$$ и вывести максимальный НОД из полученных? Не правда ли?
Одно целое число $$$n$$$, где $$$2 \le n \le 10^{18}$$$.
Одно целое число — максимальный НОД чисел $$$a$$$ и $$$b$$$ при всех возможных, где $$$1 \le a \lt b \le n$$$.
2
1
5
2
Во втором примере все возможны НОДы равны: НОД(1, 2) = 1, НОД(1, 3) = 1, НОД(1, 4) = 1, НОД(1, 5) = 1, НОД(2, 3) = 1, НОД(2, 4) = 2, НОД(2, 5) = 1, НОД(3, 4) = 1, НОД(3, 5) = 1, НОД(4, 5) = 1. Максимальным из полученных чисел является 2.
