Largest integer upto N having greatest prime factor greater than its square root | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int maxn = 100001 ; int gpf [ maxn ] ; void modifiedSieve ( ) { memset ( gpf , 0 , sizeof ( gpf ) ) ; 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 ] = max ( i , gpf [ j ] ) ; } } } int greatestValidInt ( int N ) { modifiedSieve ( ) ; for ( int i = N ; i > 0 ; i -- ) { if ( gpf [ i ] > sqrt ( i ) ) { return i ; } } return -1 ; } int main ( ) { int N = 25 ; cout << greatestValidInt ( N ) ; return 0 ; }