1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudo code
3.
Implementation in C++
3.1.
Complexity Analysis
4.
5.
Key takeaways
Last Updated: Mar 27, 2024

# Make two numbers equal by multiplying with their prime factors the minimum number of times

Ayush Tiwari
0 upvote

## Introduction

This blog finds the minimum number of operations needed to make two numbers equal by multiplying with their prime factors.

### Problem Statement

The problem states that given two positive integers ‘a’ and ‘b’, We have to make both ‘a’ and ‘b’ equal in the minimum number of operations.

In one operation:-

1. Take any one of the given integers, let say ‘a’.
2. Choose any prime factor of a, let say ‘x’.
3. Update ‘a’ with a*x i.e a=a*x.

We have to find a minimum number of operations needed to make two numbers equal. If we cannot make both integers equal then print -1.

Let's take some examples to understand this problem better.

### Sample Examples

Example 1:

``````Given Integers: a = 150, b = 180
Output - 3``````

Explanation:

Operation 1-  Select integer ‘a’ and multiply with 3(because 3 is the prime factor of a) then a*3= 450 and b=180

Operation 2- Select integer ‘a’ and multiply with 2(because 2 is the prime factor of a) then a*2= 900 and b=180

Operation 3- Select integer ‘b’ and multiply with 5(because 5 is the prime factor of b) then a = 900 and b*5=900

Example 2:

``````Given Integer: a=10, b=15
Output - 1``````

Explanation:

We cannot make both a and b equal because, in the prime factor of a = 2*5 and b=3*5, we cannot bring 3 in ‘a’ by multiplying with its own prime factor.

Also see, Euclid GCD Algorithm

## Approach

In this problem, we have to find the minimum number of operations needed to make two numbers equal by multiplying with their prime factors. If it is not possible then print -1.

First, we have to check it is possible to make ‘a’ and ‘b’ equal or not. ’a’ and ‘b’ is written as:

``````a =p1^a1*p2^a2*p3^a3.......*pn^an
b =q1^b1*q2^b2*q3^b3.......*qm^bm
Where p1,p2,p3…pn are prime factors of ‘a’ and q1,q2,q3,....qm are prime factors of ‘b’.``````

If any pi prime factors of ‘a’ are not present in the prime factors of ‘b’ or any qi prime factors of ‘b’ are not present in the prime factors of ‘a’ then we cannot make ‘a’ and ‘b’ equal because we cannot bring that factor by multiplying with their own prime factors.

If every prime factor of ‘a’ is present in ‘b’ and every prime factor of ‘b’ is present in ‘a’ then the answer will be the sum of absolute difference in the count of prime factors in ‘a’ and ‘b’.

If p1 < p2 < p3.....< pn and q1 < q2 < q3....< qm, where n = m because all prime factors of ‘a’ present in ‘b’ and all prime factors of ‘b’ present in ‘a’.

ans = mod(a1-b1)+ mod(a2-b2)+ mod(a3-b3).....+ mod(an-bn)

### Pseudo code

``````// Make two numbers equal by multiplying with their prime factors
int operations(int a, int b)
int ans =0
Map1 = prime_factor(a); // Map1 stores count of each factor of a
Map2 = prime_factor(b); // Map2 stores count of each factor of b
if -> every prime factor of ‘a’ is not present in ‘b’
return -1
if -> every prime factor of ‘b’ is not present in ‘a’
return -1;
loop(every factor of ‘a’)
ans = ans + mod(Map1.count(factor)-Map2.count(factor))
return ans;``````

## Implementation in C++

``````//code make two numbers equal by multiplying with their prime factors
#include <bits/stdc++.h>
using namespace std;
// function to find prime factors
void prime_factors(int number, map<int, int> &map)
{
// run a loop from 2 to sqrt(number)
for (int i = 2; i * i <= number; i++)
{
while (number % i == 0)
{
map[i]++;
number = number / i;
}
}
if (number > 1)
map[number]++;
}
int count_operations(int a, int b)
{
int ans = 0;
// map1 stores all prime factors of 'a' and map2 stores the prime factors of 'b'
map<int, int> map1, map2;
prime_factors(a, map1);
prime_factors(b, map2);

// check every prime factor of ‘a’ is present in ‘b' or not
for (auto factor : map1)
{
if (map2.count(factor.first) == 0) // factor not present in b
return -1;
}

// check every prime factor of ‘b’ is present in ‘a' or not
for (auto factor : map2)
{
if (map1.count(factor.first) == 0) // factor not present in a
return -1;
}

for (auto factor : map1)
ans += abs(map1[factor.first] - map2[factor.first]);
return ans;
}
// driver function
int main()
{
int a, b;
cin >> a >> b;
int ans = count_operations(a, b);
cout << ans;
}``````

Input:

``a = 90, b = 750``

Output:

``3``

### Complexity Analysis

Time complexityO(sqrt(max(a,b))), for finding prime factors n it takes O(sqrt(n)) .

Space complexity - O(N). where N is max(number of prime factors of a , number of prime factors of b)

1. How do we find the number of divisors of a given number with the help of prime factors?
Ans-. Let say we have the number n=p1a1*p2a2*p3a3.......pnan where, p1,p2,p3... pn  is prime factors of n then a number of divisors are (a1+1)*(a2+1)*(a3+1)....*(an+1).

2. How do we find the sum of divisors of a given number with the help of prime factors?
Ans- Let say we have the number n=p1a1*p2a2*p3a3.......pnan  where, p1,p2,p3... pn  is prime factors of n then sum of divisors is:(p1a1+1-1)/(a1-1)*(p2a2+1-1)/(a2-1)*(p3a3+1-1)/(a3-1)....*(pnan+1-1)/(an-1)

3. What is the difference between map and unordered_map in c++?
Ans- Map (like set) is an order of unique keys whereas in unordered_map keys can be stored in random order. The map is implemented as a balanced tree structure that is why it is possible to maintain order between the elements (by specific tree traversal) and unordered_map is based on hashing.

## Key takeaways

In this blog, we find the minimum number of operations needed to make two numbers equal by multiplying with their prime factors. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem.

Recommended Article: abs in C++

You can learn more concepts of number theoryUntil then, Keep practicing, Keep Learning and Keep Coding and practicing in Code studio.

Keep Learning, Keep Going.

Happy Coding!

Live masterclass