Largest integer upto N having greatest prime factor greater than its square root | Java 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
public class GFG { final static int maxn = 100001 ; static int gpf [ ] = new int [ maxn ] ; static void modifiedSieve ( ) { for ( int i = 0 ; i < maxn ; i ++ ) gpf [ i ] = 0 ; gpf [ 0 ] = 0 ; gpf [ 1 ] = 1 ; for ( int i = 2 ; i < maxn ; i ++ ) { if ( gpf [ i ] > 0 ) continue ; for ( int j = i ; j < maxn ; j += i ) { gpf [ j ] = Math . max ( i , gpf [ j ] ) ; } } } static int greatestValidInt ( int N ) { modifiedSieve ( ) ; for ( int i = N ; i > 0 ; i -- ) { if ( gpf [ i ] > Math . sqrt ( i ) ) { return i ; } } return - 1 ; } public static void main ( String [ ] args ) { int N = 25 ; System . out . println ( greatestValidInt ( N ) ) ; } }