Largest divisor of a number not divisible by another given number | Python3 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
from collections import defaultdict NEW_LINE def findTheGreatestX ( P , Q ) : NEW_LINE INDENT divisiors = defaultdict ( int ) NEW_LINE i = 2 NEW_LINE while i * i <= Q : NEW_LINE INDENT while ( Q % i == 0 and Q > 1 ) : NEW_LINE INDENT Q //= i NEW_LINE divisiors [ i ] += 1 NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if ( Q > 1 ) : NEW_LINE INDENT divisiors [ Q ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in divisiors : NEW_LINE INDENT frequency = divisiors [ i ] NEW_LINE temp = P NEW_LINE cur = 0 NEW_LINE while ( temp % i == 0 ) : NEW_LINE INDENT temp //= i NEW_LINE cur += 1 NEW_LINE DEDENT if ( cur < frequency ) : NEW_LINE INDENT ans = P NEW_LINE break NEW_LINE DEDENT temp = P NEW_LINE for j in range ( cur , frequency - 1 , - 1 ) : NEW_LINE INDENT temp //= i NEW_LINE DEDENT ans = max ( temp , ans ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT P = 10 NEW_LINE Q = 4 NEW_LINE findTheGreatestX ( P , Q ) NEW_LINE DEDENT