Given a positive integer N, the task is to find the XOR of the first N prime numbers.
Examples:
Input: N = 3
Output: 4
First 3 prime numbers are 2, 3 and 5.
And 2 ^ 3 ^ 5 = 4
Input: N = 5
Output: 8
Approach:
- Create Sieve of Eratosthenes to identify if a number is prime or not in O(1) time.
- Run a loop starting from 1 until and unless we find N prime numbers.
- XOR all the prime numbers and neglect those which are not prime.
- 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 numbersint 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 codeint 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 approachMAX = 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 numbersdef 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 sieveSieveOfEratosthenes()n = 4# Find the xor of 1st n prime numbersprint(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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
