C++で指定した範囲内の素数の個数を数える方法

はじめに

プログラミングにおいて、指定された範囲内に含まれる素数の個数を求めることは、古典的でありながら非常に重要な課題の一つです。本記事では、C++を使って区間 [START, END] 内の素数を数える方法を解説します。

ここでは、範囲の始点と終点を表す2つの変数 START と END が与えられます。目的は、この区間に含まれる素数の総数を求めることです。

素数の判定には、シンプルな手法を用います。ある数 i が素数であるかどうかは、「1 と i 自身以外に、i を割り切る数が存在しないこと」を確認すれば判別できます。具体的には、2 から i/2 までの各整数で i を割り、余りが 0 になるものがひとつもなければ、その数は素数であると判断し、カウントを増やしていきます。

実行例

入力

Start=1 End=20

出力

Primes in Ranges : 8

解説

1 から 20 までの間に存在する素数は、2, 3, 5, 7, 11, 13, 17, 19 の 8 個です。

入力

Start=100 End=200

出力

Primes in Ranges : 21

解説

100 から 200 までの間に存在する素数は、101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 の 21 個です。

アルゴリズムの流れ

• 範囲を表す変数として START と END を受け取ります。
• 関数 countPrimes(int strt, int end) は、指定された範囲内の素数の個数を返します。
• カウンタ変数 count を 0 で初期化します。
• for ループを使い、i = strt から i <= end まで順に走査します。
• 各数値 i に対して isprime(i) を呼び出し、素数かどうかを判定します。
• 関数 isprime(int num) は、num が素数でなければ 0 を、素数であれば 1 を返します。
• ループが終了したら、count を結果として返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int isprime(int num){
    if (num <= 1)
        return 0;
    for (int i = 2; i <= num/2; i++){
        if (num % i == 0)
            { return 0; }
    }
    return 1; //if both failed then num is prime
}
int countPrimes(int strt,int end){
    int count=0;
    for(int i=strt;i<=end;i++){
        if(isprime(i)==1)
            { count++; }
    }
    return count;
}
int main(){
    int START=10, END=20;
    cout <<endl<<"Primes in Ranges : "<<countPrimes(START,END);
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Primes in Ranges : 4

処理のポイントと計算量

このプログラムでは、10 から 20 までの範囲に含まれる素数(11, 13, 17, 19)がカウントされ、結果として 4 が出力されます。

素数判定を行う isprime 関数は、2 から num/2 まで順に割り算を試すため、1 回あたりの計算量は O(num) となります。そのため、範囲全体では O((END − START) × END) 程度の時間がかかり、扱う範囲が大きくなると処理速度が低下します。

より効率化したい場合は、判定範囲を √num まで縮める方法が有効です。ある数が n で割り切れないのであれば、それより大きな約数の組合せでも割り切れないため、√num まで調べれば十分だからです。さらに広い範囲を高速に処理したい場合は、エラトステネスのふるいを活用することで、素数を効率的に列挙・集計できます。