2つの区間の間にある素数を表示するC++プログラムの解説

素数とは、1より大きい整数であり、約数が1とその数自身のみである数のことです。最初の素数には、2、3、5、7、11、13、17などがあります。

2つの区間の間には、多くの素数が存在することがあります。例えば、区間5から20の間にある素数は以下の通りです。

5, 7, 11, 13, 17, 19

素数を求めるC++プログラム

それでは、2つの区間の間にある素数を見つけて表示するプログラムを見ていきましょう。以下のコードでは、下限（lbound）から上限（ubound）まで順番に各数値を判定し、素数であれば出力します。

サンプルコード

#include <iostream>
using namespace std;
void PrimeNumbers (int lbound, int ubound) {
    int flag, i;
    while (lbound <= ubound) {
        flag = 0;
        for(i = 2; i <= lbound/2; i++) {
            if(lbound % i == 0) {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        cout<<lbound<<" ";
        lbound++;
    }
}
int main() {
    int lowerbound = 20, upperbound = 50;
    cout<<"Prime numbers between "<<lowerbound<<" and "<<upperbound<<" are: ";
    PrimeNumbers(lowerbound,upperbound);
    return 0;
}

実行結果

Prime numbers between 20 and 50 are: 23 29 31 37 41 43 47

プログラムの仕組み

main()関数の処理

main()関数の中身は非常にシンプルです。coutオブジェクトでメッセージを出力した後、引数に下限と上限を渡してPrimeNumbers()関数を呼び出しているだけです。該当するコード部分は以下の通りです。

cout<<"Prime numbers between "<<lowerbound<<" and "<<upperbound<<" are: ";
PrimeNumbers(lowerbound,upperbound);

PrimeNumbers()関数による素数判定

PrimeNumbers()関数では、whileループを使ってlboundからuboundまでの各数値を1つずつ取り出し、その数が素数かどうかを判定します。素数であると判明した場合のみ、その数を表示します。

具体的な判定の手順は次の通りです。まずwhileループに入るたびに、フラグ変数flagを0で初期化します。続くforループでは、2からその数の半分までの整数で順番に割り切れるかどうかを確認します。もし割り切れる数が見つかった場合は、その数は素数ではないためflagを1に設定し、break文でforループを抜けます。

forループが終了した時点でもflagが0のままであれば、どの数でも割り切れなかったということなので、その数は素数です。このときだけcoutで数値を出力します。最後にlboundをインクリメントして、次の数値の判定へ進みます。

while (lbound <= ubound) {
    flag = 0;
    for(i = 2; i <= lbound/2; i++) {
        if(lbound % i == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
    cout<<lbound<<" ";
    lbound++;
}

まとめ

このプログラムは、フラグ変数を使ったシンプルな素数判定アルゴリズムの良い例です。判定範囲を「2から対象の数の半分まで」に絞ることで、無駄な計算を減らしています。さらに効率化したい場合は、判定範囲を対象の数の平方根までに狭めたり、エラトステネスの篩などのアルゴリズムを採用したりすることも可能です。