Count of prime factors of N to be added at each step to convert N to M | Array to store shortest prime factor of every integer ; Function to precompute shortest prime factors ; Function to append distinct prime factors of every integer into a set ; Store distinct prime factors ; Function to return minimum steps using BFS ; Queue of pairs to store the current number and distance from root . ; Set to store distinct prime factors ; Run BFS ; Find out the prime factors of newNum ; Iterate over every prime factor of newNum . ; If M is obtained ; Return number of operations ; If M is exceeded ; Otherwise ; Update and store the new number obtained by prime factor ; If M cannot be obtained ; Driver code
spf = [ - 1 for i in range ( 100009 ) ] ; NEW_LINE def sieve ( ) : NEW_LINE INDENT i = 2 NEW_LINE while ( i * i <= 100006 ) : NEW_LINE INDENT for j in range ( i , 100006 , i ) : NEW_LINE INDENT if ( spf [ j ] == - 1 ) : NEW_LINE INDENT spf [ j ] = i ; NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def findPrimeFactors ( s , n ) : NEW_LINE INDENT while ( n > 1 ) : NEW_LINE INDENT s . add ( spf [ n ] ) ; NEW_LINE n //= spf [ n ] ; NEW_LINE DEDENT return s ; NEW_LINE DEDENT def MinimumSteps ( n , m ) : NEW_LINE INDENT q = [ ] NEW_LINE s = set ( ) NEW_LINE q . append ( [ n , 0 ] ) NEW_LINE while ( len ( q ) != 0 ) : NEW_LINE INDENT newNum = q [ 0 ] [ 0 ] NEW_LINE distance = q [ 0 ] [ 1 ] NEW_LINE q . pop ( 0 ) ; NEW_LINE k = findPrimeFactors ( s , newNum ) ; NEW_LINE for i in k : NEW_LINE INDENT if ( newNum == m ) : NEW_LINE INDENT return distance ; NEW_LINE DEDENT elif ( newNum > m ) : NEW_LINE INDENT break ; NEW_LINE DEDENT else : NEW_LINE INDENT q . append ( [ newNum + i , distance + 1 ] ) ; NEW_LINE DEDENT DEDENT DEDENT return - 1 ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 7 NEW_LINE M = 16 ; NEW_LINE sieve ( ) ; NEW_LINE print ( MinimumSteps ( N , M ) ) NEW_LINE DEDENT