プログラミング初心者のための簡単アルゴリズム入門【素数を数えて落ち着くんだ】

f:id:paiza:20180927171854j:plain
Photo by formulanone
青木です。paizaラーニング担当のエンジニアです。

人間、どうしても素数を数えて落ち着きたいときってあると思います。

順に数えてくと、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31……自分で数えるのは限界がありますよね。

そんなときはプログラムに数えてもらいましょう。

今回は、素数を数えるためのいろいろなアルゴリズムや高速化について書きます。（言語はJavaを使います）

プログラミング初心者の方、アルゴリズムについて勉強したい方、素数が大好きな皆さんの参考になればと思います。

素数とは孤独な数字

素数とは、1と自分自身の数以外の自然数では割り切れない孤独な数字です。(ってプッチ神父が言ってました)

たとえば、7は1と7以外の自然数では割り切れないので素数です。8は2や4で割り切れるので素数ではありません。

※1は諸説ありますが、今回はひとまず素数ではないものとします。

素数を判定して落ち着くんだ

Picture by ITエンジニアを目指す女子高生たちの学園ライフ4コマ漫画『ぱいじょ！』
まずは、「素数判定」プログラムを作って素数を理解しましょう。

皆さんは、素数を数えて落ち着きたいときはどうやって数えていますか？

「2は素数、3は素数、4は2で割り切れるから素数ではない、5は素数、6は2でも3でも割り切れるから素数ではない……」と数字ひとつひとつに対して、「素数か否か」を確認しながら数えますよね？（ある程度までは暗記していたとしても、それを越えたら確認が必要になってきますよね）

そんなときは「ある自然数が素数かどうか」を判定してくれる素数判定プログラムを作っておくと、楽になります。

素数判定プログラムを作るには、まず以下のようなisPrimeメソッドを作っておきましょう。

// 素数判定
// 入力: n
// 出力: 素数かどうか
public class Main {
    static boolean isPrime(int n) {
        ...
    }
    public static void main(String[] args) {
        int n = 7;
        if (isPrime(n)) {
            System.out.println(n + "は素数");
        }
        else {
            System.out.println(n + "は素数でない");
        }
    }
}

素数判定：100以下の場合

大きな値でも対応できる素数判定を作るのは大変ですから、徐々に改善しつつやっていきましょう。

まずは、10以下の自然数nの素数判定プログラムを作成します。

10以下の素数はほんの少しですから、そのまま条件を書き出すだけでいけちゃいますね。こんな感じです。

↑このままいじれますので、nの値を変更してテストしてみてください。

ちゃんと3や7が素数と判定されて、1や8は素数でないと判定されるので、大丈夫そうですね。

次に、100以下の自然数nの素数判定プログラムです。

100以下もまあそんなに多くはないですから、そのまま条件を書いてみました。

10以下のときと同じように、nの値をいろいろ変えて試してみてくださいね。

ブログパーツとして使っているオンライン実行環境サービス「paiza.IO (パイザ・アイオー)」はこちら

素数判定：1000以下の場合

1,000以下になるとどうでしょうか、さすがに全部書き出すのは面倒すぎますね。

「素数は1と自分自身の数以外の自然数では割り切れない孤独な数字」なんですから、2以上であること、もしくはn-1以下の整数で割り切れないことを確認すれば判定できそうですね。

n = 1の場合の処理を忘れずに入れておきます

nの値を1,000以下の大きな数値にして試してみましょう。991は素数で、989は素数ではないようです。

素数判定：一億以下の場合

前述のコードで、とりあえず大きな数値でも判定できるようになったっぽいですよね。

nを大きくしながら実行していくと、ひとまず9,999,991は素数、9,999,992は素数ではないと判定できます。

ただ、これぐらいの大きさの数になってくると、paiza.IOでは判定に0.22秒程度かかってしまいます。さらに大きくして、99,999,989が素数であると判定するには、0.50秒程度かかってしまいます。ちょっと長いですね。

というわけでここからは、大きな数値でも素早く判定できるような高速化を考えていきます。

プログラムを高速化するにはどうすべきか？いろいろな手法がありますが、単純にループの回数が減れば、そのぶん処理も早く終えられます。

そもそも偶数（＝2の倍数）はすべて素数じゃないですから、偶数の場合はループでチェックするのをやめてみましょう。

これだけでも、ループ回数がおよそ半分になります。

このコードを実行してみると、さきほど0.50秒程度かかっていた数値での実行時間が0.38秒となりました。およそ0.12秒の高速化ですね。

偶数の次は、3の倍数も外してみましょうか。

ちょっとややこしいですが、こんな感じです。

2の倍数、もしくは3の倍数が出現するパターンは6ごとに周期的に繰り返されますから、周期の中で2の倍数でも3の倍数でもない数についてだけ、素数チェックをするようにしました。

これによって実行時間が0.30秒となり、偶数だけ外していたときよりも、さらに0.08秒高速化できました。

さらにに5の倍数が入るとどうなるか？

2の倍数か3の倍数か5の倍数が出現するパターンは30ごとに周期的に繰り返しますから、周期の中でいずれの倍数でもないものだけチェックに回すようにしました。

実行時間は、0.29秒でした。0.01秒だけ早くなりましたが、倍数チェックだけ増やしても、そこまで大きくは改善されませんね。

素数判定：10億以下の場合

さらに範囲を広げて、1,000,000,000（10億）以下の自然数nの素数判定プログラムを作成します。

さっきのプログラムで999,999,937を判定すると、実行時間は1.01秒でした。さきほどより0.72秒遅くなっていますね。

2,3,5の倍数を省略してきたので、7の倍数も追加したい気持ちになりますが、その場合周期が210(= 2 x 3 x 5 x 7)となって210通りの場合分けを考えなければならず、かえって非効率ですね。もっとよいアプローチが必要です。

ここで、素数ではない自然数の約数について考えてみましょう。

例えば、81の約数は 1, 3, 9, 27, 81ですよね。約数は、両端から順にペアにして掛け算すると 1 x 81, 3 x 27, 9 x 9 となって、いずれも積は81です。

81を3で割ると対応する27になるってことは、81は27でも割り切れるってことですね。

このように、素数判定するなら約数を並べて前半の半分（81の場合は9）までで割り切れるかどうかを調べればよいわけです。この半分の数値は、sqrt(81) にあたる数値です。

つまり、プログラム的にはsqrt(n)以下の数についてだけ割り切れるかどうかを調べればOKなんです。

これを踏まえてコードを書き直すと…

数学ライブラリの平方根の計算は浮動小数点誤差が気になるため、1回分余裕をもってループを回すようにしています。

実行すると0.19秒で、1.01秒と比べると0.82秒も高速化できました。

さらにもう少しコードを整理しましょう。

i <= sqrt(n) という条件は、i x i <= n に置き換えられます。こちらの方が浮動小数点が出てこなくて、すっきり高速に計算できるはず。

実行時間を確認すると0.19秒……先ほどと変わっていませんが、0.01秒未満の範囲で若干高速化されてるはずです。

素数を数えて落ち着くんだ

少なくとも10億以下の自然数に対してはそんなに悪くない実行時間で素数判定できるようになりました。

では、いよいよ素数を数えて落ち着いていきましょう。

以下のようなprimesListメソッドを作ります。

// n以下の素数を数える
// 入力: n
// 出力: n以下の素数の数とその内訳
import java.util.*;
class Main {
    static List<Integer> primesList(int n) {
        ....
    }
    public static void main(String[] args) {
        int n = 10;
        List<Integer> primes = primesList(n);
        System.out.println(primes.size() + "個の素数");
        for (int p : primes) {
            System.out.print(p + " ");
            if (p >= 1000) {
                System.out.print(" ...");
                break;
            }
        }
        System.out.println();
    }
}

素数をたくさん表示させようとすると標準出力に時間がかかるので、ひとまず1,000以上の大きな素数は表示せずに、数えた素数の個数と1,000未満の素数の一覧だけが表示されるようにしています。

素数を数える：10以下の場合

まずは10以下の素数を数えます。

素数判定のときと同じ要領で、全部書いてみました。

10以下の素数4つを数えて落ち着きました。

素数を数える 1,000以下の場合

次に、1,000以下の素数を数えます。

さきほど作った素数判定を使ってやってみましょう。

1,000以下の168個の素数を0.20秒で数えることができました。いい感じですね。

素数を数える：一千万以下の場合

次に、10,000,000以下の素数を数えてみたいのですが、先ほどのコードでそのまま実行すると、paiza.IOではタイムアウトとなってしまいます。（※paiza.IOは2.00秒以上の時間のかかるプログラムの実行を途中で打ち切りますが、もし打ち切らないとしても、0.20秒かかっていた計算を単純に1万回行うはめになって、33分(<= 0.20秒 x 10,000 / 60秒)以上はかかってしまうのでどちらにしても現実的ではないですね）

ここから一気に1万倍ぐらい高速化するにはどうすべきか？

素数判定のときに、2と3と5の倍数については判定しないようにしましたよね。自身を除いて何らかの倍数である数値は、素数ではありません。

「素数を見つけたら都度その倍数をすべて素数候補から除外することで、素数を絞り込んで見つけやすくする」という処理をすると、小さな素数から順にどんどん見つけていくことができます。

このようなアルゴリズムを「エラトステネスの篩（ふるい）」といいます。（エラトステネスの篩 - Wikipedia）

コードは以下のようになります。

ちょっと長いですが、「sieve[i]がtrueなら、iは素数である」というコードです。

sieveの要素は最初はすべてtrueであり、そこから素数でない0, 1を除いて、素数である2の2倍以上の倍数：4, 6, 8, 10…...と順に候補から除外します。

2の倍数の除外が終わったら、次は3の2倍以上の倍数6, 9, 12, ...と順に候補から除外します。

このプログラムを実行してみると、1.03秒で実行が終了し、10,000,000以下の素数が664,579個あるとわかりました。

さっきはタイムアウトしていたプログラムが、エラストテネスの篩のおかげで非常に高速に動作するようになりましたね！

素数を数える：一億以下の場合

しかし、素数の範囲をさらに拡大してn = 100,000,000にしてみると、タイムアウトしてしまいました。

これをさらに高速化するには、どうすればいいと思いますか？

素数判定のときは、sqrt(n) までの自然数で割り切れるかどうかを調べれば、nが素数かどうか判定できましたよね。この性質をエラトステネスの篩でも活用してみましょう。ふるう区間を sqrt(n) 個に分割して、それぞれの区間に個別にふるいを適用します。

まず、0から sqrt(n)-1 までの範囲の素数のリストをエラトステネスの篩で求めます。この素数のリストがあれば、残りの sqrt(n)-1 個のそれぞれの区間をふるうことができます。

このように、エラトステネスの篩を特定の区間に適用する操作を「区間篩」といいます。

コードにするとこんな感じ。

↓この辺はインデックスの調整がやや込み入っていますが「すでに見つかっている素数pの倍数をうまく探している」と理解しておいてください。pの倍数を探すので、pで割った余りが重要な意味を持ちます。

int j = start_index + (p - (start_index % p)) % p;

このコードを実行すると実行時間1.79秒で、一億以下の素数5,761,455個すべてを数えることができました。ようやく落ち着きましたね。

ジョジョの奇妙な冒険第6部ストーンオーシャン 1 (ジャンプコミックス)

作者: 荒木飛呂彦
出版社/メーカー: 集英社
発売日: 2000/05/01
メディア: コミック
購入: 1人クリック: 101回
この商品を含むブログ (56件) を見る

もっと素数を数えて落ち着くには

というわけで、一億以下の素数に適用できるアルゴリズムを紹介しました。

さらに大きな素数を数えたい人は、フェルマーテスト（フェルマーの小定理 - Wikipedia）を足がかりに、確率的素数判定法を試してみるのがよいかと思います。

また、今回のはエラトステネスの篩と区間篩を利用しました。ふるいを使った素数判定法はほかにもありますので、興味のある人は試してみてください。

篩法 - Wikipedia
サンダラムの篩 - Wikipedia

数学的な理屈よりも、計算機を回して世界で一番ビッグな素数を探したいという人は、メルセンヌ素数の概要をつかんで、GIMPS (Great Internet Mersenne Prime Search)プロジェクトに参加するのがよいかと思います。（ビットコインのマイニングよりもロマンがあるかもしれません）

メルセンヌ数 - Wikipedia
Great Internet Mersenne Prime Search - PrimeNet

「素数を自分で数えるのは苦手だけど眺めるのは好き」という人は、OEIS (The On-Line Encyclopedia of Integer Sequences)で好みの素数に関連する数列を探してみてください。

The On-Line Encyclopedia of Integer Sequences® (OEIS®)

「そこまで素数に興味がない」という人（よくここまで読みましたね）も、GNUの素因数分解コマンドの factor/gfactor だけでも知っておくと、素数に関して何かあったときに役立つと思います。

また、動画でプログラミングが学べる「paizaラーニング」では、「アルゴリズム入門編」のレッスンも公開しております。アルゴリズムについて学びたいプログラミング初心者の方はぜひごらんください。

途中で出てきた画像の漫画はこちら

「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。

そして、paizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。

スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。