Make two numbers equal in at most Ok steps dividing by their issue

Given integers X, Y, and Ok, the duty is to make X and Y equal in no more than Ok operations by making use of the next operations:

• Select an integer A and make X = X/A, (the place A is an integer that’s higher than 1 and never equal to X).
• Select an integer A and make Y = Y/A, (the place A is an integer that’s higher than 1 and never equal to Y).

Examples:

Enter: X = 10, Y = 20, Ok = 4
Output: YES
Rationalization: One optimum answer to make them equal is:
First select A = 2 and do X = X/2 so now X is the same as 5.
Now select A = 4 and do Y = Y/4 so now Y is the same as 5.
Since we’ve got utilized solely two operations right here which is lower than Ok 
to make X and Y equal and in addition higher than one.
Due to this fact the reply is YES.

Enter: X = 2, Y = 27, Ok = 1
Output: NO
Rationalization: There isn’t any attainable approach to make X and Y equal 
in lower than or equal to 1 Operation.

Method: To resolve the issue observe the beneath thought:

Listed below are solely two instances attainable:

• When Ok is the same as one and 
• When Ok is larger than 1

If Ok is the same as one then it’s attainable to make X and Y equal solely when both X is divisible by Y or Y is divisible by X

If Ok is larger than 1 then X and Y could be equal and higher than 1 solely when their GCD is larger than 1.

Observe the steps talked about beneath to implement the thought:

• Verify if Ok = 1:
  • In that case, discover out if any of them is a divisor of the opposite.
• In any other case, discover the GCD of the numbers.
  • If the GCD is 1 then it’s not attainable.
  • In any other case, a solution all the time exists.

Under is the implementation for the above strategy:

Time Complexity: O(1)
Auxiliary House: O(1)