Prime Spiral
Time limit2sMemory limit1024 MB
Given two numbers in the Ulam spiral, find the shortest path between their cells moving only through composite cells, or report impossible.
- Level
Medium6 of 10
- Topics
- BFS, Number theory, Implementation, Math
- Solved
- No attempts yet
Problem
Boredom can be good for creativity. The Polish mathematician Stanislaw Ulam (1909-1984) discovered the spiral that bears his name while listening to a "long and very boring paper". He started by writing the positive integers in a spiral on a grid, one number per grid cell. Then he crossed out the composite numbers (the non-primes). An interesting property he discovered was that the remaining prime numbers seem to line up along many diagonals of the grid:
| All positive integers | Only primes |
|---|---|
 |  |
Both of these are infinitely large grids, but due to physical constraints only a finite subset of the grid fits in this space.
Consider traveling around the second grid above (the Ulam spiral). You may move freely to any cell containing a composite number, but moving to a cell containing a prime number is not allowed. You can travel up, down, left, or right, but not diagonally. Write a program to find the length of the shortest path between two composite numbers, if such a path exists. For example, from the cells numbered 12 and 72 it is impossible to travel to any other composite cell. The length of a path is the number of steps on the path.
Input
Each test case is given on one line containing two integers 1 ≤ x, y ≤ 10,000, which indicate two cells in the grid. There are limits on the input values, but the path between x and y is not limited in any way.
Output
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 exists.