Given two integers A and B, the task is to convert A to B with a minimum number of the following operations:
- Multiply A by any prime number.
- Divide A by one of its prime divisors.
Print the minimum number of operations required.
Examples:
Input: A = 10, B = 15
Output: 2
Operation 1: 10 / 2 = 5
Operation 2: 5 * 3 = 15
Input: A = 9, B = 7
Output: 3
Naive Approach: If prime factorization of A = p1q1 * p2q2 * … * pnqn. If we multiply A by some prime then qi for that prime will increase by 1 and if we divide A by one of its prime factors then qi for that prime will decrease by 1. So for a prime p if it occurs qA times in prime factorization of A and qB times in prime factorization of B then we only need to find the sum of |qA – qB| for all the primes to get a minimum number of operations.
Efficient Approach: Eliminate all the common factors of A and B by dividing both A and B by their GCD. If A and B have no common factors then we only need the sum of powers of their prime factors to convert A to B.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// prime factors of a numberint countFactors(int n){ int factors = 0; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; factors += 1; } } if (n != 1) factors++; return factors;}// Function to return the minimum number of// given operations required to convert A to Bint minOperations(int A, int B){ int g = __gcd(A, B); // gcd(A, B); // Eliminate the common // factors of A and B A /= g; B /= g; // Sum of prime factors return countFactors(A) + countFactors(B);}// Driver codeint main(){ int A = 10, B = 15; cout << minOperations(A, B); return 0;} |
Java
// Java implementation of above approachimport java .io.*;class GFG{ // Function to return the count of// prime factors of a numberstatic int countFactors(int n){ int factors = 0; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; factors += 1; } } if (n != 1) factors++; return factors;}static int __gcd(int a, int b){ if (b == 0) return a; return __gcd(b, a % b);}// Function to return the minimum // number of given operations// required to convert A to Bstatic int minOperations(int A, int B){ int g = __gcd(A, B); // gcd(A, B); // Eliminate the common // factors of A and B A /= g; B /= g; // Sum of prime factors return countFactors(A) + countFactors(B);}// Driver codepublic static void main(String[] args){ int A = 10, B = 15; System.out.println(minOperations(A, B));}}// This code is contributed// by Code_Mech |
Python3
# Python3 implementation of above approach # from math lib import sqrt # and gcd functionfrom math import sqrt, gcd# Function to return the count of # prime factors of a number def countFactors(n) : factors = 0; for i in range(2, int(sqrt(n)) + 1) : while (n % i == 0) : n //= i factors += 1 if (n != 1) : factors += 1 return factors # Function to return the minimum number of # given operations required to convert A to B def minOperations(A, B) : g = gcd(A, B) # Eliminate the common # factors of A and B A //= g B //= g # Sum of prime factors return countFactors(A) + countFactors(B) # Driver code if __name__ == "__main__" : A, B = 10, 15 print(minOperations(A, B))# This code is contributed by Ryuga |
C#
// C# implementation of above approachusing System; class GFG{ // Function to return the count of // prime factors of a number static int countFactors(int n) { int factors = 0; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; factors += 1; } } if (n != 1) factors++; return factors; } static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to return the minimum // number of given operations // required to convert A to B static int minOperations(int A, int B) { int g = __gcd(A, B); // gcd(A, B); // Eliminate the common // factors of A and B A /= g; B /= g; // Sum of prime factors return countFactors(A) + countFactors(B); } // Driver code public static void Main() { int A = 10, B = 15; Console.WriteLine(minOperations(A, B)); }}// This code is contributed by // PrinciRaj1992 |
PHP
<?php// PHP implementation of above approach// Function to calculate gcdfunction __gcd($a, $b){ // Everything divides 0 if ($a == 0 || $b == 0) return 0; // base case if ($a == $b) return $a; // a is greater if ($a > $b) return __gcd($a - $b, $b); return __gcd($a, $b - $a);}// Function to return the count of// prime factors of a numberfunction countFactors($n){ $factors = 0; for ($i = 2; $i * $i <= $n; $i++) { while ($n % $i == 0) { $n /= $i; $factors += 1; } } if ($n != 1) $factors++; return $factors;}// Function to return the minimum number of// given operations required to convert A to Bfunction minOperations($A, $B){ $g = __gcd($A, $B); // gcd(A, B); // Eliminate the common // factors of A and B $A /= $g; $B /= $g; // Sum of prime factors return countFactors($A) + countFactors($B);}// Driver code$A = 10; $B = 15;echo minOperations($A, $B);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// javascript implementation of above approach // Function to return the count of // prime factors of a number function countFactors(n) { var factors = 0; for (i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; factors += 1; } } if (n != 1) factors++; return factors; } function __gcd(a , b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to return the minimum // number of given operations // required to convert A to B function minOperations(A , B) { var g = __gcd(A, B); // gcd(A, B); // Eliminate the common // factors of A and B A /= g; B /= g; // Sum of prime factors return countFactors(A) + countFactors(B); } // Driver code var A = 10, B = 15; document.write(minOperations(A, B));// This code contributed by Rajput-Ji </script> |
Output:
2
Time complexity : O(sqrtn*logn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
