C++のSTLを使って指定した範囲の素数を出力する方法

C++のSTL（標準テンプレートライブラリ）を活用すると、指定した範囲内に存在する素数を効率よく出力できます。この記事では、エラトステネスの篩で素数の一覧を生成し、set_difference()による差集合の計算とremove_if()による不要な要素の削除を組み合わせて、任意の区間の素数だけを取り出す方法を解説します。

アルゴリズムの流れ

開始
    ユーザー定義型 stl（unsigned long long int）を宣言する
    stl 型のベクトルを返す関数 number(a) を定義する
        bool 型のベクトル Prime_Number を宣言し、すべて true で初期化する
            Prime_Number[0] = false
            Prime_Number[1] = false
        整数型の変数 b を宣言し、b = sqrt(a) で初期化する
        for (stl pr = 2; pr <= b; pr++)
            もし Prime_Number[pr] が true ならば
                for (stl i = pr*2; i <= a; i += pr)
                    Prime_Number[i] = false
        vector 型の result を宣言する
        for (int i = 0; i < a; i++)
            もし Prime_Number[i] が true ならば
                result.push_back(i)
        result を返す
    bool 型の関数 remove_zero(i) を定義する
        i == 0 を返す（ベクトルから 0 を取り除くために使用）
    stl 型の First_Num と Last_Num を引数に取る関数 Number_Range() を定義する
        s1 = number(First_Num)：0〜First_Num までの素数を求める
        s2 = number(Last_Num)：0〜Last_Num までの素数を求める
        vector 型の result(Last_Num - First_Num) を宣言する
        set_difference() を呼び出して、2つのベクトルの差集合を求める
        イテレータ itr = remove_if(result.begin(), result.end(), remove_zero) で余分な 0 を削除する
        result.resize(itr - result.begin()) でサイズを調整する
        result を返す
    main 関数
        First_Num = 20、Last_Num = 50 で初期化する
        result = Number_Range(First_Num, Last_Num) を呼び出す
        「20から50までの素数は次の通りです」と出力する
        for (auto i : result) で各素数の値を出力する
終了

コードの解説

number() 関数：エラトステネスの篩

number() 関数は、古典的な素数生成アルゴリズムである「エラトステネスの篩」を実装しています。0 から a までのすべての数を一旦素数候補（true）として初期化し、2 から √a までの各素数についてその倍数を順に false へと書き換えていきます。最後まで true として残ったインデックスが素数なので、それらを vector に格納して返します。計算量は O(N log log N) と非常に効率的です。

set_difference()：2つの素数リストの差集合

Number_Range() 関数では、まず 0〜First_Num までの素数リスト s1 と、0〜Last_Num までの素数リスト s2 を生成します。STL の set_difference() は「s2 には含まれるが s1 には含まれない要素」、つまり First_Num より大きく Last_Num 以下の素数だけを result に書き込みます。ソート済みのシーケンスに対して線形時間 O(N) で動作するため、大きな範囲でも高速です。

remove_if() と resize()：余分な 0 の除去

set_difference() は書き込まなかった残りの領域を 0 で埋めるため、そのままでは余分な 0 が混在します。そこで remove_if() に述語関数 remove_zero() を渡して 0 を末尾へ移動させ、戻り値のイテレータとの差を使って result を resize() することで、素数だけのきれいなベクトルが完成します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int stl;

// 0〜a までの素数をエラトステネスの篩で求める
vector<stl> number(stl a) {
    vector<bool> Prime_Number(a + 1, true);
    Prime_Number[0] = false;
    Prime_Number[1] = false;
    int b = sqrt(a);
    for (stl pr = 2; pr <= b; pr++) {
        if (Prime_Number[pr]) {
            for (stl i = pr * 2; i <= a; i += pr)
                Prime_Number[i] = false;
        }
    }
    vector<stl> result;
    for (int i = 0; i < a; i++)
        if (Prime_Number[i])
            result.push_back(i);
    return result;
}

// ベクトルから 0 を取り除くための述語関数
bool remove_zero(stl i) {
    return i == 0;
}

// First_Num 〜 Last_Num の範囲の素数を求める
vector<stl> Number_Range(stl First_Num, stl Last_Num) {
    vector<stl> s1 = number(First_Num); // 0〜First_Num までの素数
    vector<stl> s2 = number(Last_Num);  // 0〜Last_Num までの素数
    vector<stl> result(Last_Num - First_Num);
    // 2つのベクトルの差集合を求める
    set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(), result.begin());
    // 余分な 0 を削除する
    vector<stl>::iterator itr = remove_if(result.begin(), result.end(), remove_zero);
    result.resize(itr - result.begin());
    return result;
}

int main(void) {
    stl First_Num = 20, Last_Num = 50;
    vector<stl> result = Number_Range(First_Num, Last_Num);
    cout << "The Prime Numbers from " << First_Num << " to " << Last_Num << " are: ";
    for (auto i : result)
        cout << i << ' ';
    return 0;
}

実行結果

The Prime Numbers from 20 to 50 are: 23 29 31 37 41 43 47

このように、20 以上 50 以下の素数である 23、29、31、37、41、43、47 が正しく出力されます。main 関数内の First_Num と Last_Num の値を変更するだけで、任意の範囲の素数を同じコードで求められます。