Highest power of a number that divides other number | Python program to implement the above approach ; Function to get the prime factors and its count of times it divides ; Count the number of 2 s that divide n ; n must be odd at this point . So we can skip one element ( Note i = i + 2 ) ; While i divides n , count i and divide n ; This condition is to handle the case when n is a prime number greater than 2 ; Function to return the highest power ; Initialize two arrays ; Get the prime factors of n and m ; Iterate and find the maximum power ; If i not a prime factor of n and m ; If i is a prime factor of n and m If count of i dividing m is more than i dividing n , then power will be 0 ; If i is a prime factor of M ; get the maximum power ; Drivers code
import math NEW_LINE def primeFactors ( n , freq ) : NEW_LINE INDENT cnt = 0 NEW_LINE while n % 2 == 0 : NEW_LINE INDENT cnt = cnt + 1 NEW_LINE n = int ( n // 2 ) NEW_LINE DEDENT freq [ 2 ] = cnt NEW_LINE i = 3 NEW_LINE while i <= math . sqrt ( n ) : NEW_LINE INDENT cnt = 0 NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT cnt = cnt + 1 NEW_LINE n = int ( n // i ) NEW_LINE DEDENT freq [ int ( i ) ] = cnt NEW_LINE i = i + 2 NEW_LINE DEDENT if ( n > 2 ) : NEW_LINE INDENT freq [ int ( n ) ] = 1 NEW_LINE DEDENT DEDENT def getMaximumPower ( n , m ) : NEW_LINE INDENT freq1 = [ 0 ] * ( n + 1 ) NEW_LINE freq2 = [ 0 ] * ( m + 1 ) NEW_LINE primeFactors ( n , freq1 ) NEW_LINE primeFactors ( m , freq2 ) NEW_LINE maxi = 0 NEW_LINE i = 2 NEW_LINE while i <= m : NEW_LINE INDENT if ( freq1 [ i ] == 0 and freq2 [ i ] == 0 ) : NEW_LINE INDENT i = i + 1 NEW_LINE continue NEW_LINE DEDENT if ( freq2 [ i ] > freq1 [ i ] ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( freq2 [ i ] ) : NEW_LINE INDENT maxi = max ( maxi , int ( freq1 [ i ] // freq2 [ i ] ) ) NEW_LINE DEDENT i = i + 1 NEW_LINE DEDENT return maxi NEW_LINE DEDENT n = 48 NEW_LINE m = 4 NEW_LINE print ( getMaximumPower ( n , m ) ) NEW_LINE