SPOJ: PPATH — Prime Path Solution

Problem:

We have a 4-digit prime number and we need to convert it to another 4-digit prime number, in each step changing exactly one digit. But here’s the problem, in the path from source prime number to the destination prime number, every intermediate number must be prime too. And we need find out minimum number of steps required to do it, for each prime number pair given as input.

Observations:

Here we have a source prime number and a destination prime number, and we have intermediate prime numbers connecting these two, so for calculating the shortest path, we can use BFS here.

Implementation:

Our nodes are all prime 4-digit numbers, so first we create a list of prime numbers using Sieve of Eratosthenes.

But every node isn’t connected to every other nodes, so to build the graph we connect those nodes(prime numbers from the list) only who differ by exactly one digit. For every connecting edge, weight is 1, so we don’t specify that.

Next we call our BFS function with the source prime number as root node, and we run it until we reach our destination prime number, calculating and storing level of every node we visit. After getting the destination node, we return it’s level, which is our output.

CODE: