# Path through graph Codevita 9 Solution

Page Contents

## Path through graph Codevita 9 Solution

You are given two regular numbers. Envision these characteristic numbers as hubs on a chart. On this chart, a number is associated with its biggest factor other than itself. You need to locate the most limited way among them and print the quantity of edges on that way.

In the event that the two numbers don’t have any regular factor, at that point build a way through 1. For better comprehension allude to the models beneath:

Model 1:

Input numbers: 2 4

The numbers are straightforwardly associated as follows on the chart. 2 is simply the biggest factor of 4, other than itself.

We can likewise observe that there is just nervous between them.

4 <- – > 2

Henceforth the quantity of edges in most limited way is 1.

Yield: 1

Model 2:

Input numbers: 18 19

The chart for number 18 and 19 will resemble this. Here we have 4 edges in the way.

18 <- – > 9 <- – > 3 <- – > 1 <- – > 19

Yield: 4

Model 3:

Input numbers: 9

The quantity of edges in most limited way is zero since the numbers compare to a similar hub.

Yield: 0

Requirements

0 < M, N <= 10 ^ 9

Information

Single line containing two space isolated whole numbers M, N

Yield

Number of edges in the most limited way.

Time Limit

Models

Model 1

Information

15689 28

Yield

Clarification :

The chart for number 15689 and 28 will resemble this.

Since we realize that biggest factor of 15689 other than itself is 541.

Since 541 is a prime number, it’s biggest factor other than itself is 1.

For number 28, it’s biggest factor other than itself is 14.

Biggest factor of 14, other than itself is 7.

Since 7 is a prime number, it’s biggest factor other than itself is 1.

Along these lines, the chart will resemble this:

15689 <- – > 541 <- – > 1 <- – > 7 <- – > 14 <- – > 28

Since there are 5 edges in this diagram, yield will be 5.

Model 2

Info

16 4

Yield

Clarification :

The diagram for number 16 and 4 will resemble this.

Since we realize that biggest factor of 16 other than itself is 8.

Biggest factor of 8 other than itself is 4. That is the other info number, so we will stop here.

Thus, the diagram will resemble this:

16<- – >8<- – >4

Since there are 2 edges in this chart, yield will be 2.”