Create a Graph by connecting divisors from N to M and find shortest path | 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 ; Given N and M ; Function Call
function isprm ( n ) { if ( n <= 1 ) return 0 ; if ( n <= 3 ) return 1 ; if ( n % 2 == 0 n % 3 == 0 ) return 0 ; for ( let i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return 0 ; return 1 ; } function shortestpath ( m , n ) { let mfactor = new Array ( ) let nfactor = new Array ( ) let fre = new Map ( ) ; mfactor . push ( m ) ; fre [ m ] = 1 ; while ( m != 1 ) { if ( isprm ( m ) ) { mfactor . push ( 1 ) ; fre [ 1 ] = 1 ; m = 1 ; } else { for ( let i = 2 ; i <= Math . sqrt ( m ) ; i ++ ) { if ( m % i == 0 ) { mfactor . push ( m / i ) ; fre [ m / i ] = 1 ; m = ( m / i ) ; break ; } } } } nfactor . push ( n ) ; while ( fre [ n ] != 1 ) { if ( isprm ( n ) ) { nfactor . push ( 1 ) ; n = 1 ; } else { for ( let i = 2 ; i <= Math . sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) { nfactor . push ( n / i ) ; n = ( n / i ) ; break ; } } } } for ( let i = 0 ; i < mfactor . length ; i ++ ) { if ( mfactor [ i ] == n ) break ; document . write ( mfactor [ i ] + " " ) ; } for ( let i = nfactor . length - 1 ; i >= 0 ; i -- ) { if ( i == 0 ) document . write ( nfactor [ i ] ) ; else document . write ( nfactor [ i ] + " " ) ; } } let m = 18 , n = 19 ; shortestpath ( m , n ) ;