Highest power of a number that divides other number | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void primeFactors ( int n , int freq [ ] ) { int cnt = 0 ; while ( n % 2 == 0 ) { cnt ++ ; n = n / 2 ; } freq [ 2 ] = cnt ; for ( int i = 3 ; i <= sqrt ( n ) ; i = i + 2 ) { cnt = 0 ; while ( n % i == 0 ) { cnt ++ ; n = n / i ; } freq [ i ] = cnt ; } if ( n > 2 ) freq [ n ] = 1 ; } int getMaximumPower ( int n , int m ) { int freq1 [ n + 1 ] , freq2 [ m + 1 ] ; memset ( freq1 , 0 , sizeof freq1 ) ; memset ( freq2 , 0 , sizeof freq2 ) ; primeFactors ( n , freq1 ) ; primeFactors ( m , freq2 ) ; int maxi = 0 ; for ( int 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 , freq1 [ i ] / freq2 [ i ] ) ; } } return maxi ; } int main ( ) { int n = 48 , m = 4 ; cout << getMaximumPower ( n , m ) ; return 0 ; }