Create a Graph by connecting divisors from N to M and find shortest path | Python3 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
import math NEW_LINE def isprm ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT i = 5 NEW_LINE while i * i <= n : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT i += 6 NEW_LINE DEDENT return 1 NEW_LINE DEDENT def shortestpath ( m , n ) : NEW_LINE INDENT mfactor = [ ] NEW_LINE nfactor = [ ] NEW_LINE fre = dict . fromkeys ( range ( n + 1 ) , 0 ) NEW_LINE mfactor . append ( m ) NEW_LINE fre [ m ] = 1 NEW_LINE while ( m != 1 ) : NEW_LINE INDENT if ( isprm ( m ) ) : NEW_LINE INDENT mfactor . append ( 1 ) NEW_LINE fre [ 1 ] = 1 NEW_LINE m = 1 NEW_LINE DEDENT else : NEW_LINE INDENT sqt = ( int ) ( math . sqrt ( m ) ) NEW_LINE for i in range ( 2 , sqt + 1 ) : NEW_LINE INDENT if ( m % i == 0 ) : NEW_LINE INDENT mfactor . append ( m // i ) NEW_LINE fre [ m // i ] = 1 NEW_LINE m = ( m // i ) NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT nfactor . append ( n ) NEW_LINE while ( fre [ n ] != 1 ) : NEW_LINE INDENT if ( isprm ( n ) ) : NEW_LINE INDENT nfactor . append ( 1 ) NEW_LINE n = 1 NEW_LINE DEDENT else : NEW_LINE INDENT sqt = ( int ) ( math . sqrt ( n ) ) NEW_LINE for i in range ( 2 , sqt + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT nfactor . append ( n // i ) NEW_LINE n = ( n // i ) NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( len ( mfactor ) ) : NEW_LINE INDENT if ( mfactor [ i ] == n ) : NEW_LINE INDENT break NEW_LINE DEDENT print ( mfactor [ i ] , end = " ▁ < - - > ▁ " ) NEW_LINE DEDENT for i in range ( len ( nfactor ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT print ( nfactor [ i ] , end = " " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( nfactor [ i ] , end = " ▁ < - - > ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT m = 18 NEW_LINE n = 19 NEW_LINE shortestpath ( m , n ) NEW_LINE DEDENT