Count numbers < = N whose difference with the count of primes upto them is > = K | Python3 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
MAX = 1000001 NEW_LINE MAX_sqrt = MAX ** ( 0.5 ) NEW_LINE primeUpto = [ 0 ] * ( MAX ) NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT isPrime = [ 1 ] * ( MAX ) NEW_LINE isPrime [ 0 ] , isPrime [ 1 ] = 0 , 0 NEW_LINE for i in range ( 2 , int ( MAX_sqrt ) ) : NEW_LINE INDENT if isPrime [ i ] == 1 : NEW_LINE INDENT for j in range ( i * 2 , MAX , i ) : NEW_LINE INDENT isPrime [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , MAX ) : NEW_LINE INDENT primeUpto [ i ] = primeUpto [ i - 1 ] NEW_LINE if isPrime [ i ] == 1 : NEW_LINE INDENT primeUpto [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT def countOfNumbers ( N , K ) : NEW_LINE INDENT SieveOfEratosthenes ( ) NEW_LINE low , high , ans = 1 , N , 0 NEW_LINE while low <= high : NEW_LINE INDENT mid = ( low + high ) >> 1 NEW_LINE if mid - primeUpto [ mid ] >= K : NEW_LINE INDENT ans = mid NEW_LINE high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return ( N - ans + 1 ) if ans else 0 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N , K = 10 , 3 NEW_LINE print ( countOfNumbers ( N , K ) ) NEW_LINE DEDENT