075 - Magic For Balls(★3) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

得点: 3

問題文

整数 x が書かれたボールに対し、そのボールを叩くことによって以下の操作が行われます。

  • x が素数でない場合:叩かれたボールを消滅させ、整数 a が書かれたボールと整数 b が書かれたボールを追加する。a, bab=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 を出力してください。


Source Name

「競プロ典型90問」75日目