Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача A. Разложение на четно-простые
| Имя входного файла: | a.in |
| Имя выходного файла: | a.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Натуральное четное число будем называть четно-простым, если оно не может быть представлено в виде произведения двух и более четных натуральных чисел.
Напишите программу, которая по введенному натуральному четному числу будет вычислять, сколькими способами его можно представить в виде произведения четно-простых чисел (при этом представления, отличающиеся только порядком множителей, нужно считать одинаковыми).
Примеры. Число 10 является четно-простым, поэтому может быть представлено в виде произведения четно-простых единственным способом (как произведение из одного множителя 10). Число 4 не является четно-простым, однако может быть представлено как произведение четно-простых единственным способом: 2*2. Число 60 может быть представлено как произведение четно-простых следующими способами: 6*10, 30*2 и других таких представлений нет.
Формат входных данных
Вводится одно натуральное четное число N (2≤N≤109).
Формат выходных данных
Выведите одно число - количество вариантов представления введенного числа N в виде произведения четно-простых чисел.
Примеры
| a.in | a.out |
10 |
1 |
4 |
1 |
60 |
2 |