Nearest prime less than given number n | Java 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 mean we reached at nearest prime ; Driver code
import java . util . * ; class GFG { static int MAX = 1000000 ; static ArrayList < Integer > primes = new ArrayList < Integer > ( ) ; static void Sieve ( ) { int n = MAX ; int nNew = ( int ) Math . sqrt ( n ) ; int [ ] marked = new int [ n / 2 + 500 ] ; for ( int i = 1 ; i <= ( nNew - 1 ) / 2 ; i ++ ) for ( int j = ( i * ( i + 1 ) ) << 1 ; j <= n / 2 ; j = j + 2 * i + 1 ) marked [ j ] = 1 ; primes . add ( 2 ) ; for ( int i = 1 ; i <= n / 2 ; i ++ ) if ( marked [ i ] == 0 ) primes . add ( 2 * i + 1 ) ; } static int binarySearch ( int left , int right , int n ) { if ( left <= right ) { int mid = ( left + right ) / 2 ; if ( mid == 0 || mid == primes . size ( ) - 1 ) return primes . get ( mid ) ; if ( primes . get ( mid ) == n ) return primes . get ( mid - 1 ) ; if ( primes . get ( mid ) < n && primes . get ( mid + 1 ) > n ) return primes . get ( mid ) ; if ( n < primes . get ( mid ) ) return binarySearch ( left , mid - 1 , n ) ; else return binarySearch ( mid + 1 , right , n ) ; } return 0 ; } public static void main ( String [ ] args ) { Sieve ( ) ; int n = 17 ; System . out . println ( binarySearch ( 0 , primes . size ( ) - 1 , n ) ) ; } }