Recuento de todos los valores de N en [L, R] tales que el recuento de primos hasta N también es primo

Posted on by Rudeus Greyrat

Dados dos enteros positivos L y R , la tarea es encontrar el número total de valores entre el rango [L, R] tal que el conteo de números primos de 1 a N también sea primo.
Ejemplos: 

Entrada: L = 3, R = 10 
Salida: 4 
Explicación: 
Número de primos hasta 3, 4, 5, 6, 7, 8, 9 y 10 son 2, 2, 3, 3, 4, 4, 4 y 4 respectivamente . Entonces, hay un total de 4 de esos números {3, 4, 5, 6} [3, 10].
Entrada: L = 4, R = 12 
Salida: 5 
Explicación: 
Número de primos hasta 4, 5, 6, 7, 8, 9, 10, 11 y 12 son 2, 3, 3, 4, 4, 4, 4, 5 y 5 respectivamente. Entonces, hay un total de 5 números {4, 5, 6, 11, 12} que satisfacen la condición en el rango [4, 12]. 
 

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es atravesar todos los valores en el rango [1, L – 1] y contar el número de números primos en ese rango. Una vez calculado, compruebe si el recuento es primo o no. Ahora, comience a recorrer los valores en el rango [L, R] uno por uno y verifique si el número es primo o no y aumente el conteo en consecuencia. Para cada conteo actualizado, verifique si es primo o no y, en consecuencia, actualice el conteo de números requeridos del rango dado. 
Complejidad de tiempo: O(R 2 )
Enfoque eficiente: 
El enfoque anterior puede optimizarse aún más mediante el tamiz de Eratóstenes . Siga los pasos a continuación para resolver el problema:  

  1. Encuentra todos los números primos hasta R usando un tamiz.
  2. Mantenga una array de frecuencias para almacenar el recuento de números primos hasta para todos los valores hasta R .
  3. Cree otra array de conteo (digamos freqPrime[] ) y agregue 1 en la posición i si el conteo acumulativo de primos totales hasta i es en sí mismo un número primo.
  4. Ahora, para cualquier rango de L a R , el número de primos locos se puede calcular mediante freqPrime[R] – freqPrime[L – 1] .

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 the number of
// crazy primes in the given range [L, R]
int count_crazy_primes(int L, int R)
{
    // Stores all primes
    int prime[R + 1] = { 0 };
 
    // Stores count of primes
    int countPrime[R + 1] = { 0 };
 
    // Stores if frequency of
    // primes is a prime or not
    // upto each index
    int freqPrime[R + 1] = { 0 };
 
    prime[0] = prime[1] = 1;
    // Sieve of Eratosthenes
    for (int p = 2; p * p <= R; p++) {
        if (prime[p] == 0) {
            for (int i = p * p;
                 i <= R; i += p)
 
                prime[i] = 1;
        }
    }
 
    // Count primes
    for (int i = 1; i <= R; i++) {
        countPrime[i] = countPrime[i - 1];
 
        // If i is a prime
        if (!prime[i]) {
            countPrime[i]++;
        }
    }
 
    // Stores frequency of primes
    for (int i = 1; i <= R; i++) {
        freqPrime[i] = freqPrime[i - 1];
 
        // If the frequency of primes
        // is a prime
        if (!prime[countPrime[i]]) {
 
            // Increase count of
            // required numbers
            freqPrime[i]++;
        }
    }
 
    // Return the required count
    return (freqPrime[R]
            - freqPrime[L - 1]);
}
 
// Driver Code
int main()
{
    // Given Range
    int L = 4, R = 12;
 
    // Function Call
    cout << count_crazy_primes(L, R);
    return 0;
}

Java

// Java implementation of the approach
class GFG{
 
// Function to count the number of
// crazy primes in the given range [L, R]
static int count_crazy_primes(int L, int R)
{
     
    // Stores all primes
    int prime[] = new int[R + 1];
 
    // Stores count of primes
    int countPrime[] = new int[R + 1];
 
    // Stores if frequency of
    // primes is a prime or not
    // upto each index
    int freqPrime[] = new int[R + 1];
     
    prime[0] = 1;
    prime[1] = 1;
     
    // Sieve of Eratosthenes
    for(int p = 2; p * p <= R; p++)
    {
       if (prime[p] == 0)
       {
           for(int i = p * p;
                   i <= R; i += p)
              prime[i] = 1;
       }
    }
 
    // Count primes
    for(int i = 1; i <= R; i++)
    {
       countPrime[i] = countPrime[i - 1];
        
       // If i is a prime
       if (prime[i] != 0)
       {
           countPrime[i]++;
       }
    }
 
    // Stores frequency of primes
    for(int i = 1; i <= R; i++)
    {
       freqPrime[i] = freqPrime[i - 1];
        
       // If the frequency of primes
       // is a prime
       if (prime[countPrime[i]] != 0)
       {
            
           // Increase count of
           // required numbers
           freqPrime[i]++;
       }
    }
 
    // Return the required count
    return (freqPrime[R] -
            freqPrime[L - 1]);
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given range
    int L = 4, R = 12;
 
    // Function call
    System.out.println(count_crazy_primes(L, R));
}
}
 
// This code is contributed by Pratima Pandey    

Python3

# Python3 program for the above approach
 
# Function to count the number of
# crazy primes in the given range [L, R]
def count_crazy_primes(L, R):
 
    # Stores all primes
    prime = [0] * (R + 1)
 
    # Stores count of primes
    countPrime = [0] * (R + 1)
 
    # Stores if frequency of
    # primes is a prime or not
    # upto each index
    freqPrime = [0] * (R + 1)
 
    prime[0] = prime[1] = 1
     
    # Sieve of Eratosthenes
    p = 2
    while p * p <= R:
        if (prime[p] == 0):
            for i in range (p * p,
                            R + 1 , p):
                prime[i] = 1
        p += 1
    
    # Count primes
    for i in range (1 , R + 1):
        countPrime[i] = countPrime[i - 1]
 
        # If i is a prime
        if (not prime[i]):
            countPrime[i] += 1
 
    # Stores frequency of primes
    for i in range (1, R + 1):
        freqPrime[i] = freqPrime[i - 1]
 
        # If the frequency of primes
        # is a prime
        if (not prime[countPrime[i]]):
 
            # Increase count of
            # required numbers
            freqPrime[i] += 1
 
    # Return the required count
    return (freqPrime[R] -
            freqPrime[L - 1])
 
# Driver Code
if __name__ =="__main__":
   
    # Given Range
    L = 4
    R = 12
 
    # Function Call
    print(count_crazy_primes(L, R))
 
# This code is contributed by Chitranayal

C#

// C# implementation of the approach
using System;
class GFG{
   
// Function to count the number of
// crazy primes in the given range [L, R]
static int count_crazy_primes(int L,
                              int R)
{     
    // Stores all primes
    int []prime = new int[R + 1];
   
    // Stores count of primes
    int []countPrime = new int[R + 1];
   
    // Stores if frequency of
    // primes is a prime or not
    // upto each index
    int []freqPrime = new int[R + 1];
       
    prime[0] = 1;
    prime[1] = 1;
       
    // Sieve of Eratosthenes
    for(int p = 2; p * p <= R; p++)
    {
       if (prime[p] == 0)
       {
           for(int i = p * p; i <= R;
               i += p)
              prime[i] = 1;
       }
    }
   
    // Count primes
    for(int i = 1; i <= R; i++)
    {
       countPrime[i] = countPrime[i - 1];
          
       // If i is a prime
       if (prime[i] != 0)
       {
           countPrime[i]++;
       }
    }
   
    // Stores frequency of primes
    for(int i = 1; i <= R; i++)
    {
       freqPrime[i] = freqPrime[i - 1];
          
       // If the frequency of primes
       // is a prime
       if (prime[countPrime[i]] != 0)
       {            
           // Increase count of
           // required numbers
           freqPrime[i]++;
       }
    }
   
    // Return the required count
    return (freqPrime[R] -
            freqPrime[L - 1]);
}
   
// Driver code
public static void Main(String[] args)
{      
    // Given range
    int L = 4, R = 12;
   
    // Function call
    Console.WriteLine(
            count_crazy_primes(L, R));
}
}
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
 
// Function to count the number of
// crazy primes in the given range [L, R]
function count_crazy_primes(L, R)
{
     
    // Stores all primes
    let prime = Array.from({length: R+1}, (_, i) => 0);
 
    // Stores count of primes
    let countPrime = Array.from({length: R+1}, (_, i) => -1);
 
    // Stores if frequency of
    // primes is a prime or not
    // upto each index
    let freqPrime = Array.from({length: R+1}, (_, i) => 0);
     
    prime[0] = 1;
    prime[1] = 1;
     
    // Sieve of Eratosthenes
    for(let p = 2; p * p <= R; p++)
    {
       if (prime[p] == 0)
       {
           for(let i = p * p;
                   i <= R; i += p)
              prime[i] = 1;
       }
    }
 
    // Count primes
    for(let i = 1; i <= R; i++)
    {
       countPrime[i] = countPrime[i - 1];
        
       // If i is a prime
       if (prime[i] != 0)
       {
           countPrime[i]++;
       }
    }
    // Stores frequency of primes
    for (let i = 1; i <= R; i++) {
        freqPrime[i] = freqPrime[i - 1];
 
        // If the frequency of primes
        // is a prime
        if (!prime[countPrime[i]]) {
 
            // Increase count of
            // required numbers
            freqPrime[i]++;
        }
    }
 
 
    // Return the required count
    return (freqPrime[R] -
            freqPrime[L - 1]);
}
 
    // Driver Code
     
    // Given range
    let L = 4, R = 12;
 
    // Function call
    document.write(count_crazy_primes(L, R));
 
</script>
Producción: 

5

 

Complejidad de tiempo: O(R*log(log(R))) 
Espacio auxiliar: O(R)

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 *