Largest integer upto N having greatest prime factor greater than its square root | python program for the above approach ; Stores the Greatest Prime Factor ; Modified Sieve to find the Greatest Prime Factor of all integers in the range [ 1 , maxn ] ; Initialize the array with 0 ; Iterate through all values of i ; If i is not a prime number ; Update the multiples of i ; Function to find integer in the range [ 1 , N ] such that its Greatest Prime factor is greater than its square root ; Iterate through all values of i in the range [ N , 1 ] ; If greatest prime factor of i is greater than its sqare root ; Return answer ; If no valid integer exist ; Driver Code
import math NEW_LINE maxn = 100001 NEW_LINE gpf = [ 0 for _ in range ( maxn ) ] NEW_LINE def modifiedSieve ( ) : NEW_LINE INDENT gpf [ 0 ] = 0 NEW_LINE gpf [ 1 ] = 1 NEW_LINE for i in range ( 2 , maxn ) : NEW_LINE INDENT if ( gpf [ i ] > 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for j in range ( i , maxn , i ) : NEW_LINE INDENT gpf [ j ] = max ( i , gpf [ j ] ) NEW_LINE DEDENT DEDENT DEDENT def greatestValidInt ( N ) : NEW_LINE INDENT modifiedSieve ( ) NEW_LINE for i in range ( N , 0 , - 1 ) : NEW_LINE INDENT if ( gpf [ i ] > math . sqrt ( i ) ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 25 NEW_LINE print ( greatestValidInt ( N ) ) NEW_LINE DEDENT