Queries for the smallest and the largest prime number of given digit | Python3 implementation of the approach ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it numbers which are multiple of p and are less than p ^ 2 are already been marked . ; Function to return the smallest prime number with d digits ; check if prime ; Function to return the largest prime number with d digits ; check if prime ; Driver code ; Perform queries
from math import sqrt NEW_LINE MAX = 100000 NEW_LINE prime = [ True ] * ( MAX + 1 ) NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT for p in range ( 2 , int ( sqrt ( MAX ) ) + 1 ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , MAX + 1 , p ) : NEW_LINE INDENT prime [ i ] = False ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def smallestPrime ( d ) : NEW_LINE INDENT l = 10 ** ( d - 1 ) ; NEW_LINE r = ( 10 ** d ) - 1 ; NEW_LINE for i in range ( l , r + 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT return i ; NEW_LINE DEDENT DEDENT return - 1 ; NEW_LINE DEDENT def largestPrime ( d ) : NEW_LINE INDENT l = 10 ** ( d - 1 ) ; NEW_LINE r = ( 10 ** d ) - 1 ; NEW_LINE for i in range ( r , l , - 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT return i ; NEW_LINE DEDENT DEDENT return - 1 ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT SieveOfEratosthenes ( ) ; NEW_LINE queries = [ 2 , 5 ] ; NEW_LINE q = len ( queries ) ; NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( smallestPrime ( queries [ i ] ) , " ▁ " , largestPrime ( queries [ i ] ) ) ; NEW_LINE DEDENT DEDENT