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

Trong bài toán này, chúng ta được đưa ra một mảng gồm n phần tử. Nhiệm vụ của chúng ta là in xor của tất cả các số nguyên tố của mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - {2, 6, 8, 9, 11}

Đầu ra -

Để giải quyết vấn đề này, chúng ta sẽ tìm tất cả các số nguyên tố của mảng và xor chúng để tìm ra kết quả. Để kiểm tra xem phần tử có phải là số nguyên tố hay không, chúng tôi sẽ sử dụng thuật toán sieve và sau đó xor tất cả các phần tử là số nguyên tố.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

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