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