Path Through Graph
Problem Description
Constraints
0 < M, N <= 10 ^ 9
Input
Single line containing two space separated integers M, N
Output
Number of edges in the shortest path.
Time Limit
1
Examples
Example 1
Input
15689 28
Output
5
Explanation :
The graph for number 15689 and 28 will look like this.
Since we know that largest factor of 15689 other than itself is 541.
Since 541 is a prime number, it’s largest factor other than itself is 1.
For number 28, it’s largest factor other than itself is 14.
Largest factor of 14, other than itself is 7.
Since 7 is a prime number, it’s largest factor other than itself is 1.
So, the graph will look like this:
15689 <–> 541 <–> 1 <–> 7 <–> 14 <–> 28
Since there are 5 edges in this graph, output will be 5.
Example 2
Input
16 4
Output
2
Explanation :
The graph for number 16 and 4 will look like this.
Since we know that largest factor of 16 other than itself is 8.
Largest factor of 8 other than itself is 4. That’s the other input number, so we will stop here.
So, the graph will look like this:
16<–>8<–>4
Since there are 2 edges in this graph, output will be 2.
[sg_popup id=”743″ event=”onLoad”][/sg_popup]
