【C++】指定した範囲内の素数を見つけるプログラムの作り方

このチュートリアルでは、指定された範囲（区間）内に存在する素数を見つけるC++プログラムについて解説します。

ここでは、下限と上限となる2つの整数が与えられ、その範囲内のすべての素数を出力するプログラムを作成します。

アルゴリズムの考え方

素数とは、1とその数自身以外に正の約数を持たない、1より大きい自然数のことです。本プログラムでは、以下の手順で素数を判定します。

• 範囲内の各整数 i に対して、2から i / 2 までの数で順番に割り切れるかどうかを確認します。
• 1つでも割り切れる数が見つかった場合、その数は素数ではありません。
• 最後まで割り切れる数が見つからなければ、その数は素数として出力します。
• 0と1は素数の定義に当てはまらないため、あらかじめ除外しています。

判定には、素数かどうかを記録するためのフラグ変数を使用します。割り切れる約数が見つかった時点でフラグを0にし、break文でループを抜けることで無駄な計算を省いています。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, i, j, flag;
    // 下限の設定
    a = 3;
    // 上限の設定
    b = 12;
    cout << "\nPrime numbers between "
    << a << " and " << b << " are: ";
    for (i = a; i <= b; i++) {
        if (i == 1 || i == 0)
        continue;
        flag = 1;
        for (j = 2; j <= i / 2; ++j) {
            if (i % j == 0) {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
        cout << i << " ";
    }
    return 0;
}

実行結果

Prime numbers between 3 and 12 are: 3 5 7 11

この例では、3から12の間に存在する素数「3、5、7、11」が出力されます。

補足：計算量をさらに減らすには

上記のコードでは約数の探索範囲を i / 2 までとしていますが、実際には sqrt(i)（平方根）まで調べれば十分です。約数は平方根を境にペアで現れるため、探索範囲を狭めることで大きな数に対しても高速に動作します。