Nearest prime less than given number n | PHP program to find the nearest prime to n . ; array to store all primes less than 10 ^ 6 ; Utility function of Sieve of Sundaram ; In general Sieve of Sundaram , produces primes smaller than ( 2 * x + 2 ) for a number given number x ; This array is used to separate numbers of the form i + j + 2 ij from others where 1 <= i <= j ; eliminate indexes which does not produce primes ; Since 2 is a prime number ; Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; modified binary search to find nearest prime less than N ; base condition is , if we are reaching at left corner or right corner of primes [ ] array then return that corner element because before or after that we don 't have any prime number in  primes array ; now if n is itself a prime so it will be present in primes array and here we have to find nearest prime less than n so we will return primes [ mid - 1 ] ; now if primes [ mid ] < n and primes [ mid + 1 ] > n that means we reached at nearest prime ; Driver Code
< ? php $ MAX = 10000 ; $ primes = array ( ) ; function Sieve ( ) { global $ MAX , $ primes ; $ n = $ MAX ; $ nNew = ( int ) ( sqrt ( $ n ) ) ; $ marked = array_fill ( 0 , ( int ) ( $ n / 2 + 500 ) , 0 ) ; for ( $ i = 1 ; $ i <= ( $ nNew - 1 ) / 2 ; $ i ++ ) for ( $ j = ( $ i * ( $ i + 1 ) ) << 1 ; $ j <= $ n / 2 ; $ j = $ j + 2 * $ i + 1 ) $ marked [ $ j ] = 1 ; array_push ( $ primes , 2 ) ; for ( $ i = 1 ; $ i <= $ n / 2 ; $ i ++ ) if ( $ marked [ $ i ] == 0 ) array_push ( $ primes , 2 * $ i + 1 ) ; } function binarySearch ( $ left , $ right , $ n ) { global $ primes ; if ( $ left <= $ right ) { $ mid = ( int ) ( ( $ left + $ right ) / 2 ) ; if ( $ mid == 0 || $ mid == count ( $ primes ) - 1 ) return $ primes [ $ mid ] ; if ( $ primes [ $ mid ] == $ n ) return $ primes [ $ mid - 1 ] ; if ( $ primes [ $ mid ] < $ n && $ primes [ $ mid + 1 ] > $ n ) return $ primes [ $ mid ] ; if ( $ n < $ primes [ $ mid ] ) return binarySearch ( $ left , $ mid - 1 , $ n ) ; else return binarySearch ( $ mid + 1 , $ right , $ n ) ; } return 0 ; } Sieve ( ) ; $ n = 17 ; echo binarySearch ( 0 , count ( $ primes ) - 1 , $ n ) ; ? >