text: Nearest prime less than given number n | C ++ 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 program to run the case
code: #include <bits/stdc++.h> NEW_LINE #define MAX  1000000 NEW_LINE using namespace std ; vector < int > primes ; void Sieve ( ) { int n = MAX ; int nNew = sqrt ( n ) ; int marked [ n / 2 + 500 ] = { 0 } ; 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 . push_back ( 2 ) ; for ( int i = 1 ; i <= n / 2 ; i ++ ) if ( marked [ i ] == 0 ) primes . push_back ( 2 * i + 1 ) ; } 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 [ 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 ; } int main ( ) { Sieve ( ) ; int n = 17 ; cout << binarySearch ( 0 , primes . size ( ) - 1 , n ) ; return 0 ; }