【Java】素数判定①（試し割り法）

　数学的な問題を解いていると非常によくテーマとして挙げられる素数。数学者体質の人はよくハマってしまうほど興味深い性質もあるらしいのだが、コードとしても似たようなものが使えるので、ちょこっと取り上げてみることにした。その定義は「正の約数が 1 と自分自身のみであるもののことで、ただし 1 は（現在では）含めない。正の約数の個数が 2 である自然数と言い換えることもできる。(～以下略～)」(Wikipedia)となっているが、簡単に言えば「何らかの数の倍数でない」とか「素数の反対は合成数である」とだけ覚えていれば十分かも知れない。あと「２の倍数（偶数）は２以外は素数でないことから、素数のほとんどは奇数である」と覚えておくとコードを書くとき、その計算量を半分にできることが多い。

●素数かどうかを判定する(試し割り法)

/**<h1>素数かどうかを判定する（試し割り法）</h1>
 * <p>偶数以外で、3 から √n までに対して順番に割り切れるものが存在しないことをチェックする。</p>
 * @param n ： 調べる値 (n >= 0) [n を含む]
 * @return<b>boolean</b> ： true = 素数 (1 は例外で false)
 */
public static final boolean isPrime(final long n) {
    if (n < 2) {
        return false;
    }
    if (n % 2 == 0) {
        return (n == 2);
    }

    for (long i = 3; i * i <= n; i += 2) {    //奇数のみ [O(√n[/2])で可]
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}


//メインでは...
long n = 46116646144580591L;
System.out.println(isPrime(n));

true

　引数の型が long になっているが、int の範囲で十分なら型を変えても良いだろう。実際に int 範囲の場合、以下に示す高速化のポイントは、あまり効果は見えない（非常に大きな値のときよくわかる）。

　今回のコードはお手本そのままという感じなので、目新しいものはないが、このコードを取り上げたのは「ちょっとした高速化のポイント」がいくつか含まれているからだ。そのポイントは今後取り上げようと思っている「素数表（エラトステネスの篩）」や「素因数分解」「約数」など数学的なコードに頻繁に出てくる。実際には非常に細かいテクニックなのだが、使うと使わないでは効率が結構変わるものなので、改めて考えてみよう。

　まず一番目立つのはループ部分の「i * i <= n」となっている所だろうか。これは言ってみれば「i <= √n」と同じ意味だ。だから、以下のように書くこともできる

●ループ部分の「i * i <= n」の別表記１

～(略)～
for (long i = 3; i <= Math.sqrt(n); i += 2) {
    //処理
}
～(略)～

●ループ部分の「i * i <= n」の別表記２

～(略)～
for (long i = 3; i <= n / i; i += 2) {
    //処理
}
～(略)～

　実際に色々なサンプルコードを見てみると、このような表記も非常に多いのだが、見つけたら試しに「i * i <= n」のような掛け算の表記にしてみよう。特に非常に大きな計算やサーバーサイドのスクリプト、ゲームなどのメインスレッドループなどでは実行速度が大きく改善されることがある。というのは平方根(sqrt)や sin, cos, log などの算術関数、除算（割り算）などはコンピュータにとっては思いのほか負荷が高く、大量に計算すると重くなるからだ（ただの１回のようなものならそれほど問題ない）。もしどうしても使いたいときは、ループ外で１回計算し、変数にその答えを入れて利用するとか、「n / 2」を「n >> 1（ビットシフト）」(平方数で割るとき)などにするという手もある。まぁ、実際のところやり過ぎるとコードがわかりづらくなるのでほどほどにしておいた方が良いかもしれないが(笑)、ピンポイントで高速化できる箇所を修正するだけでもかなり効果はある。

　あとは冒頭に書いたように素数判定に偶数を一気に除外している所だろうか。コードの「if (n % 2 == 0)」とループの「i += 2」となっている箇所だ。こうすると一気に候補を半分にできるわけで、意外と見落としがちだったりする。できるだけループ回数を減らすのは実行速度の向上に繋がる。ループの √n 化も同じことで、「n が約数 d を持ったとすると、n/d も n の約数で、n = n * n/d なので、min(d, n/d) <= √n となる（d または n/d の小さい方の数は必ず √n 以下となる）」。O(√n )というのは非常に高速なので、使える箇所には積極的に使おう（数学的な関数では意外と使えることが多い）。

　他にも素数判定法には「AKS素数判定法」とか「フェルマーテスト」（確率的＝正しいとは限らない答えが出ることがある）「ミラー–ラビン素数判定法」（確率的）などもあるようだが、CodeIQなどに出題されるプログラミング問題では「エラトステネスの篩(ふるい)」のような篩法で十分だろう。実際に私は中級(★★)～上級(★★★★)問題をすべて解いているが、素数関連の問題でエラトステネスの篩を使ってタイムアウトしたことは一度もない(←せっかくなので作った関数などを実際の問題によく試させて貰っている(笑))。興味があるなら、より高度な素数判定法の参考も以下に載せておこう。

（参考）
・素数判定法
・AKS素数判定法のアルゴリズム


（関連記事）
【Java】素数判定②（エラトステネスの篩(ふるい)）
【Java】素数判定③（サンダラムの篩(ふるい)）
【Java】素数判定④（アトキンの篩(ふるい)）

■参考になる書籍