Create a Graph by connecting divisors from N to M and find shortest path | Java 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
import java . util . * ; 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 ) { Vector < Integer > mfactor = new Vector < > ( ) ; Vector < Integer > nfactor = new Vector < > ( ) ; HashMap < Integer , Integer > fre = new HashMap < > ( ) ; mfactor . add ( m ) ; fre . put ( m , 1 ) ; while ( m != 1 ) { if ( isprm ( m ) != 0 ) { mfactor . add ( 1 ) ; fre . put ( 1 , 1 ) ; m = 1 ; } else { for ( int i = 2 ; i <= Math . sqrt ( m ) ; i ++ ) { if ( m % i == 0 ) { mfactor . add ( m / i ) ; fre . put ( m / i , 1 ) ; m = ( m / i ) ; break ; } } } } nfactor . add ( n ) ; while ( fre . containsKey ( n ) && fre . get ( 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 . size ( ) ; i ++ ) { if ( mfactor . get ( i ) == n ) break ; System . out . print ( mfactor . get ( i ) + " ▁ < - - > ▁ " ) ; } for ( int i = nfactor . size ( ) - 1 ; i >= 0 ; i -- ) { if ( i == 0 ) System . out . print ( nfactor . get ( i ) ) ; else System . out . print ( nfactor . get ( i ) + " ▁ < - - > ▁ " ) ; } } public static void main ( String [ ] args ) { int m = 18 , n = 19 ; shortestpath ( m , n ) ; } }