Nearest prime less than given number n | Python3 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
import math NEW_LINE MAX = 10000 ; NEW_LINE primes = [ ] ; NEW_LINE def Sieve ( ) : NEW_LINE INDENT n = MAX ; NEW_LINE nNew = int ( math . sqrt ( n ) ) ; NEW_LINE marked = [ 0 ] * ( int ( n / 2 + 500 ) ) ; NEW_LINE for i in range ( 1 , int ( ( nNew - 1 ) / 2 ) + 1 ) : NEW_LINE INDENT for j in range ( ( ( i * ( i + 1 ) ) << 1 ) , ( int ( n / 2 ) + 1 ) , ( 2 * i + 1 ) ) : NEW_LINE INDENT marked [ j ] = 1 ; NEW_LINE DEDENT DEDENT primes . append ( 2 ) ; NEW_LINE for i in range ( 1 , int ( n / 2 ) + 1 ) : NEW_LINE INDENT if ( marked [ i ] == 0 ) : NEW_LINE INDENT primes . append ( 2 * i + 1 ) ; NEW_LINE DEDENT DEDENT DEDENT def binarySearch ( left , right , n ) : NEW_LINE INDENT if ( left <= right ) : NEW_LINE INDENT mid = int ( ( left + right ) / 2 ) ; NEW_LINE if ( mid == 0 or mid == len ( primes ) - 1 ) : NEW_LINE INDENT return primes [ mid ] ; NEW_LINE DEDENT if ( primes [ mid ] == n ) : NEW_LINE INDENT return primes [ mid - 1 ] ; NEW_LINE DEDENT if ( primes [ mid ] < n and primes [ mid + 1 ] > n ) : NEW_LINE INDENT return primes [ mid ] ; NEW_LINE DEDENT if ( n < primes [ mid ] ) : NEW_LINE INDENT return binarySearch ( left , mid - 1 , n ) ; NEW_LINE DEDENT else : NEW_LINE INDENT return binarySearch ( mid + 1 , right , n ) ; NEW_LINE DEDENT DEDENT return 0 ; NEW_LINE DEDENT Sieve ( ) ; NEW_LINE n = 17 ; NEW_LINE print ( binarySearch ( 0 , len ( primes ) - 1 , n ) ) ; NEW_LINE