Contar números < = N cuya diferencia con el conteo de primos hasta ellos es > = K

Posted on by Rudeus Greyrat

Dados dos enteros positivos N y K , la tarea es contar todos los números que cumplan las siguientes condiciones: 
Si el número es num , 
 

  • número ≤ norte .
  • abs(num – count) ≥ K donde count es el conteo de primos hasta num .

Ejemplos: 
 

Entrada: N = 10, K = 3 
Salida: 5 
6, 7, 8, 9 y 10 son los números válidos. Para el 6, la diferencia entre el 6 y los números primos hasta el 6 (2, 3, 5) es 3, es decir, 6 – 3 = 3. Para el 7, 8, 9 y 10, las diferencias son 3, 4, 5 y 6 respectivamente, que son ≥ K.
Entrada: N = 30, K = 13 
Salida: 10 
 

Requisito previo: Enfoque de búsqueda binaria : observe que la función que es la diferencia del número y el conteo de números primos hasta ese número es una función monótonamente creciente para un K particular . Además, si un número X es un número válido, entonces X + 1 también será un número válido. Prueba :

 
 

Deje que la función C i denote la cuenta de números primos hasta el número i. Ahora, 
para el número X + 1 la diferencia es X + 1 – C X + 1 que es mayor 
o igual que la diferencia X – C X para el número X, es decir (X + 1 – C X + 1 ) ≥ ( X – C X ). 
Así, si (X – C X ) ≥ S, entonces (X + 1 – CX + 1) ≥ S. 
 

Por lo tanto, podemos usar la búsqueda binaria para encontrar el número mínimo válido X y todos los números de X a N serán números válidos. Entonces, la respuesta sería N – X + 1 .
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1000001;
 
// primeUpto[i] denotes count of prime
// numbers upto i
int primeUpto[MAX];
 
// Function to compute all prime numbers
// and update primeUpto array
void SieveOfEratosthenes()
{
    bool isPrime[MAX];
    memset(isPrime, 1, sizeof(isPrime));
 
    // 0 and 1 are not primes
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i * i < MAX; i++) {
 
        // If i is prime
        if (isPrime[i]) {
 
            // Set all multiples of i as non-prime
            for (int j = i * 2; j < MAX; j += i)
                isPrime[j] = 0;
        }
    }
 
    // Compute primeUpto array
    for (int i = 1; i < MAX; i++) {
        primeUpto[i] = primeUpto[i - 1];
        if (isPrime[i])
            primeUpto[i]++;
    }
}
 
// Function to return the count
// of valid numbers
int countOfNumbers(int N, int K)
{
 
    // Compute primeUpto array
    SieveOfEratosthenes();
    int low = 1, high = N, ans = 0;
    while (low <= high) {
        int mid = (low + high) >> 1;
 
        // Check if the number is
        // valid, try to reduce it
        if (mid - primeUpto[mid] >= K) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
 
    // ans is the minimum valid number
    return (ans ? N - ans + 1 : 0);
}
 
// Driver Code
int main()
{
    int N = 10, K = 3;
    cout << countOfNumbers(N, K);
}

Java

// Java implementation of the above approach
 
public class GFG{
 
 
    static final int MAX = 1000001;
     
    // primeUpto[i] denotes count of prime
    // numbers upto i
    static int primeUpto[] = new int [MAX];
     
    // Function to compute all prime numbers
    // and update primeUpto array
    static void SieveOfEratosthenes()
    {
        int isPrime[] = new int[MAX];
        for (int i=0; i < MAX ; i++ )
            isPrime[i] = 1;
 
        // 0 and 1 are not primes
        isPrime[0] = isPrime[1] = 0;
        for (int i = 2; i * i < MAX; i++) {
     
            // If i is prime
            if (isPrime[i] == 1) {
     
                // Set all multiples of i as non-prime
                for (int j = i * 2; j < MAX; j += i)
                    isPrime[j] = 0;
            }
        }
     
        // Compute primeUpto array
        for (int i = 1; i < MAX; i++) {
            primeUpto[i] = primeUpto[i - 1];
            if (isPrime[i] == 1)
                primeUpto[i]++;
        }
    }
     
    // Function to return the count
    // of valid numbers
    static int countOfNumbers(int N, int K)
    {
     
        // Compute primeUpto array
        SieveOfEratosthenes();
        int low = 1, high = N, ans = 0;
        while (low <= high) {
            int mid = (low + high) >> 1;
     
            // Check if the number is
            // valid, try to reduce it
            if (mid - primeUpto[mid] >= K) {
                ans = mid;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
     
        ans = ans != 0 ? N - ans + 1 : 0 ;
        // ans is the minimum valid number
        return ans ;
    }
     
    // Driver Code
     public static void main(String []args)
    {
        int N = 10, K = 3;
        System.out.println(countOfNumbers(N, K)) ;
    }
    // This code is contributed by Ryuga
}

Python3

# Python3 implementation of the above approach
 
MAX = 1000001
MAX_sqrt = MAX ** (0.5)
   
# primeUpto[i] denotes count of prime
# numbers upto i
primeUpto = [0] * (MAX)
   
# Function to compute all prime numbers
# and update primeUpto array
def SieveOfEratosthenes():
  
    isPrime = [1] * (MAX)
     
    # 0 and 1 are not primes
    isPrime[0], isPrime[1] = 0, 0
    for i in range(2, int(MAX_sqrt)): 
   
        # If i is prime
        if isPrime[i] == 1:
   
            # Set all multiples of i as non-prime
            for j in range(i * 2, MAX, i):
                isPrime[j] = 0
   
    # Compute primeUpto array
    for i in range(1, MAX):
        primeUpto[i] = primeUpto[i - 1]
        if isPrime[i] == 1:
            primeUpto[i] += 1
  
   
# Function to return the count
# of valid numbers
def countOfNumbers(N, K):
   
    # Compute primeUpto array
    SieveOfEratosthenes()
    low, high, ans = 1, N, 0
    while low <= high: 
        mid = (low + high) >> 1
   
        # Check if the number is
        # valid, try to reduce it
        if mid - primeUpto[mid] >= K: 
            ans = mid
            high = mid - 1
          
        else:
            low = mid + 1
   
    # ans is the minimum valid number
    return (N - ans + 1) if ans else 0
  
   
# Driver Code
if __name__ == "__main__":
  
    N, K = 10, 3 
    print(countOfNumbers(N, K))
  
 # This code is contributed by Rituraj Jain

C#

// C# implementation of the above approach
using System;
 
public class GFG{
 
 
    static  int MAX = 1000001;
     
    // primeUpto[i] denotes count of prime
    // numbers upto i
    static int []primeUpto = new int [MAX];
     
    // Function to compute all prime numbers
    // and update primeUpto array
    static void SieveOfEratosthenes()
    {
        int []isPrime = new int[MAX];
        for (int i=0; i < MAX ; i++ )
            isPrime[i] = 1;
 
        // 0 and 1 are not primes
        isPrime[0] = isPrime[1] = 0;
        for (int i = 2; i * i < MAX; i++) {
     
            // If i is prime
            if (isPrime[i] == 1) {
     
                // Set all multiples of i as non-prime
                for (int j = i * 2; j < MAX; j += i)
                    isPrime[j] = 0;
            }
        }
     
        // Compute primeUpto array
        for (int i = 1; i < MAX; i++) {
            primeUpto[i] = primeUpto[i - 1];
            if (isPrime[i] == 1)
                primeUpto[i]++;
        }
    }
     
    // Function to return the count
    // of valid numbers
    static int countOfNumbers(int N, int K)
    {
     
        // Compute primeUpto array
        SieveOfEratosthenes();
        int low = 1, high = N, ans = 0;
        while (low <= high) {
            int mid = (low + high) >> 1;
     
            // Check if the number is
            // valid, try to reduce it
            if (mid - primeUpto[mid] >= K) {
                ans = mid;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
     
        ans = ans != 0 ? N - ans + 1 : 0 ;
        // ans is the minimum valid number
        return ans ;
    }
     
    // Driver Code
    public static void Main()
    {
        int N = 10, K = 3;
        Console.WriteLine(countOfNumbers(N, K)) ;
    }
    // This code is contributed by anuj_67..
}

PHP

<?php
// PHP implementation of the above approach
 
$MAX = 100001;
 
// primeUpto[i] denotes count of
// prime numbers upto i
$primeUpto = array_fill(0, $MAX, 0);
 
// Function to compute all prime numbers
// and update primeUpto array
function SieveOfEratosthenes()
{
    global $MAX,$primeUpto;
    $isPrime = array_fill(0, $MAX, true);
 
    // 0 and 1 are not primes
    $isPrime[0] = $isPrime[1] = false;
    for ($i = 2; $i * $i < $MAX; $i++)
    {
 
        // If i is prime
        if ($isPrime[$i])
        {
 
            // Set all multiples of i as non-prime
            for ($j = $i * 2; $j < $MAX; $j += $i)
                $isPrime[$j] = false;
        }
    }
 
    // Compute primeUpto array
    for ($i = 1; $i < $MAX; $i++)
    {
        $primeUpto[$i] = $primeUpto[$i - 1];
        if ($isPrime[$i])
            $primeUpto[$i]++;
    }
}
 
// Function to return the count
// of valid numbers
function countOfNumbers($N, $K)
{
 
    // Compute primeUpto array
    SieveOfEratosthenes();
    global $primeUpto;
    $low = 1;
    $high = $N;
    $ans = 0;
    while ($low <= $high)
    {
        $mid = ($low + $high) >> 1;
 
        // Check if the number is
        // valid, try to reduce it
        if ($mid - $primeUpto[$mid] >= $K)
        {
            $ans = $mid;
            $high = $mid - 1;
        }
        else
            $low = $mid + 1;
    }
 
    // ans is the minimum valid number
    return ($ans ? $N - $ans + 1 : 0);
}
 
// Driver Code
$N = 10;
$K = 3;
echo countOfNumbers($N, $K);
     
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation of the above approach
 
var MAX = 1000001;
 
// primeUpto[i] denotes count of prime
// numbers upto i
var primeUpto = Array(MAX).fill(0);
 
// Function to compute all prime numbers
// and update primeUpto array
function SieveOfEratosthenes()
{
    var isPrime = Array(MAX).fill(1);
 
    // 0 and 1 are not primes
    isPrime[0] = isPrime[1] = 0;
    for (var i = 2; i * i < MAX; i++) {
 
        // If i is prime
        if (isPrime[i]) {
 
            // Set all multiples of i as non-prime
            for (var j = i * 2; j < MAX; j += i)
                isPrime[j] = 0;
        }
    }
 
    // Compute primeUpto array
    for (var i = 1; i < MAX; i++) {
        primeUpto[i] = primeUpto[i - 1];
        if (isPrime[i])
            primeUpto[i]++;
    }
}
 
// Function to return the count
// of valid numbers
function countOfNumbers(N, K)
{
 
    // Compute primeUpto array
    SieveOfEratosthenes();
    var low = 1, high = N, ans = 0;
    while (low <= high) {
        var mid = (low + high) >> 1;
 
        // Check if the number is
        // valid, try to reduce it
        if (mid - primeUpto[mid] >= K) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
 
    // ans is the minimum valid number
    return (ans ? N - ans + 1 : 0);
}
 
// Driver Code
var N = 10, K = 3;
document.write( countOfNumbers(N, K));
 
 
</script>
Producción: 

5

 

Complejidad del tiempo: O(MAX*log(log(MAX)))

Espacio Auxiliar: O(MAX)

Publicación traducida automáticamente

Artículo escrito por Nishant Tanwar 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 *