素数を出力するプログラムをRubyで書いてみた

きっかけ

あるイベントで素数まつなかさんにお会いしたのが始まりです。
数学博士でありながらRailsエンジニアでもあるすごい人です。
まつなかさんについての詳細は以下動画が面白いです。

素数の本

そのイベントで「素数表１５万個」という本に出会いました。
ただひたすら素数が書いているだけな本ですが、ある１ページが気になった。
そこにはC++で素数を出力するプログラムのソースコードが書いてありました。
試さずにはいられなくなり、まつなかさんにお願いして譲ってもらいました。

素数コード

実際に書いてあったコードです。
ターミナルアプリによっては、最初の出力がカットされる場合あり。

prime_num.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int maxn = 2020000;
    vector<bool> n;
    n.resize(maxn,1);

    for(int i=2; i<maxn; i++){
        if(n[i]){cout << i << endl;}
        for(int j=i; j<maxn; j+=i){
            n[j] = 0;
        }
    }
    return 0;
}

Rubyに変換

今回は生成AI(ChatGPT)に聞いてみました。
C++で何となく分かっても難しかった。
今回はどのような仕組みになっているかを重視しました。

prime_num.rb

maxn = 2_020_000
n = Array.new(maxn, true)
n[0] = n[1] = false # 0と1は素数ではない

(2...maxn).each do |i|
    if n[i]
        puts i
        (i * 2...maxn).step(i) do |j|
            n[j] = false
        end
    end
end

解説(ChatGPTからの引用）

何をしているの？

このコードは「素数」を探して、それを全部表示しています。
素数とは、1と自分自身以外の数字では割り切れない数字のことです。たとえば、2, 3, 5, 7 などが素数です。

どうやって素数を見つけるの？

コンピュータがたくさんの数字をチェックして、「これは素数かな？」と調べています。この方法を 「エラトステネスの篩（ふるい）」 と言います。

ステップ

1. 大きなリストを作成
   202万個の数字を用意し、最初は「すべて素数かもしれない」と仮定します。

2. 0と1を除外
   0 と 1 は素数ではないので、最初にチェックから外します。

3. 2から順番にチェック

   • 2 が素数なので「見つけた！」と出力します。
   • そして、2 の倍数（4, 6, 8, …）をすべてリストから削除します。

4. 次の数字をチェック
   次に残っている数字（3 など）を探して、それを素数として出力し、同じようにその倍数をすべて削除します。

5. すべての数字を調査
   202万まで調査を続けると、最終的にリストには素数だけが残ります。

このコードのすごいところ！

• とても効率的に素数を見つけられるアルゴリズムです。
• 一つずつ数字を調べるよりも、何倍も速い方法です。

例え話

たとえば、たくさんの友達が並んでいて、「素数の子だけ残って！」というゲームをしているとします。
最初に「2の倍数の子は全員いなくなって！」と言い、次に「3の倍数の子は…」と進めていくと、最後には素数の子だけが残ります。

（引用ここまで）

感想

Rubyに変換し、解説を読んで素数の導き方が勉強になりました。
エラトステネスの篩って言葉があるのも初耳です。
例え話も友達を例にしていて分かりやすかった。
まつなかさんの動画は記事作成時に見つけたもので、爆笑してしまいました。

あとがき

C++のコードについて、改良版を追記します。
改良点は以下の通りです。

• 0と1の出力を無効化
• 倍数の無効化範囲の改善　j = i から j = i * i に変更

などです。

prime_num_v2.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int maxn = 2020000;
    vector<bool> n(maxn, true);
    n[0] = n[1] = false; // 0 と 1 は素数ではない

    for(int i=2; i*i<maxn; i++){
        if(n[i]){
            for(int j=i*i; j<maxn; j+=i){
                n[j] = false;
            }
        }
    }

    for(int i=2; i<maxn; i++){
        if(n[i]){
            cout << i << endl;
        }
    }

    return 0;
}