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: using System . Collections . Generic ; using System ; using System . Linq ; class GFG { static void findTheGreatestX ( int P , int Q ) { Dictionary < int , int > divisers = new Dictionary < int , int > ( ) ; for ( int i = 2 ; i * i <= Q ; i ++ ) { while ( Q % i == 0 && Q > 1 ) { Q /= i ; if ( divisers . ContainsKey ( i ) ) divisers [ i ] ++ ; else divisers [ i ] = 1 ; } } if ( Q > 1 ) { if ( divisers . ContainsKey ( Q ) ) divisers [ Q ] ++ ; else divisers [ Q ] = 1 ; } int ans = 0 ; var val = divisers . Keys . ToList ( ) ; foreach ( var key in val ) { int frequency = divisers [ key ] ; int temp = P ; int cur = 0 ; while ( temp % key == 0 ) { temp /= key ; cur ++ ; } if ( cur < frequency ) { ans = P ; break ; } temp = P ; for ( int j = cur ; j >= frequency ; j -- ) { temp /= key ; } ans = Math . Max ( temp , ans ) ; } Console . WriteLine ( ans ) ; } public static void Main ( String [ ] args ) { int P = 10 , Q = 4 ; findTheGreatestX ( P , Q ) ; } }