Recuento de elementos que tienen el valor de Totient de Euler uno menos que él mismo

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros y un rango L a R , la tarea es encontrar el número total de elementos en la array desde el índice L a R que satisface la siguiente condición:

F(arr[i]) = arr[i] - 1
 

donde F(x) es la Función Totient de Euler .

 

Ejemplos:

Entrada: arr[] = {2, 4, 5, 8}, L = 1, R = 3 
Salida: 2 
Explicación: 
Aquí en el rango dado, F(2) = 1 y (2 – 1) = 1. De manera similar , F(5) = 4 y (5 – 1) = 4. 
Entonces, el recuento total de índices que satisfacen la condición es 2. 
Entrada: arr[] = {9, 3, 4, 6, 8}, L = 3 , R = 5 
Salida: 0 
Explicación: 
En el rango dado no hay ningún elemento que satisfaga la condición dada. 
Entonces el conteo total es 0.

Enfoque ingenuo: el enfoque ingenuo para resolver este problema es iterar sobre todos los elementos de la array y verificar si el valor de Totient de Euler del elemento actual es uno menos que él mismo. Si es así, entonces incremente el conteo.
Complejidad de tiempo: O(N * sqrt(N)) 
Espacio auxiliar: O(1)
Enfoque eficiente:

La función Totient de Euler F(n) para una entrada n es el conteo de números en {1, 2, 3, …, n} que son primos relativos a n, es decir, los números cuyo Máximo Común Divisor con n es 1.

  1. Si observamos, podemos notar que la condición dada arriba solo es satisfecha por los números primos .
  2. Entonces, todo lo que necesitamos hacer es calcular el número total de números primos en el rango dado.
  3. Usaremos la criba de Eratóstenes para calcular números primos de manera eficiente.
  4. Además, calcularemos previamente la cantidad de números primos en una array de conteo.

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;
 
long long prime[1000001] = { 0 };
 
// Seiev of Erotosthenes method to compute all primes
void seiveOfEratosthenes()
{
    for (int i = 2; i < 1000001; i++)
        prime[i] = 1;
 
    for (int i = 2; i * i < 1000001; i++) {
        // If current number is marked prime then mark its
        // multiple as non-prime
        if (prime[i] == 1)
            for (int j = i * i; j < 1000001; j += i)
                prime[j] = 0;
    }
}
 
// Function to count the number
// of element satisfying the condition
void CountElements(int arr[], int n, int L, int R)
{
    seiveOfEratosthenes();
 
    long long countPrime[n + 1] = { 0 };
 
    // Compute the number of primes in count prime array
    for (int i = 1; i <= n; i++)
        countPrime[i] = countPrime[i - 1] + prime[arr[i - 1]];
 
    // Print the number of elements satisfying the condition
    printf("%lld", (countPrime[R] - countPrime[L - 1]));
    return;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 4, 5, 8 };
    // Size of the array
    int N = sizeof(arr) / sizeof(int);
    int L = 1, R = 3;
    // Function Call
    CountElements(arr, N, L, R);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

C

// C program for the above approach
#include <stdio.h>
#include <string.h>
 
long long prime[1000001];
 
// Seiev of Erotosthenes method to compute all primes
void seiveOfEratosthenes()
{
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i < 1000001; i++)
        prime[i] = 1;
 
    for (int i = 2; i * i < 1000001; i++) {
        // If current number is marked prime then mark its
        // multiple as non-prime
        if (prime[i] == 1)
            for (int j = i * i; j < 1000001; j += i)
                prime[j] = 0;
    }
}
 
// Function to count the number
// of element satisfying the condition
void CountElements(int arr[], int n, int L, int R)
{
    seiveOfEratosthenes();
    long long countPrime[n + 1];
    memset(countPrime, 0, sizeof(countPrime));
 
    // Compute the number of primes in count prime array
    for (int i = 1; i <= n; i++)
        countPrime[i]
            = countPrime[i - 1] + prime[arr[i - 1]];
 
    // Print the number of elements satisfying the condition
    printf("%lld", (countPrime[R] - countPrime[L - 1]));
    return;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 4, 5, 8 };
    // Size of the array
    int N = sizeof(arr) / sizeof(int);
    int L = 1, R = 3;
    // Function Call
    CountElements(arr, N, L, R);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static int prime[] = new int[1000001];
 
// Seiev of Erotosthenes method to
// compute all primes
static void seiveOfEratosthenes()
{
    for(int i = 2; i < 1000001; i++)
    {
       prime[i] = 1;
    }
 
    for(int i = 2; i * i < 1000001; i++)
    {
        
       // If current number is
       // marked prime then mark
       // its multiple as non-prime
       if (prime[i] == 1)
       {
           for(int j = i * i;
                   j < 1000001; j += i)
           {
              prime[j] = 0;
           }
       }
    }
}
 
// Function to count the number
// of element satisfying the condition
static void CountElements(int arr[], int n,
                          int L, int R)
{
    seiveOfEratosthenes();
 
    int countPrime[] = new int[n + 1];
 
    // Compute the number of primes
    // in count prime array
    for(int i = 1; i <= n; i++)
    {
       countPrime[i] = countPrime[i - 1] +
                        prime[arr[i - 1]];
    }
 
    // Print the number of elements
    // satisfying the condition
    System.out.print(countPrime[R] -
                     countPrime[L - 1] + "\n");
 
    return;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 2, 4, 5, 8 };
 
    // Size of the array
    int N = arr.length;
    int L = 1, R = 3;
 
    // Function Call
    CountElements(arr, N, L, R);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program for the above approach
prime = [0] * (1000001)
 
# Seiev of Erotosthenes method to
# compute all primes
def seiveOfEratosthenes():
 
    for i in range(2, 1000001):
        prime[i] = 1
     
    i = 2
    while(i * i < 1000001):
 
        # If current number is
        # marked prime then mark
        # its multiple as non-prime
        if (prime[i] == 1):
            for j in range(i * i, 1000001, i):
                prime[j] = 0
         
        i += 1
 
# Function to count the number
# of element satisfying the condition
def CountElements(arr, n, L, R):
     
    seiveOfEratosthenes()
 
    countPrime = [0] * (n + 1)
 
    # Compute the number of primes
    # in count prime array
    for i in range(1, n + 1):
        countPrime[i] = (countPrime[i - 1] +
                          prime[arr[i - 1]])
     
    # Print the number of elements
    # satisfying the condition
    print(countPrime[R] -
          countPrime[L - 1])
 
    return
 
# Driver Code
 
# Given array
arr = [ 2, 4, 5, 8 ]
 
# Size of the array
N = len(arr)
L = 1
R = 3
 
# Function call
CountElements(arr, N, L, R)
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
class GFG{
 
static int []prime = new int[1000001];
 
// Seiev of Erotosthenes method to
// compute all primes
static void seiveOfEratosthenes()
{
    for(int i = 2; i < 1000001; i++)
    {
        prime[i] = 1;
    }
 
    for(int i = 2; i * i < 1000001; i++)
    {
         
        // If current number is
        // marked prime then mark
        // its multiple as non-prime
        if (prime[i] == 1)
        {
            for(int j = i * i;
                    j < 1000001; j += i)
            {
                prime[j] = 0;
            }
        }
    }
}
 
// Function to count the number
// of element satisfying the condition
static void CountElements(int []arr, int n,
                          int L, int R)
{
    seiveOfEratosthenes();
 
    int []countPrime = new int[n + 1];
 
    // Compute the number of primes
    // in count prime array
    for(int i = 1; i <= n; i++)
    {
        countPrime[i] = countPrime[i - 1] +
                         prime[arr[i - 1]];
    }
 
    // Print the number of elements
    // satisfying the condition
    Console.Write(countPrime[R] -
                  countPrime[L - 1] + "\n");
 
    return;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 2, 4, 5, 8 };
 
    // Size of the array
    int N = arr.Length;
    int L = 1, R = 3;
 
    // Function Call
    CountElements(arr, N, L, R);
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
 
// JavaScript program for the above approach
 
let prime = new Uint8Array(1000001);
 
// Seiev of Erotosthenes method to
// compute all primes
function seiveOfEratosthenes()
{
 
    for (let i = 2; i < 1000001;
        i++) {
        prime[i] = 1;
    }
 
    for (let i = 2; i * i < 1000001;
        i++) {
 
        // If current number is
        // marked prime then mark
        // its multiple as non-prime
        if (prime[i] == 1) {
            for (let j = i * i;
                j < 1000001; j += i) {
                prime[j] = 0;
            }
        }
    }
}
 
// Function to count the number
// of element satisfying the condition
function CountElements(arr, n, L, R)
{
    seiveOfEratosthenes();
 
    countPrime = new Uint8Array(n + 1);
 
    // Compute the number of primes
    // in count prime array
    for (let i = 1; i <= n; i++) {
        countPrime[i] = countPrime[i - 1]
                        + prime[arr[i - 1]];
    }
 
    // Print the number of elements
    // satisfying the condition
    document.write((countPrime[R]
                - countPrime[L - 1])
        + "<br>");
 
    return;
}
 
// Driver Code
 
    // Given array
    let arr = [ 2, 4, 5, 8 ];
 
    // Size of the array
    let N = arr.length;
    let L = 1, R = 3;
 
    // Function Call
    CountElements(arr, N, L, R);
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>
Producción: 

2

Complejidad de tiempo: O(N * log(logN))  
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por deepika_sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *