← 返回题目列表

AtCoder · typical90_bw

075. 球魔法(★3)

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

得点: 3 点

問題文

整数 x 的球,通过敲击该球敲将执行以下操作。 如果

  • x 不是质数:消灭被敲击的球,并添加写有整数 a 的球和写有整数 b 的球。a, b 是 您也可以写 ab=x 和 a \geq 2, b \geq 2 可以从满足条件的整数中自由选择。
  • x 如果是质数:什么也不会发生。

另外,魔法 1 次使用,可以同时敲击当前所有的球。另一方面,除了使用魔法之外,不能以其他方式敲击球。

现在,整数 给出了 N 上写有数字的球有 1 个。你想通过使用几次魔法,将所有球上写的数字变成质数。最少需要进行多少次操作?

制約

  • 2 \leq N \leq 10^{12}
  • N 是一个整数

入力

输入是按以下格式从标准输入给出的。

N

出力

请打印答案。 到达


入力例 1

42

出力例 1

2

简介, 准备42 上写有数字的球。使用魔法敲击这个球时,例如会进行如下操作。

  • 42 上写有数字的球将消失,7 上写有数字的球和 6 的球。

现在,各自有 6, 7 已写入 2 个球。使用魔法敲击这些球时,将会进行如下操作。

  • 7 的球也不会发生任何事情。 有
  • 6 上写有数字的球将消失,2 上写有数字的球和 3 的球。

现在,各自有 2, 3, 7 已写入 3 个球。由于它们都是质数, 可以通过2 次魔法来达到条件。2 无法在少于次数的情况下达成条件。


入力例 2

48

出力例 2

3

例如,按照下图的步骤进行操作,3 就可以用次数的魔法将所有球上写的数字变为素数。


入力例 3

54

出力例 3

2

入力例 4

53

出力例 4

0

如果一开始就是素数的话,即使不使用魔法也满足条件,0 。 须满足