3707: 学习除法(第一轮01)

鸡尾酒的学生丹丹学不会除法，有一天他遇到了这样的一个问题：给定一个整数 n，你可以任选一个 n  的因子 x，然后将 n  除以 x 。你可以进行任意次这样的 操作，直到 n  是一个质数为止。请问至少几次操作可以让 n  变成一个质数。

由于丹丹不会除法，更不知道因子是什么意思，所以他将这个问题交给你了，请 你帮他解决这个问题。

例如：原数字 n = 8，选择 8  的因子 2，将  8  除以  2，此时 n = 4。然后再选 择 4  的因子  2，将  4   除以  2，得到 n = 2。此时 n  是一个质数。（这样的操作 方案不一定是最优的，因为本题在求最少的操作次数）

输入仅一行一个整数 n。

输出一行一个答案。

8

1