← 返回题目列表

Codeforces · 1076/B

B. 除数减法

中文机器翻译题面 查看原题

给你一个整数$$$n$$$。对其应用以下算法:

1. 如果$$$n = 0$$$,则结束算法;
2. 求$$$n$$$的最小素因数$$$d$$$;
3. 从 $$$n$$$ 中减去 $$$d$$$ 并转到步骤 $$$1$$$。

确定算法将进行的减法次数。

输入

唯一一行包含单个整数 $$$n$$$ ($$$2 \le n \le 10^{10}$$$)。

输出

打印一个整数 — 算法将进行的减法次数。

示例

输入 #1

5

输出 #1

1

输入 #2

4

输出 #2

2

注意

在第一个示例中 $$$5$$$ 是最小的素因数,因此它会立即被减去以得到 $$$0$$$。

在第二个示例中,$$$2$$$ 是两个步骤中的最小素因数。