# Count numbers < = N whose difference with the count of primes upto them is > = K

• Difficulty Level : Medium
• Last Updated : 26 May, 2021

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:
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 ` `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

 `> 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

 ``

Output:

`5`

My Personal Notes arrow_drop_up
Recommended Articles
Page :
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}