Create a Graph by connecting divisors from N to M and find shortest path | C ++ program for the above approach ; Function to check the number is prime or not ; Base Cases ; Iterate till [ 5 , sqrt ( N ) ] to detect primarility of numbers ; Function to print the shortest path ; Use vector to store the factor of m and n ; Use map to check if largest common factor previously present or not ; First store m ; Check whether m is prime or not ; Largest common factor of m ; If m is divisible by i ; Store the largest common factor ; For number n ; Check whether n is prime ; Largest common factor of n ; Store the largest common factor ; Print the path Print factors from m ; To avoid duplicate printing of same element ; Print the factors from n ; Driver Code ; Given N and M ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int isprm ( int n ) { if ( n <= 1 ) return 0 ; if ( n <= 3 ) return 1 ; if ( n % 2 == 0 n % 3 == 0 ) return 0 ; for ( int i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return 0 ; return 1 ; } void shortestpath ( int m , int n ) { vector < int > mfactor , nfactor ; map < int , int > fre ; mfactor . push_back ( m ) ; fre [ m ] = 1 ; while ( m != 1 ) { if ( isprm ( m ) ) { mfactor . push_back ( 1 ) ; fre [ 1 ] = 1 ; m = 1 ; } else { for ( int i = 2 ; i <= sqrt ( m ) ; i ++ ) { if ( m % i == 0 ) { mfactor . push_back ( m / i ) ; fre [ m / i ] = 1 ; m = ( m / i ) ; break ; } } } } nfactor . push_back ( n ) ; while ( fre [ n ] != 1 ) { if ( isprm ( n ) ) { nfactor . push_back ( 1 ) ; n = 1 ; } else { for ( int i = 2 ; i <= sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) { nfactor . push_back ( n / i ) ; n = ( n / i ) ; break ; } } } } for ( int i = 0 ; i < mfactor . size ( ) ; i ++ ) { if ( mfactor [ i ] == n ) break ; cout << mfactor [ i ] << " ▁ < - - > ▁ " ; } for ( int i = nfactor . size ( ) - 1 ; i >= 0 ; i -- ) { if ( i == 0 ) cout << nfactor [ i ] ; else cout << nfactor [ i ] << " ▁ < - - > ▁ " ; } } int main ( ) { int m = 18 , n = 19 ; shortestpath ( m , n ) ; return 0 ; }