Bitwise XOR of all prime numbers present in an array

Updated

Given an array of integers ‘arr’, the task is to find the bitwise XOR of all the prime numbers present in the array.

Examples :

Input : arr[] = {2, 5, 8, 4, 3}
Output : 4

Input : arr[] = {7, 12, 2, 6, 11}
Output : 14

Approach :

-> Create a sieve to check whether an element is prime or not in O(1). -> Traverse the array and check if the number is prime. If it is prime, store it in a vector. -> Then, compute the xor of all the elements of the vector.

Implementation :

// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 
  
bool prime[100005]; 
  
void SieveOfEratosthenes(int n) 
{ 
  
    memset(prime, true, sizeof(prime)); 
  
    // false here indicates 
    // that it is not prime 
    prime[1] = false; 
  
    for (int p = 2; p * p <= n; p++) { 
  
        // If prime[p] is not changed, 
        // then it is a prime 
        if (prime[p]) { 
  
            // Update all multiples of p, 
            // set them to non-prime 
            for (int i = p * 2; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 
} 
  
// Function that computes
// xor of all prime elements
int XOR_OF_PRIMES(int arr[], int n) 
{ 
    SieveOfEratosthenes(100004); 
  
    // this vector will contain 
    // prime numbers
    vector<int> v; 
  
    for (int i = 0; i < n; i++) { 
  
        // if the element is prime 
        if (prime[arr[i]]) 
            v.push_back(arr[i]); 
    }   
    int ans;
    //initialize ans with fist element of vector
    ans = v[0];
    for(int j=1;j<v.size();j++)
      ans = ans^v[j];
    return ans;

} 
  
// Driver code 
int main() 
{ 
  
    int arr[] = { 4, 3, 2, 6, 100, 17 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout<<XOR_OF_PRIMES(arr, n); 
 
    return 0; 
} 

Output :

16
Comment
Mithlesh Upadhyay Published 15 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials