数値が素数かどうかを高速に判定する

これまで、ある数値 n が素数であるかどうかを調べる方法としては、基本的に割り算を使った線形探索を行っていました。つまり、n を大きくすれば、その素数判定に必要な操作回数は比例的に増えていく（ある定数倍）という仕組みでした。最悪のケース（たとえば 51 や 107 のように n 自体が素数のケース）を考えると、私たちのアルゴリズムは n/4 回程度の演算を行っていました。

これは、n を 10 倍にすると、素数判定のための操作回数も 10 倍になり、100 倍にすると 100 倍になるということを意味しています。つまり、アルゴリズムの実行時間は n に比例していたわけです。では、もっと速く判定する方法はないのでしょうか。よく見ると、まだ無駄なチェックが多いように思われます。

を用いる方法:

n に約数 d があるとします。

つまり、n は d で割り切ることができ、d と はどちらも整数です。そして、d と のどちらか一方は必ず 以下になります。素数判定をする際、1 と n 以外の割り切れる数が存在するかどうかを調べたいわけですから、d と の小さいほうを探せば十分です。つまり、そのどちらかは 以下になるため、ループを までで止めれば判定が可能です。

これは大きな改良です。これまでは n 回程度かかっていたものを、 回で済ませられるわけです。たとえば、あるアルゴリズムが 10 年（3650 日）かかっていた計算を、n ではなく の回数だけ演算するように最適化できるとしたら、2 か月（61 日）で完了するイメージです。

入力

The first line of the input contains a single integer n (1 ≤ n ≤ ).

出力

The program should print Yes in case n is prime and No otherwise.

Examples