数値が素数かどうかを判定する — もう少し高速に
ある大規模な企業のプロダクション環境で、素数かどうかを判定するプログラムが使用されているとしましょう。しかし、企業の急速な拡大に伴いユーザー数が増えると、これに比例して素数判定コードへのリクエストも増加します。そこで、プログラムをもう少し高速化して、新規ユーザーの増加に対応できるようにしてほしい、という依頼がやってきたと想定してください。
前回の実装では、おそらく次のいずれかを用いていたのではないでしょうか。
- 2から
nまでの数字をすべてループして、約数の個数を数える。
- 2から
nまでループし、約数を見つけた時点で処理を打ち切る。
今回は、これらの方法をいくつかの小さな工夫で最適化してみます。
Optimization 1:
2から
nまでの全数字を調べる代わりに、まずnが2で割り切れるかを確認し、割り切れなければその後は奇数だけをチェックします。2で割り切れないなら、その先の4や6などの偶数を調べる必要はなくなるからです。Optimization 2:
2から
nまでループするのではなく、n/2までループするようにします。最小の約数は2なので、n/2より大きい約数はありえないからです。これらの最適化を組み合わせると、
n/2までの奇数だけを確認すればよくなり、チェック対象は約n/4個なので単純な線形探索よりも4倍程度効率的になります。ただし、この最適化を行っても、依然としてアルゴリズムの計算量は
nに比例する線形探索のままです。nが増えれば処理量も増えるという点は変わりません。nの増加に伴って計算量が比例して増えないようにする、より抜本的な高速化手法については、後のステップで取り上げる予定です。入力
最初の行に整数
n (1 ≤ n ≤ ) が与えられます。出力
n が素数なら "Yes"、そうでなければ "No" を出力してください。例
入力 | 出力 |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB