Home Technology Path Through Graph

Path Through Graph [Codevita 9]

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]

LEAVE A REPLY

Please enter your comment!
Please enter your name here

3 + 6 =

Most Popular

5 Best Wireless Neckband under Rs. 2000 – October 2020

If you are looking for Best Wireless Neckband under 2000, then you are at right place. We have covered all best neckbands...

15 Best Easiest Programming Languages in the World in 2020

A programming language in today’s generation can really ace up one’s skill set and benefit you in the long run. Having said...

Carl Pei – “Thank You OnePlus”

Just with a simple "Thank You" message , Carl Pei on Friday left OnePlus. He was the Man behind the Success of...

What is cloud computing? Introduction to Cloud Computing

In this article we will talk about one of the most trending and important technologies, which is playing a pivotal in our...

Recent Comments