Count numbers < = N whose difference with the count of primes upto them is > = K | PHP 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
< ? php $ MAX = 100001 ; $ primeUpto = array_fill ( 0 , $ MAX , 0 ) ; function SieveOfEratosthenes ( ) { global $ MAX , $ primeUpto ; $ isPrime = array_fill ( 0 , $ MAX , true ) ; $ isPrime [ 0 ] = $ isPrime [ 1 ] = false ; for ( $ i = 2 ; $ i * $ i < $ MAX ; $ i ++ ) { if ( $ isPrime [ $ i ] ) { for ( $ j = $ i * 2 ; $ j < $ MAX ; $ j += $ i ) $ isPrime [ $ j ] = false ; } } for ( $ i = 1 ; $ i < $ MAX ; $ i ++ ) { $ primeUpto [ $ i ] = $ primeUpto [ $ i - 1 ] ; if ( $ isPrime [ $ i ] ) $ primeUpto [ $ i ] ++ ; } } function countOfNumbers ( $ N , $ K ) { SieveOfEratosthenes ( ) ; global $ primeUpto ; $ low = 1 ; $ high = $ N ; $ ans = 0 ; while ( $ low <= $ high ) { $ mid = ( $ low + $ high ) >> 1 ; if ( $ mid - $ primeUpto [ $ mid ] >= $ K ) { $ ans = $ mid ; $ high = $ mid - 1 ; } else $ low = $ mid + 1 ; } return ( $ ans ? $ N - $ ans + 1 : 0 ) ; } $ N = 10 ; $ K = 3 ; echo countOfNumbers ( $ N , $ K ) ; ? >