Dada una array arr[] de N enteros positivos. La tarea es imprimir todos los pares posibles de modo que su XOR sea un número primo .
Ejemplos:
Entrada: arr[] = {1, 3, 6, 11}
Salida: (1, 3) (1, 6) (3, 6) (6, 11)
Explicación:
El XOR de los pares anteriores:
1^3 = 2
1^6 = 7
3^6 = 5
6^11 = 13
Entrada: arr[] = { 22, 58, 63, 0, 47 }
Salida: (22, 63) (58, 63) (0, 47)
Explicación:
El XOR de los pares anteriores:
22^33 = 37
58^63 = 5
0^47 = 47
Acercarse:
- Genera todos los números primos usando Sieve of Eratosthenes .
- Para todos los pares posibles de la array dada , verifique si el XOR de ese par es primo o no.
- Si el XOR de un par es primo, imprima ese par; de lo contrario, verifique el siguiente par.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5;
bool isPrime[sz + 1];
// Function for Sieve of Eratosthenes
void generatePrime()
{
int i, j;
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for (i = 2; i * i <= sz; i++) {
// If i is prime, then make all
// multiples of i false
if (isPrime[i]) {
for (j = i * i; j < sz; j += i) {
isPrime[j] = false;
}
}
}
}
// Function to print all Pairs whose
// XOR is prime
void Pair_of_PrimeXor(int A[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// if A[i]^A[j] is prime,
// then print this pair
if (isPrime[(A[i] ^ A[j])]) {
cout << "(" << A[i]
<< ", " << A[j] << ") ";
}
}
}
}
// Driver Code
int main()
{
int A[] = { 1, 3, 6, 11 };
int n = sizeof(A) / sizeof(A[0]);
// Generate all the prime number
generatePrime();
// Function Call
Pair_of_PrimeXor(A, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
static int sz = (int) 1e5;
static boolean []isPrime = new boolean[sz + 1];
// Function for Sieve of Eratosthenes
static void generatePrime()
{
int i, j;
for (i = 2; i <= sz; i++)
isPrime[i] = true;
for (i = 2; i * i <= sz; i++) {
// If i is prime, then make all
// multiples of i false
if (isPrime[i]) {
for (j = i * i; j < sz; j += i) {
isPrime[j] = false;
}
}
}
}
// Function to print all Pairs whose
// XOR is prime
static void Pair_of_PrimeXor(int A[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// if A[i]^A[j] is prime,
// then print this pair
if (isPrime[(A[i] ^ A[j])]) {
System.out.print("(" + A[i]
+ ", " + A[j]+ ") ");
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 3, 6, 11 };
int n = A.length;
// Generate all the prime number
generatePrime();
// Function Call
Pair_of_PrimeXor(A, n);
}
}
// This code is contributed by sapnasingh4991
Python
# Python implementation of the above approach
sz = 10**5
isPrime = [True]*(sz + 1)
# Function for Sieve of Eratosthenes
def generatePrime():
i, j = 0, 0
isPrime[0] = isPrime[1] = False
for i in range(2, sz + 1):
if i * i > sz:
break
# If i is prime, then make all
# multiples of i false
if (isPrime[i]):
for j in range(i*i, sz, i):
isPrime[j] = False
# Function to print all Pairs whose
# XOR is prime
def Pair_of_PrimeXor(A, n):
for i in range(n):
for j in range(i + 1, n):
# if A[i]^A[j] is prime,
# then print this pair
if (isPrime[(A[i] ^ A[j])]):
print("(",A[i],",",A[j],")",end=" ")
# Driver Code
if __name__ == '__main__':
A = [1, 3, 6, 11]
n =len(A)
# Generate all the prime number
generatePrime()
# Function Call
Pair_of_PrimeXor(A, n)
# This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
class GFG
{
static int sz = (int) 1e5;
static bool []isPrime = new bool[sz + 1];
// Function for Sieve of Eratosthenes
static void generatePrime()
{
int i, j;
for (i = 2; i <= sz; i++)
isPrime[i] = true;
for (i = 2; i * i <= sz; i++) {
// If i is prime, then make all
// multiples of i false
if (isPrime[i]) {
for (j = i * i; j < sz; j += i) {
isPrime[j] = false;
}
}
}
}
// Function to print all Pairs whose
// XOR is prime
static void Pair_of_PrimeXor(int []A, int n)
{
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// if A[i]^A[j] is prime,
// then print this pair
if (isPrime[(A[i] ^ A[j])]) {
Console.Write("(" + A[i]
+ ", " + A[j]+ ") ");
}
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 1, 3, 6, 11 };
int n = A.Length;
// Generate all the prime number
generatePrime();
// Function Call
Pair_of_PrimeXor(A, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of
// the above approach
const sz = 100000;
let isPrime = new Array(sz + 1).fill(true);
// Function for Sieve of Eratosthenes
function generatePrime()
{
let i, j;
isPrime[0] = isPrime[1] = false;
for (i = 2; i * i <= sz; i++) {
// If i is prime, then make all
// multiples of i false
if (isPrime[i]) {
for (j = i * i; j < sz; j += i) {
isPrime[j] = false;
}
}
}
}
// Function to print all Pairs whose
// XOR is prime
function Pair_of_PrimeXor(A, n)
{
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// if A[i]^A[j] is prime,
// then print this pair
if (isPrime[(A[i] ^ A[j])]) {
document.write("(" + A[i]
+ ", " + A[j] + ") ");
}
}
}
}
// Driver Code
let A = [ 1, 3, 6, 11 ];
let n = A.length;
// Generate all the prime number
generatePrime();
// Function Call
Pair_of_PrimeXor(A, n);
</script>
Producción:
(1, 3) (1, 6) (3, 6) (6, 11)
Complejidad de tiempo: O(N 2 ), donde N es la longitud de la array dada.
Espacio Auxiliar: O(sz)