Problem B
Prime Spiral

Boredom can be good for creativity. Polish mathematician Stanislaw Ulam (1909-1984) discovered the eponymous Ulam spiral while listening to a “long and very boring paper”. He started by writing down the positive integers in a spiral on a grid, one number per grid cell. Then he eliminated the composite numbers (i.e. non-primes). An interesting property he discovered was that the remaining prime numbers seem to form along many diagonals of the grid:

\includegraphics[width=0.45\textwidth ]{spiral_all_numbers}     \includegraphics[width=0.45\textwidth ]{spiral_primes}
Figure 1: Two spirals: one with all positive integers given, one with only primes.

Note that both of these are infinitely large grids, but due to physical constraints only a finite subset of the grid will fit in this space.

Let’s consider traveling around the second grid above (the Ulam spiral), where you are free to travel to any cell containing a composite number, but traveling to any cell containing a prime number is disallowed. You can travel up, down, left, or right, but not diagonally. Write a program to find the length of the shortest path between pairs composite numbers, if it is possible. Note, for example, that it is impossible to travel from the cells numbered $12$ and $72$ to any other composite cell. The length of a path is the number of steps on the path.


Each test case is described by a line of input containing two integers $1 \leq x, y \leq 10\, 000$ which indicate two cells in the grid. Note that while there are limits on the input values, the intervening path between $x$ and $y$ is not limited in any way.


For each case, display the case number followed by the length of the shortest path between the cells $x$ and $y$, or “impossible” if no such path is possible.

Sample Input 1 Sample Output 1
1 4
9 32
10 12
Case 1: 1
Case 2: 7
Case 3: impossible

Please log in to submit a solution to this problem

Log in