Shortest path to reach one prime to other by changing single digit at a time | CPP program to reach a prime number from another by changing single digits and using only prime numbers . ; Finding all 4 digit prime numbers ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Forming a vector of prime numbers ; in1 and in2 are two vertices of graph which are actually indexes in pset [ ] ; Returns true if num1 and num2 differ by single digit . ; To compare the digits ; If the numbers differ only by a single digit return true else false ; Generate all 4 digit ; Create a graph where node numbers are indexes in pset [ ] and there is an edge between two nodes only if they differ by single digit . ; Since graph nodes represent indexes of numbers in pset [ ] , we find indexes of num1 and num2 . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; class graph { int V ; list < int > * l ; public : graph ( int V ) { this -> V = V ; l = new list < int > [ V ] ; } void addedge ( int V1 , int V2 ) { l [ V1 ] . push_back ( V2 ) ; l [ V2 ] . push_back ( V1 ) ; } int bfs ( int in1 , int in2 ) ; } ; void SieveOfEratosthenes ( vector < int > & v ) { int n = 9999 ; bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } for ( int p = 1000 ; p <= n ; p ++ ) if ( prime [ p ] ) v . push_back ( p ) ; } int graph :: bfs ( int in1 , int in2 ) { int visited [ V ] ; memset ( visited , 0 , sizeof ( visited ) ) ; queue < int > que ; visited [ in1 ] = 1 ; que . push ( in1 ) ; list < int > :: iterator i ; while ( ! que . empty ( ) ) { int p = que . front ( ) ; que . pop ( ) ; for ( i = l [ p ] . begin ( ) ; i != l [ p ] . end ( ) ; i ++ ) { if ( ! visited [ * i ] ) { visited [ * i ] = visited [ p ] + 1 ; que . push ( * i ) ; } if ( * i == in2 ) { return visited [ * i ] - 1 ; } } } } bool compare ( int num1 , int num2 ) { string s1 = to_string ( num1 ) ; string s2 = to_string ( num2 ) ; int c = 0 ; if ( s1 [ 0 ] != s2 [ 0 ] ) c ++ ; if ( s1 [ 1 ] != s2 [ 1 ] ) c ++ ; if ( s1 [ 2 ] != s2 [ 2 ] ) c ++ ; if ( s1 [ 3 ] != s2 [ 3 ] ) c ++ ; return ( c == 1 ) ; } int shortestPath ( int num1 , int num2 ) { vector < int > pset ; SieveOfEratosthenes ( pset ) ; graph g ( pset . size ( ) ) ; for ( int i = 0 ; i < pset . size ( ) ; i ++ ) for ( int j = i + 1 ; j < pset . size ( ) ; j ++ ) if ( compare ( pset [ i ] , pset [ j ] ) ) g . addedge ( i , j ) ; int in1 , in2 ; for ( int j = 0 ; j < pset . size ( ) ; j ++ ) if ( pset [ j ] == num1 ) in1 = j ; for ( int j = 0 ; j < pset . size ( ) ; j ++ ) if ( pset [ j ] == num2 ) in2 = j ; return g . bfs ( in1 , in2 ) ; } int main ( ) { int num1 = 1033 , num2 = 8179 ; cout << shortestPath ( num1 , num2 ) ; return 0 ; }