404179: GYM101445 C Игра “Числа”

C. Игра “Числа”ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Суперкомпьютер по имени Lesli очень любит играть с программистами в различные интеллектуальные игры. Сегодня планируется играть в игру “Числа” и Lesli очень хочет победить. Но никто из программистов не соглашается запрограммировать Lesli для игры в “Числа”, чтобы избавиться от сильного конкурента. А ты сможешь помочь Lesli?

В игру “Числа” играют двое, ходят по очереди. Игра начинается с некоторого целого числа n, 1 ≤ n ≤ 10⁹. Далее каждый игрок в свой ход должен выбрать число вида p^k такое, что p – простое число, k – целое положительное число, n делится нацело на p^k, после чего разделить n на p^k. Более того, запрещено использовать простое число p, которое использовал соперник на предыдущем ходу. Проигрывает тот, кто не может сделать ход.

Входные данные

В единственной строке записано целое число 1 ≤ n ≤ 10⁹.

Выходные данные

В единственной строке выведите “YES” (без кавычек), если первый игрок побеждает в игре со стартовым числом n при оптимальной стратегии обоих игроков. В противном случае выведите “NO” (без кавычек).

ПримерыВходные данные

1

Выходные данные

NO

Входные данные

8

Выходные данные

YES