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 , Math . 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 astatic void duplicate printing of same element ; Print the factors from n ; Driver Code ; Given N and M ; Function call
using System ; using System . Collections . Generic ; class GFG { static 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 ; } static void shortestpath ( int m , int n ) { List < int > mfactor = new List < int > ( ) ; List < int > nfactor = new List < int > ( ) ; Dictionary < int , int > fre = new Dictionary < int , int > ( ) ; mfactor . Add ( m ) ; fre . Add ( m , 1 ) ; while ( m != 1 ) { if ( isprm ( m ) != 0 ) { mfactor . Add ( 1 ) ; if ( ! fre . ContainsKey ( 1 ) ) fre . Add ( 1 , 1 ) ; m = 1 ; } else { for ( int i = 2 ; i <= Math . Sqrt ( m ) ; i ++ ) { if ( m % i == 0 ) { mfactor . Add ( m / i ) ; if ( ! fre . ContainsKey ( m / i ) ) fre . Add ( m / i , 1 ) ; m = ( m / i ) ; break ; } } } } nfactor . Add ( n ) ; while ( fre . ContainsKey ( n ) && fre [ n ] != 1 ) { if ( isprm ( n ) != 0 ) { nfactor . Add ( 1 ) ; n = 1 ; } else { for ( int i = 2 ; i <= Math . Sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) { nfactor . Add ( n / i ) ; n = ( n / i ) ; break ; } } } } for ( int i = 0 ; i < mfactor . Count ; i ++ ) { if ( mfactor [ i ] == n ) break ; Console . Write ( mfactor [ i ] + " ▁ < - - > ▁ " ) ; } for ( int i = nfactor . Count - 1 ; i >= 0 ; i -- ) { if ( i == 0 ) Console . Write ( nfactor [ i ] ) ; else Console . Write ( nfactor [ i ] + " ▁ < - - > ▁ " ) ; } } public static void Main ( String [ ] args ) { int m = 18 , n = 19 ; shortestpath ( m , n ) ; } }