text: Largest divisor of a number not divisible by another given number | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void findTheGreatestX ( int P , int Q ) { map < int , int > divisiors ; for ( int i = 2 ; i * i <= Q ; i ++ ) { while ( Q % i == 0 and Q > 1 ) { Q /= i ; divisiors [ i ] ++ ; } } if ( Q > 1 ) divisiors [ Q ] ++ ; int ans = 0 ; for ( auto i : divisiors ) { int frequency = i . second ; int temp = P ; int cur = 0 ; while ( temp % i . first == 0 ) { temp /= i . first ; cur ++ ; } if ( cur < frequency ) { ans = P ; break ; } temp = P ; for ( int j = cur ; j >= frequency ; j -- ) { temp /= i . first ; } ans = max ( temp , ans ) ; } cout << ans ; } int main ( ) { int P = 10 , Q = 4 ; findTheGreatestX ( P , Q ) ; return 0 ; }