Dado un entero positivo N , la tarea es calcular el XOR bit a bit de los primeros N números que son un producto de exactamente dos números primos distintos .
Ejemplos:
Entrada: N = 20
Salida: 7
Explicación: Los números del rango [1, 20] que son un producto de exactamente dos números primos distintos son {6, 10, 12, 14, 15, 18, 20}.
Bitwise XOR de estos números = 6 ^ 10 ^ 12 ^ 14 ^ 15 ^ 18 ^ 20 = 7Entrada: N = 50
Salida: 26
Enfoque ingenuo: el enfoque más simple es iterar sobre cada número hasta N y encontrar los factores primos de cada número mediante el método de descomposición en factores primos . Los números para los cuales el conteo de factores primos distintos resulta ser dos, luego calcule su XOR con la respuesta. Después de comprobar todos los números, imprima la respuesta obtenida.
Complejidad de Tiempo: O(N*√N)
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el Tamiz de Eratóstenes con una pequeña modificación. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable ans como 0 para almacenar el resultado requerido.
- Cree una array de enteros , arr[] de tamaño N+1 , e inicialice con todos ceros, donde arr[i] denota el número de números primos distintos de i .
- Itere en el rango [2, N] usando la variable i y si el valor de arr[i] es 0 , entonces, revise todos los múltiplos de i usando la variable j e incremente el valor de arr[j] en 1 ya que i es un factor primo de j .
- Iterar en el rango [2, N] usando la variable i y si arr[i] es igual a 2 , luego tomar XOR de i con ans .
- Imprime el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count prime factors
// using Sieve of Eratosthenes
void sieve(int arr[], int n)
{
// Iterate in the [2, N]
for (int i = 2; i <= n; i++) {
// If the current number is prime
if (arr[i] == 0)
// Iterate over all multiples of i
for (int j = 2 * i; j <= n; j += i) {
// Increment arr[j] by 1 since
// i is a prime factor of j
arr[j]++;
}
}
}
// Function to find Bitwise XOR
// of first N natural numbers
// satisfying the given condition
void findXOR(int n)
{
// arr[i]: Stores the number of
// distinct prime factors of i
int arr[n + 1] = { 0 };
// Initialize the base cases
arr[0] = arr[1] = 1;
// Function Call to fill
// the array, arr[]
sieve(arr, n);
// Store the required result
int ans = 0;
// Iterate over the range [2, N]
for (int i = 2; i <= n; i++) {
// Check if the i-th number has
// exactly two distinct prime factor
if (arr[i] == 2) {
// If true, update the answer
ans = (ans ^ i);
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
// Given Input
int n = 20;
// Function Call
findXOR(n);
return 0;
}
Java
// Java program for the above approach
public class GFG {
// Function to count prime factors
// using Sieve of Eratosthenes
static void sieve(int arr[], int n)
{
// Iterate in the [2, N]
for (int i = 2; i <= n; i++) {
// If the current number is prime
if (arr[i] == 0)
// Iterate over all multiples of i
for (int j = 2 * i; j <= n; j += i) {
// Increment arr[j] by 1 since
// i is a prime factor of j
arr[j]++;
}
}
}
// Function to find Bitwise XOR
// of first N natural numbers
// satisfying the given condition
static void findXOR(int n)
{
// arr[i]: Stores the number of
// distinct prime factors of i
int arr[] = new int[n + 1];
// Initialize the base cases
arr[0] = arr[1] = 1;
// Function Call to fill
// the array, arr[]
sieve(arr, n);
// Store the required result
int ans = 0;
// Iterate over the range [2, N]
for (int i = 2; i <= n; i++) {
// Check if the i-th number has
// exactly two distinct prime factor
if (arr[i] == 2) {
// If true, update the answer
ans = (ans ^ i);
}
}
// Print the result
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
// Given Input
int n = 20;
// Function Call
findXOR(n);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to count prime factors # using Sieve of Eratosthenes def sieve(arr, n): # Iterate in the [2, N] for i in range(2, n + 1, 1): # If the current number is prime if (arr[i] == 0): # Iterate over all multiples of i for j in range(2 * i, n + 1, i): # Increment arr[j] by 1 since # i is a prime factor of j arr[j] += 1 # Function to find Bitwise XOR # of first N natural numbers # satisfying the given condition def findXOR(n): # arr[i]: Stores the number of # distinct prime factors of i arr = [0 for i in range(n + 1)] # Initialize the base cases arr[0] = arr[1] = 1 # Function Call to fill # the array, arr[] sieve(arr, n) # Store the required result ans = 0 # Iterate over the range [2, N] for i in range(2, n + 1, 1): # Check if the i-th number has # exactly two distinct prime factor if (arr[i] == 2): # If true, update the answer ans = (ans ^ i) # Print the result print(ans) # Driver Code if __name__ == '__main__': # Given Input n = 20 # Function Call findXOR(n) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Function to count prime factors
// using Sieve of Eratosthenes
static void sieve(int []arr, int n)
{
// Iterate in the [2, N]
for(int i = 2; i <= n; i++)
{
// If the current number is prime
if (arr[i] == 0)
// Iterate over all multiples of i
for(int j = 2 * i; j <= n; j += i)
{
// Increment arr[j] by 1 since
// i is a prime factor of j
arr[j]++;
}
}
}
// Function to find Bitwise XOR
// of first N natural numbers
// satisfying the given condition
static void findXOR(int n)
{
// arr[i]: Stores the number of
// distinct prime factors of i
int []arr = new int[n + 1];
// Initialize the base cases
arr[0] = arr[1] = 1;
// Function Call to fill
// the array, arr[]
sieve(arr, n);
// Store the required result
int ans = 0;
// Iterate over the range [2, N]
for(int i = 2; i <= n; i++)
{
// Check if the i-th number has
// exactly two distinct prime factor
if (arr[i] == 2)
{
// If true, update the answer
ans = (ans ^ i);
}
}
// Print the result
Console.WriteLine(ans);
}
// Driver code
public static void Main(String[] args)
{
// Given Input
int n = 20;
// Function Call
findXOR(n);
}
}
// This code is contributed by ankThon
Javascript
<script>
// JavaScript program for the above approach
// Function to count prime factors
// using Sieve of Eratosthenes
function sieve( arr, n)
{
// Iterate in the [2, N]
for (var i = 2; i <= n; i++) {
// If the current number is prime
if (arr[i] == 0)
// Iterate over all multiples of i
for (var j = 2 * i; j <= n; j += i) {
// Increment arr[j] by 1 since
// i is a prime factor of j
arr[j]++;
}
}
}
// Function to find Bitwise XOR
// of first N natural numbers
// satisfying the given condition
function findXOR( n)
{
// arr[i]: Stores the number of
// distinct prime factors of i
var arr = new Array(n + 1);
arr.fill(0);
// Initialize the base cases
arr[0] = arr[1] = 1;
// Function Call to fill
// the array, arr[]
sieve(arr, n);
// Store the required result
var ans = 0;
// Iterate over the range [2, N]
for (var i = 2; i <= n; i++) {
// Check if the i-th number has
// exactly two distinct prime factor
if (arr[i] == 2) {
// If true, update the answer
ans = (ans ^ i);
}
}
// Print the result
document.write( ans);
}
n = 20;
// Function Call
findXOR(n);
// This code is contributed by SoumikMondal
</script>
Producción:
7
Complejidad de tiempo: O(N*log(logN))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prakersh009 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA