XOR của tất cả số nguyên tố trong mảng C++

Trong bài toán này, cho một mảng n phần tử. Nhiệm vụ là in ra XOR của tất cả các số nguyên tố trong mảng.

Ví dụ để hiểu bài toán:

Input – {2, 6, 8, 9, 11}

Output – XOR của 2 và 11 (các số nguyên tố) = 2 ^ 11 = 9

Để giải bài toán, ta tìm tất cả số nguyên tố trong mảng sau đó XOR chúng. Để kiểm tra số nguyên tố, dùng sàng Eratosthenes rồi XOR các phần tử là số nguyên tố.

Ví dụ minh họa

#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 << "XOR của tất cả số nguyên tố trong mảng: " << findXorOfPrimes(arr, n);
    return 0;
}

Kết quả

XOR của tất cả số nguyên tố trong mảng: 16

Giải thích: Các số nguyên tố trong mảng: 3, 2, 17. XOR = 3 ^ 2 ^ 17 = 16