Nearest prime less than given number 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 mean we reached at nearest prime ; Driver program to run the case
var primes = [ ] ; var MAX = 1000000 ; function Sieve ( ) { let n = MAX ; let nNew = parseInt ( Math . sqrt ( n ) ) ; var marked = new Array ( n / 2 + 500 ) . fill ( 0 ) ; for ( let i = 1 ; i <= parseInt ( ( nNew - 1 ) / 2 ) ; i ++ ) for ( let j = ( i * ( i + 1 ) ) << 1 ; j <= parseInt ( n / 2 ) ; j = j + 2 * i + 1 ) marked [ j ] = 1 ; primes . push ( 2 ) ; for ( let i = 1 ; i <= parseInt ( n / 2 ) ; i ++ ) if ( marked [ i ] == 0 ) primes . push ( 2 * i + 1 ) ; } function binarySearch ( left , right , n ) { if ( left <= right ) { let mid = parseInt ( ( left + right ) / 2 ) ; if ( mid == 0 mid == primes . length - 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 ( ) ; let n = 17 ; document . write ( binarySearch ( 0 , primes . length - 1 , n ) ) ;