NonCoprimeGraph | Topcoder Archive

Problem Statement

Two positive integers are called coprime (or relatively prime) if their greatest common divisor is 1. For example, 10 and 21 are coprime, but 15 and 21 are not coprime as they are both divisible by 3.

Let G be a simple undirected graph with the following properties:

G has n vertices, numbered 1, 2, ..., n.
For each pair (i,j) such that i != j, the vertices i and j are connected by an edge if and only if the numbers i and j are not coprime.

You are given the int n. You are also given ints s and t. Find and return the length of the shortest path between the vertices s and t. If there is no such path, return -1 instead.

Definition

Class:: NonCoprimeGraph
Method:: distance
Parameters:: int, int, int
Returns:: int
Method signature:: int distance(int n, int s, int t)
(be sure your method is public)

Constraints

n will be between 1 and 1,000,000,000, inclusive.
s will be between 1 and n, inclusive.
t will be between 1 and n, inclusive.

Examples

```
10
```
```
8
```
```
9
```
```
Returns: 2
```
The numbers 8 and 9 are coprime, thus there is no direct edge between the vertices 8 and 9. There is a unique shortest path of length 2: the path 8 - 6 - 9.
```
10
```
```
6
```
```
9
```
```
Returns: 1
```
The numbers 6 and 9 are both divisible by 3. As they are not coprime, there is a direct edge between the vertices 6 and 9. Obviously, this edge is the shortest path that connects 6 and 9.
```
100
```
```
89
```
```
97
```
```
Returns: -1
```
```
100
```
```
97
```
```
97
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.