Largest divisor of a number not divisible by another given number | Java program to implement the above approach ; Function to find the largest number X such that it divides P but is not divisible by Q ; Stores the frequency count of of all Prime Factors ; Increment the frequency of the current prime factor ; If Q is a prime factor ; Stores the desired result ; Iterate through all divisors of Q ; Stores the frequency count of current prime divisor on dividing P ; Count the frequency of the current prime factor ; If cur is less than frequency then P is the final result ; Iterate to get temporary answer ; Update current answer ; Print the desired result ; Driver Code ; Given P and Q ; Function Call
import java . util . * ; class GFG { static void findTheGreatestX ( int P , int Q ) { HashMap < Integer , Integer > divisiors = new HashMap < > ( ) ; for ( int i = 2 ; i * i <= Q ; i ++ ) { while ( Q % i == 0 && Q > 1 ) { Q /= i ; if ( divisiors . containsKey ( i ) ) { divisiors . put ( i , divisiors . get ( i ) + 1 ) ; } else { divisiors . put ( i , 1 ) ; } } } if ( Q > 1 ) if ( divisiors . containsKey ( Q ) ) { divisiors . put ( Q , divisiors . get ( Q ) + 1 ) ; } else { divisiors . put ( Q , 1 ) ; } int ans = 0 ; for ( Map . Entry < Integer , Integer > i : divisiors . entrySet ( ) ) { int frequency = i . getValue ( ) ; int temp = P ; int cur = 0 ; while ( temp % i . getKey ( ) == 0 ) { temp /= i . getKey ( ) ; cur ++ ; } if ( cur < frequency ) { ans = P ; break ; } temp = P ; for ( int j = cur ; j >= frequency ; j -- ) { temp /= i . getKey ( ) ; } ans = Math . max ( temp , ans ) ; } System . out . print ( ans ) ; } public static void main ( String [ ] args ) { int P = 10 , Q = 4 ; findTheGreatestX ( P , Q ) ; } }