Sunday, October 12, 2025
HomeData Modelling & AIFind the XOR of first N Prime Numbers

Find the XOR of first N Prime Numbers

Given a positive integer N, the task is to find the XOR of the first N prime numbers.
Examples: 
 

Input: N = 3 
Output:
First 3 prime numbers are 2, 3 and 5. 
And 2 ^ 3 ^ 5 = 4
Input: N = 5 
Output: 8  

Approach:  

  1. Create Sieve of Eratosthenes to identify if a number is prime or not in O(1) time.
  2. Run a loop starting from 1 until and unless we find N prime numbers.
  3. XOR all the prime numbers and neglect those which are not prime.
  4. Finally, print the XOR of the 1st N prime numbers.

Below is the implementation of the above approach: 

C++




// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
 
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[MAX + 1];
void SieveOfEratosthenes()
{
    memset(prime, true, sizeof(prime));
 
    prime[1] = false;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
 
            // Set all multiples of p to non-prime
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the xor of 1st N prime numbers
int xorFirstNPrime(int n)
{
    // Count of prime numbers
    int count = 0, num = 1;
 
    // XOR of prime numbers
    int xorVal = 0;
 
    while (count < n) {
 
        // If the number is prime xor it
        if (prime[num]) {
            xorVal ^= num;
 
            // Increment the count
            count++;
        }
 
        // Get to the next number
        num++;
    }
    return xorVal;
}
 
// Driver code
int main()
{
    // Create the sieve
    SieveOfEratosthenes();
 
    int n = 4;
 
    // Find the xor of 1st n prime numbers
    cout << xorFirstNPrime(n);
 
    return 0;
}


Java




// Java implementation of the approach
class GFG
{
static final int MAX = 10000;
 
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
static boolean prime[] = new boolean [MAX + 1];
 
static void SieveOfEratosthenes()
{
    int i ;
    for (i = 0; i < MAX + 1; i++)
    {
        prime[i] = true;
    }
 
    prime[1] = false;
 
    for (int p = 2; p * p <= MAX; p++)
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
 
            // Set all multiples of p to non-prime
            for (i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the xor of
// 1st N prime numbers
static int xorFirstNPrime(int n)
{
    // Count of prime numbers
    int count = 0, num = 1;
 
    // XOR of prime numbers
    int xorVal = 0;
 
    while (count < n)
    {
 
        // If the number is prime xor it
        if (prime[num])
        {
            xorVal ^= num;
 
            // Increment the count
            count++;
        }
 
        // Get to the next number
        num++;
    }
    return xorVal;
}
 
// Driver code
public static void main (String[] args)
{
    // Create the sieve
    SieveOfEratosthenes();
 
    int n = 4;
 
    // Find the xor of 1st n prime numbers
    System.out.println(xorFirstNPrime(n));
 
}
}
 
// This code is contributed by AnkitRai01


Python3




# Python3 implementation of the approach
MAX = 10000
 
# Create a boolean array "prime[0..n]" and
# initialize all entries it as true.
# A value in prime[i] will finally be false +
# if i is Not a prime, else true.
prime = [True for i in range(MAX + 1)]
 
def SieveOfEratosthenes():
 
    prime[1] = False
 
    for p in range(2, MAX + 1):
 
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True):
 
            # Set all multiples of p to non-prime
            for i in range(2 * p, MAX + 1, p):
                prime[i] = False
 
# Function to return the xor of
# 1st N prime numbers
def xorFirstNPrime(n):
     
    # Count of prime numbers
    count = 0
    num = 1
 
    # XOR of prime numbers
    xorVal = 0
 
    while (count < n):
 
        # If the number is prime xor it
        if (prime[num]):
            xorVal ^= num
 
            # Increment the count
            count += 1
 
        # Get to the next number
        num += 1
 
    return xorVal
 
# Driver code
 
# Create the sieve
SieveOfEratosthenes()
 
n = 4
 
# Find the xor of 1st n prime numbers
print(xorFirstNPrime(n))
 
# This code is contributed by Mohit Kumar


C#




// C# implementation of the approach
using System;
 
class GFG
{
     
static int MAX = 10000;
 
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
static bool []prime = new bool [MAX + 1];
 
static void SieveOfEratosthenes()
{
    int i ;
    for (i = 0; i < MAX + 1; i++)
    {
        prime[i] = true;
    }
 
    prime[1] = false;
 
    for (int p = 2; p * p <= MAX; p++)
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
 
            // Set all multiples of p to non-prime
            for (i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the xor of
// 1st N prime numbers
static int xorFirstNPrime(int n)
{
    // Count of prime numbers
    int count = 0, num = 1;
 
    // XOR of prime numbers
    int xorVal = 0;
 
    while (count < n)
    {
 
        // If the number is prime xor it
        if (prime[num])
        {
            xorVal ^= num;
 
            // Increment the count
            count++;
        }
 
        // Get to the next number
        num++;
    }
    return xorVal;
}
 
// Driver code
static public void Main ()
{
     
    // Create the sieve
    SieveOfEratosthenes();
    int n = 4;
 
    // Find the xor of 1st n prime numbers
    Console.Write(xorFirstNPrime(n));
}
}
 
// This code is contributed by Sachin


Javascript




<script>
 
    // Javascript implementation of the approach
     
    let MAX = 10000;
   
    // Create a boolean array "prime[0..n]" 
    // and initialize all entries it as true. 
    // A value in prime[i] will finally be false
    // if i is Not a prime, else true. 
    let prime = new Array(MAX + 1); 
       
    function SieveOfEratosthenes() 
    
        let i;
        for (i = 0; i < MAX + 1; i++)
        {
            prime[i] = true;
        }
       
        prime[1] = false
       
        for (let p = 2; p * p <= MAX; p++) 
        
       
            // If prime[p] is not changed, 
            // then it is a prime 
            if (prime[p] == true
            
       
                // Set all multiples of p to non-prime 
                for (i = p * 2; i <= MAX; i += p) 
                    prime[i] = false
            
        
    
       
    // Function to return the xor of 
    // 1st N prime numbers 
    function xorFirstNPrime(n) 
    
        // Count of prime numbers 
        let count = 0, num = 1; 
       
        // XOR of prime numbers 
        let xorVal = 0; 
       
        while (count < n)
        
       
            // If the number is prime xor it 
            if (prime[num]) 
            
                xorVal ^= num; 
       
                // Increment the count 
                count++; 
            
       
            // Get to the next number 
            num++; 
        
        return xorVal; 
    }
     
    // Create the sieve 
    SieveOfEratosthenes(); 
    let n = 4; 
   
    // Find the xor of 1st n prime numbers 
    document.write(xorFirstNPrime(n)); 
     
</script>


Output: 

3

 

Time Complexity: O(n + MAX*log(log(MAX)))

Auxiliary Space: O(MAX)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

RELATED ARTICLES

Most Popular

Dominic
32352 POSTS0 COMMENTS
Milvus
87 POSTS0 COMMENTS
Nango Kala
6720 POSTS0 COMMENTS
Nicole Veronica
11885 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11941 POSTS0 COMMENTS
Shaida Kate Naidoo
6840 POSTS0 COMMENTS
Ted Musemwa
7105 POSTS0 COMMENTS
Thapelo Manthata
6795 POSTS0 COMMENTS
Umr Jansen
6795 POSTS0 COMMENTS