Highest power of a number that divides other number | 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 ;  ; 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
< ? php function primeFactors ( $ n , $ freq ) { $ cnt = 0 ; while ( $ n % 2 == 0 ) { $ cnt ++ ; $ n = floor ( $ n / 2 ) ; } $ freq [ 2 ] = $ cnt ; for ( $ i = 3 ; $ i <= sqrt ( $ n ) ; $ i = $ i + 2 ) { $ cnt = 0 ; while ( $ n % $ i == 0 ) { $ cnt ++ ; $ n = floor ( $ n / $ i ) ; } $ freq [ $ i ] = $ cnt ; } if ( $ n > 2 ) $ freq [ $ n ] = 1 ; return $ freq ; } function getMaximumPower ( $ n , $ m ) { ' ' ' Initialize two arrays ' ' ' $ freq1 = array_fill ( 0 , $ n + 1 , 0 ) ; $ freq2 = array_fill ( 0 , $ m + 1 , 0 ) ; $ freq1 = primeFactors ( $ n , $ freq1 ) ; $ freq2 = primeFactors ( $ m , $ freq2 ) ; $ maxi = 0 ; for ( $ i = 2 ; $ i <= $ m ; $ i ++ ) { if ( $ freq1 [ $ i ] == 0 && $ freq2 [ $ i ] == 0 ) continue ; if ( $ freq2 [ $ i ] > $ freq1 [ $ i ] ) return 0 ; if ( $ freq2 [ $ i ] ) { $ maxi = max ( $ maxi , floor ( $ freq1 [ $ i ] / $ freq2 [ $ i ] ) ) ; } } return $ maxi ; } $ n = 48 ; $ m = 4 ; echo getMaximumPower ( $ n , $ m ) ; ? >