Encuentre el XOR de los primeros N números primos

Dado un entero positivo N , la tarea es encontrar el XOR de los primeros N números primos.
Ejemplos: 
 

Entrada: N = 3 
Salida: 4 
Los primeros 3 números primos son 2, 3 y 5. 
Y 2 ^ 3 ^ 5 = 4
Entrada: N = 5 
Salida: 8  

Acercarse:  

1. Crear Tamiz de Eratóstenes para identificar si un número es primo o no en tiempo O(1).
2. Ejecute un ciclo comenzando desde 1 hasta y a menos que encontremos N números primos.
3. XOR todos los números primos y despreciar los que no son primos.
4. Finalmente, imprima el XOR de los primeros ^N números primos.

A continuación se muestra la implementación del enfoque anterior: 

// 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 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 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# 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

<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>

3

Complejidad del tiempo: O(n + MAX*log(log(MAX)))

Espacio Auxiliar: O(MAX)