C++で配列内のk番目ごとの素数の積を求める方法

問題概要

n個の素数を含む配列arr[n]と整数kが与えられたとき、配列内のk番目ごとの素数の積を求めることが本記事の課題です。

例えば、配列arr[] = {3, 5, 7, 11}、k = 2が与えられた場合、2番目ごとの素数である「5」と「11」を取り出し、その積(5 × 11 = 55)を計算して結果を出力します。

素数とは?

素数とは、1とその数自身以外のどの数でも割り切れない自然数のことです。素数の例としては、2、3、5、7、11、13などが挙げられます。

入出力例

入力: arr[] = {3, 5, 7, 11, 13}、k = 2
出力: 55
説明: 配列の2番目ごとの要素は「5」と「11」であり、その積は55になります。

入力: arr[] = {5, 7, 13, 23, 31}、k = 3
出力: 13
説明: 配列の3番目ごとの要素は「13」であるため、出力は13になります。

解決のためのアプローチ

• n個の要素を含む配列とkを入力として受け取り、k番目ごとの要素の積を求めます。
• 素数を高速に判定するためのふるい(エラトステネスの篩)を事前に作成します。
• 配列を先頭から走査し、k番目ごとの素数を見つけるたびに、積を保持する変数に掛け合わせていきます。
• 最終的な積を出力します。

アルゴリズム

開始
Step 1-> MAXを1000000として定義・初期化
Step 2-> bool型配列 prime[MAX + 1] を定義
Step 3-> 関数 createsieve() 内で
　　memset(prime, true, sizeof(prime)) を呼び出す
　　prime[1] = false を設定
　　prime[0] = false を設定
　　ループ: p = 2 から p * p <= MAX まで p++
　　　　もし prime[p] == true ならば、
　　　　　　ループ: i = p * 2 から i <= MAX まで i += p
　　　　　　　　prime[i] = false を設定
Step 4-> 関数 productOfKthPrimes(int arr[], int n, int k)
　　c = 0 を設定
　　product = 1 を設定
　　ループ: i = 0 から i < n まで i++
　　　　もし prime[arr[i]] ならば、
　　　　　　c を 1 増やす
　　　　　　もし c % k == 0 ならば、
　　　　　　　　product = product * arr[i] を設定
　　　　　　　　c = 0 にリセット
　　積を出力
Step 5-> main() 関数内で
　　createsieve() を呼び出す
　　n = 5、k = 2 を設定
　　arr[n] = { 2, 3, 11, 13, 23 } を設定
　　productOfKthPrimes(arr, n, k) を呼び出す
終了

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool prime[MAX + 1];
void createsieve() {
    memset(prime, true, sizeof(prime));
    // 0と1は素数ではない
    prime[1] = false;
    prime[0] = false;
    for (int p = 2; p * p <= MAX; p++) {
        if (prime[p] == true) {
            // pの倍数をすべて合成数としてマークする
            for (int i = p * 2; i <= MAX; i += p)
            prime[i] = false;
        }
    }
}
// 答えを計算する関数
void productOfKthPrimes(int arr[], int n, int k) {
    // 素数の個数をカウント
    int c = 0;
    // 素数の積を求める
    long long int product = 1;
    // 配列を走査
    for (int i = 0; i < n; i++) {
        // 要素が素数の場合
        if (prime[arr[i]]) {
            c++;
            if (c % k == 0) {
                product *= arr[i];
                c = 0;
            }
        }
    }
    cout << product << endl;
}
// メイン関数
int main() {
    // ふるいを作成
    createsieve();
    int n = 5, k = 2;
    int arr[n] = { 2, 3, 11, 13, 23 };
    productOfKthPrimes(arr, n, k);
    return 0;
}

出力結果

39

コードの解説

このプログラムでは、まずcreatesieve()関数がエラトステネスの篩を用いて、1000000以下のすべての素数を事前に判定します。これにより、任意の数が素数かどうかをO(1)の計算量で確認できるようになり、全体の処理が大幅に高速化されます。

続いてproductOfKthPrimes()関数が配列を先頭から走査し、各要素が素数であるかどうかを判定します。素数であればカウンタcをインクリメントし、cがkの倍数に達した時点でその要素を積に掛け合わせた後、カウンタをリセットします。

上記の実行例では、配列{2, 3, 11, 13, 23}の中から2番目ごとの素数である「3」と「13」が選ばれ、3 × 13 = 39が出力されます。なお、積が大きくなる可能性を考慮し、product変数にはオーバーフロー対策としてlong long int型を使用している点にも注目してください。