Given two positive integers N and K, the task is to count all the numbers that satisfy the following conditions:
If the number is num,
- num ? N.
- abs(num – count) ? K where count is the count of primes upto num.
Examples:
Input: N = 10, K = 3
Output: 5
6, 7, 8, 9 and 10 are the valid numbers. For 6, the difference between 6 and prime numbers upto 6 (2, 3, 5) is 3 i.e. 6 – 3 = 3. For 7, 8, 9 and 10 the differences are 3, 4, 5 and 6 respectively which are ? K.
Input: N = 30, K = 13
Output: 10
Prerequisite: Binary Search
Approach: Observe that the function which is the difference of the number and count of prime numbers upto that number is a monotonically increasing function for a particular K. Also, if a number X is a valid number then X + 1 will also be a valid number.
Proof :
Let the function Ci denotes the count of prime numbers upto number i. Now,
for the number X + 1 the difference is X + 1 – CX + 1 which is greater than
or equal to the difference X – CX for the number X, i.e. (X + 1 – CX + 1) ? (X – CX).
Thus, if (X – CX) ? S, then (X + 1 – CX + 1) ? S.
Hence, we can use binary search to find the minimum valid number X and all the numbers from X to N will be valid numbers. So, the answer would be N – X + 1.
Below is the implementation of the above approach:
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 iint primeUpto[MAX];// Function to compute all prime numbers// and update primeUpto arrayvoid 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 numbersint 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 Codeint 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 = 1000001MAX_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 approachvar MAX = 1000001;// primeUpto[i] denotes count of prime// numbers upto ivar primeUpto = Array(MAX).fill(0);// Function to compute all prime numbers// and update primeUpto arrayfunction 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 numbersfunction 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 Codevar N = 10, K = 3;document.write( countOfNumbers(N, K));</script> |
Output:
5
Time Complexity: O(MAX*log(log(MAX)))
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
