Count of prime factors of N to be added at each step to convert N to M | JavaScript program to find the minimum steps required to convert a number N to M . ; Array to store shortest prime factor of every integer ; Function to precompute shortest prime factors ; Function to insert 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
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } var spf = Array ( 100009 ) . fill ( 0 ) ; function sieve ( ) { for ( var i = 0 ; i < 100005 ; i ++ ) spf [ i ] = - 1 ; for ( var i = 2 ; i * i <= 100005 ; i ++ ) { for ( var j = i ; j <= 100005 ; j += i ) { if ( spf [ j ] == - 1 ) { spf [ j ] = i ; } } } } function findPrimeFactors ( s , n ) { while ( n > 1 ) { s . add ( spf [ n ] ) ; n /= spf [ n ] ; } return s ; } function MinimumSteps ( n , m ) { var q = [ ] ; var s = new Set ( ) ; q . push ( new pair ( n , 0 ) ) ; while ( q . length != 0 ) { var newNum = q [ 0 ] . first ; var distance = q [ 0 ] . second ; q . shift ( ) ; var k = findPrimeFactors ( s , newNum ) ; for ( var i of k ) { if ( newNum == m ) { return distance ; } else if ( newNum > m ) { break ; } else { q . push ( new pair ( newNum + i , distance + 1 ) ) ; } } } return - 1 ; } var N = 7 , M = 16 ; sieve ( ) ; document . write ( MinimumSteps ( N , M ) ) ;