075 - Magic For Balls(★3)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
得点: 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 を出力してください。