C++で合計が素数かつn未満となるペアの個数を数える方法

正の整数 n が入力として与えられます。この記事の目的は、合計 (i + j) が素数であり、かつ n 未満となるペア (i, j) の個数を求めることです。ここで、i ≠ j かつ i, j ≥ 1 という条件を満たす必要があります。

例として、n が 4 の場合を考えてみましょう。このとき条件を満たすペアは (1, 2) の 1 つだけです。1 + 2 = 3 は素数であり、4 未満だからです。また、1 と 2 はどちらも 1 以上の条件を満たしています。

それでは、具体例を使って理解を深めましょう。

入力 − n = 7

出力 − 合計が素数かつ n 未満となるペアの数 − 3

説明 − 該当するペアは (1, 2)、(1, 4)、(2, 3) です。合計の 3、5、5 はいずれも素数であり、7 未満です。

入力 − n = 10

出力 − 合計が素数かつ n 未満となるペアの数 − 6

説明 − 該当するペアは (1, 2)、(1, 4)、(2, 3)、(1, 6)、(2, 5)、(3, 4) です。合計の 3、5、5、7、7、7 はいずれも素数であり、10 未満です。

プログラムで使用するアプローチ

このアプローチでは、まず関数 check_prime(bool check[], int temp) の中で「サンダラムの篩(Sieve of Sundaram)」を用いて、n 未満のすべての素数を求めます。サンダラムの篩は、(i + j + 2ij) の形式の数を除外していくことで素数を導き出すアルゴリズムです。

さらに、各奇数 temp について、合計が temp となる異なるペアの個数は temp / 2 であるという性質を利用します。

2 を除くすべての素数は奇数であるため、n 未満の素数が見つかるたびに、count に temp / 2 を加算していけばよいことになります。

• 変数 n を入力として受け取ります。
• 関数 prime_pair(int n) は n を受け取り、合計が素数かつ n 未満となるペアの個数を返します。
• カウント用変数 count を 0 で初期化します。
• サンダラムの篩は入力 n に対して 2*n + 2 未満の素数を生成するため、n を半分にした値を temp_2 に格納します。
• 長さ temp_2 の配列 check[] を作成し、(i + j + 2*i*j) の形式の数値を true としてマークできるようにします。すべての要素は false で初期化します。
• 関数 check_prime(bool check[], int temp) では、(i + j + 2*i*j) の形式で、その合計が temp 以下となる数値に対して check[] を true に設定します。
• for ループでインデックス i = 1 から i ≤ temp_2 まで配列 check[] を走査します。
• check[i] が false の場合、対応する素数は temp = 2*i + 1 となります。
• 合計が temp になるペアの個数は temp / 2 なので、count に temp / 2 を加算します。
• for ループが終了した時点で、合計が素数かつ n 未満となるペアの総数が得られます。
• count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp){
    for (int i=1; i<=temp; i++){
        for (int j=i; (i + j + 2*i*j) <= temp; j++){
            check[i + j + 2*i*j] = true;
        }
    }
}
int prime_pair(int n){
    int count = 0;
    int temp;
    int temp_2 = (n-2)/2;
    bool check[temp_2 + 1];
    memset(check, false, sizeof(check));
    check_prime(check, temp_2);
    for (int i=1; i <= temp_2; i++){
        if (check[i] == false){
            temp = 2*i + 1;
            count += (temp / 2);
        }
    }
    return count;
}
int main(){
    int n = 10;
    cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
    return 0;
}

出力

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

Count of pairs with sum as a prime number and less than n are: 6