数値が素数かどうかを高速に判定する
これまで、ある数値
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 日）で完了するイメージです。ある数が素数かどうかを判定する、より進んだアルゴリズムはある？
はい！詳細は <a href="https://cp-algorithms.com/algebra/primality_tests.html">Algorithms for Competitive Programming</a> で読むことができます。
n の増加に応じた演算回数が ではなく、対数的に増えるアルゴリズムも存在します。入力
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
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB