C++で配列内のすべての素数のXORを求める方法

問題概要

この問題では、n個の要素からなる配列が与えられます。求めるのは、配列に含まれるすべての素数のXOR(排他的論理和)です。

具体例で問題を確認してみましょう。

入力 − {2, 6, 8, 9, 11}

出力 − 9

解説 − 配列内の素数は「2」と「11」の2つです。2 XOR 11 = 9 となるため、答えは 9 になります。

解決のためのアプローチ

この問題を解くには、まず配列内のすべての素数を特定し、それらを順にXORしていくことで結果を求めます。

各要素が素数かどうかを判定するには、エラトステネスの篩(Sieve of Eratosthenes)を使用するのが効率的です。あらかじめ素数表を作成しておけば、各要素に対して高速に素数判定が可能となり、素数である要素のみをXOR演算していきます。

実装例

この解決策を実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
bool prime[100005];
void SieveOfEratosthenes(int n) {
    memset(prime, true, sizeof(prime));
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
}
int findXorOfPrimes(int arr[], int n){
    SieveOfEratosthenes(100005);
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (prime[arr[i]])
            result = result ^ arr[i];
    }
    return result;
}
int main() {
    int arr[] = { 4, 3, 2, 6, 100, 17 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The xor of all prime number of the array is : "<<findXorOfPrimes(arr, n);
    return 0;
}

出力

The xor of all prime number of the array is : 16

コードの解説

このプログラムでは、配列 {4, 3, 2, 6, 100, 17} に含まれる素数は「3」「2」「17」の3つです。これらのXORを計算すると、3 XOR 2 = 1、1 XOR 17 = 16 となるため、出力は 16 になります。

• SieveOfEratosthenes関数：エラトステネスの篩を用いて、指定した範囲までの素数表を事前に作成します。
• findXorOfPrimes関数：配列の各要素を素数表と照合し、素数であれば結果変数にXORしていきます。

計算量

エラトステネスの篩による前処理は O(N log log N)、その後の各要素の判定とXOR演算は O(N) で処理できるため、要素数や値の範囲が大きい場合でも効率的に動作するアルゴリズムです。