XOR de todos los números primos en una array en posiciones divisibles por K

Dada una array arr de números enteros de tamaño N y un número entero K , la tarea es encontrar el XOR de todos los números que son primos y están en una posición divisible por K.

Ejemplos: 

Entrada: arr[] = {2, 3, 5, 7, 11, 8}, K = 2 
Salida: 4 
Explicación: Las 
posiciones que son divisibles por K son 2, 4, 6 y los elementos son 3, 7, 8. 
3 y 7 son primos entre estos. 
Por lo tanto XOR = 3 ^ 7 = 4 

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 3 
Salida: 3 
 

Enfoque ingenuo: recorra la array y para cada posición i que sea divisible por k , verifique si es primo o no. Si es un número primo, calcule el XOR de este número con la respuesta anterior.

Enfoque eficiente: un enfoque eficiente es usar Sieve Of Eratosthenes . La array de tamices se puede usar para verificar que un número sea primo o no en el tiempo O (1) . 

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

// C++ program to find XOR of
// all Prime numbers in an Array
// at positions divisible by K
 
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000005
 
void SieveOfEratosthenes(vector<bool>& prime)
{
    // 0 and 1 are not prime numbers
    prime[1] = false;
    prime[0] = false;
 
    for (int p = 2; p * p < MAX; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * 2;
                 i < MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the required XOR
void prime_xor(int arr[], int n, int k)
{
 
    vector<bool> prime(MAX, true);
 
    SieveOfEratosthenes(prime);
 
    // To store XOR of the primes
    long long int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If the number is a prime
        if (prime[arr[i]]) {
 
            // If index is divisible by k
            if ((i + 1) % k == 0) {
                ans ^= arr[i];
            }
        }
    }
 
    // Print the xor
    cout << ans << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, 5, 7, 11, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
 
    // Function call
    prime_xor(arr, n, K);
 
    return 0;
}

// Java program to find XOR of
// all Prime numbers in an Array
// at positions divisible by K
class GFG {
 
    static int MAX = 1000005;
    static boolean prime[] = new boolean[MAX];
     
    static void SieveOfEratosthenes(boolean []prime)
    {
        // 0 and 1 are not prime numbers
        prime[1] = false;
        prime[0] = false;
     
        for (int p = 2; p * p < MAX; p++) {
     
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
     
                // Update all multiples of p
                for (int i = p * 2;i < MAX; i += p)
                    prime[i] = false;
            }
        }
    }
     
    // Function to find the required XOR
    static void prime_xor(int arr[], int n, int k)
    {
         
        for(int i = 0; i < MAX; i++)
            prime[i] = true;
     
        SieveOfEratosthenes(prime);
     
        // To store XOR of the primes
        int ans = 0;
     
        // Traverse the array
        for (int i = 0; i < n; i++) {
     
            // If the number is a prime
            if (prime[arr[i]]) {
     
                // If index is divisible by k
                if ((i + 1) % k == 0) {
                    ans ^= arr[i];
                }
            }
        }
     
        // Print the xor
        System.out.println(ans);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 2, 3, 5, 7, 11, 8 };
        int n = arr.length;
        int K = 2;
     
        // Function call
        prime_xor(arr, n, K);
     
    }
}
 
// This code is contributed by Yash_R

# Python3 program to find XOR of
# all Prime numbers in an Array
# at positions divisible by K
MAX = 1000005
 
def SieveOfEratosthenes(prime) :
 
    # 0 and 1 are not prime numbers
    prime[1] = False;
    prime[0] = False;
 
    for p in range(2, int(MAX ** (1/2))) :
 
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True) :
 
            # Update all multiples of p
            for i in range(p * 2, MAX, p) :
                prime[i] = False;
 
# Function to find the required XOR
def prime_xor(arr, n, k) :
 
    prime = [True]*MAX ;
 
    SieveOfEratosthenes(prime);
 
    # To store XOR of the primes
    ans = 0;
 
    # Traverse the array
    for i in range(n) :
 
        # If the number is a prime
        if (prime[arr[i]]) :
 
            # If index is divisible by k
            if ((i + 1) % k == 0) :
                ans ^= arr[i];
 
    # Print the xor
    print(ans);
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 2, 3, 5, 7, 11, 8 ];
    n = len(arr);
    K = 2;
 
    # Function call
    prime_xor(arr, n, K);
 
# This code is contributed by Yash_R

// C# program to find XOR of
// all Prime numbers in an Array
// at positions divisible by K
using System;
 
class GFG {
 
    static int MAX = 1000005;
    static bool []prime = new bool[MAX];
     
    static void SieveOfEratosthenes(bool []prime)
    {
        // 0 and 1 are not prime numbers
        prime[1] = false;
        prime[0] = false;
     
        for (int p = 2; p * p < MAX; p++) {
     
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
     
                // Update all multiples of p
                for (int i = p * 2;i < MAX; i += p)
                    prime[i] = false;
            }
        }
    }
     
    // Function to find the required XOR
    static void prime_xor(int []arr, int n, int k)
    {
         
        for(int i = 0; i < MAX; i++)
            prime[i] = true;
     
        SieveOfEratosthenes(prime);
     
        // To store XOR of the primes
        int ans = 0;
     
        // Traverse the array
        for (int i = 0; i < n; i++) {
     
            // If the number is a prime
            if (prime[arr[i]]) {
     
                // If index is divisible by k
                if ((i + 1) % k == 0) {
                    ans ^= arr[i];
                }
            }
        }
     
        // Print the xor
        Console.WriteLine(ans);
    }
     
    // Driver code
    public static void Main (string[] args)
    {
        int []arr = { 2, 3, 5, 7, 11, 8 };
        int n = arr.Length;
        int K = 2;
     
        // Function call
        prime_xor(arr, n, K);
     
    }
}
 
// This code is contributed by Yash_R

<script>
 
// Javascript program to find XOR of
// all Prime numbers in an Array
// at positions divisible by K
const MAX = 1000005;
 
function SieveOfEratosthenes(prime)
{
     
    // 0 and 1 are not prime numbers
    prime[1] = false;
    prime[0] = false;
 
    for(let p = 2; p * p < MAX; p++)
    {
         
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
             
            // Update all multiples of p
            for(let i = p * 2; i < MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the required XOR
function prime_xor(arr, n, k)
{
    let prime = new Array(MAX).fill(true);
 
    SieveOfEratosthenes(prime);
 
    // To store XOR of the primes
    let ans = 0;
 
    // Traverse the array
    for(let i = 0; i < n; i++)
    {
         
        // If the number is a prime
        if (prime[arr[i]])
        {
             
            // If index is divisible by k
            if ((i + 1) % k == 0)
            {
                ans ^= arr[i];
            }
        }
    }
     
    // Print the xor
    document.write(ans);
}
 
// Driver code
let arr = [ 2, 3, 5, 7, 11, 8 ];
let n = arr.length;
let K = 2;
 
// Function call
prime_xor(arr, n, K);
 
// This code is contributed by subham348
 
</script>

Complejidad de tiempo: O(N log (log N))

Espacio Auxiliar:  O(√n)