Задано целое число \(n\). К нему применяется следующий алгоритм:
- если \(n = 0\), то завершить алгоритм;
- найти наименьший простой делитель \(d\) числа \(n\);
- вычесть \(d\) из \(n\) и перейти к шагу \(1\).
Определите количество вычитаний, которые совершит алгоритм.
Выходные данные
Выведите единственное целое число — количество вычитаний, которые совершит алгоритм.
Примечание
В первом примере \(5\) — это наименьший простой делитель, поэтому он сразу вычтется, приведя число к \(0\).
Во втором примере \(2\) — наименьший простой делитель на обоих шагах.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
|
1
|
|
2
|
4
|
2
|