C++ STLを活用して指定範囲内の素数をすべて出力する方法

はじめに

本記事では、C++の標準テンプレートライブラリ（STL）を活用して、指定された範囲内に存在する素数をすべて出力するプログラムを解説します。

ここでは、2つの整数 a と b が与えられたとき、その間に含まれるすべての素数を見つけて表示することを目標とします。素数の生成には、古典的かつ高速なアルゴリズムである「エラトステネスのふるい」をサブルーチンとして利用し、求めた素数は vector に格納してから一括して出力します。

アルゴリズムの流れ

エラトステネスのふるいは、n 以下の素数を効率的に列挙できる手法です。2 から順に素数を確定させながら、その倍数をふるい落としていくことで、計算量を O(N log log N) 程度まで抑えられます。

このプログラムでは、次の手順で指定範囲内の素数を抽出します。

1. 開始値 start 以下の素数リストを作成する
2. 終了値 end 以下の素数リストを作成する
3. STL の set_difference で両者の差分（＝範囲内の素数）を求める
4. remove_if で余分な要素を除去し、結果を出力する

サンプルコード

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

// n 未満の素数をすべて返す（エラトステネスのふるい）
vector<unll> eratosthenes(unll n) {
    vector<bool> prime_num(n + 1, true);
    prime_num[0] = false;
    prime_num[1] = false;
    int m = sqrt(n);
    for (unll p = 2; p <= m; p++) {
        if (prime_num[p]) {
            for (unll i = p * 2; i <= n; i += p)
                prime_num[i] = false;
        }
    }
    vector<unll> elements;
    for (int i = 0; i < n; i++)
        if (prime_num[i])
            elements.push_back(i);
    return elements;
}

// 余分な 0 を除去するための述語関数
bool check_zero(unll i) {
    return i == 0;
}

// [start, end) の範囲に含まれる素数を返す
vector<unll> sieve_range(unll start, unll end) {
    vector<unll> s1 = eratosthenes(start);
    vector<unll> s2 = eratosthenes(end);
    vector<unll> elements(end - start);
    set_difference(s2.begin(), s2.end(), s1.begin(),
                   s1.end(), elements.begin());
    vector<unll>::iterator itr =
        remove_if(elements.begin(), elements.end(), check_zero);
    elements.resize(itr - elements.begin());
    return elements;
}

int main(void) {
    unll start = 10;
    unll end = 90;
    vector<unll> elements = sieve_range(start, end);
    for (auto i : elements)
        cout << i << ' ';
    return 0;
}

実行結果

11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89

コードのポイント

• eratosthenes 関数： エラトステネスのふるいを実装し、n 未満の素数を vector として返します。
• sieve_range 関数： 2つのふるい結果の差分を set_difference で計算することで、指定範囲内の素数だけを効率よく取り出します。
• check_zero 関数： 差分計算時に残った不要な 0 の要素を remove_if で除去するための述語関数です。

このように、STL のアルゴリズムを組み合わせることで、簡潔で読みやすいコードのまま素数の範囲列挙を実現できます。エラトステネスのふるいの計算量は非常に小さいため、比較的大きな範囲でも高速に動作する点も大きなメリットです。