Count of prime factors of N to be added at each step to convert N to M | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int [ ] spf = new int [ 100009 ] ; static void sieve ( ) { for ( int i = 0 ; i < 100005 ; i ++ ) spf [ i ] = - 1 ; for ( int i = 2 ; i * i <= 100005 ; i ++ ) { for ( int j = i ; j <= 100005 ; j += i ) { if ( spf [ j ] == - 1 ) { spf [ j ] = i ; } } } } static HashSet < Integer > findPrimeFactors ( HashSet < Integer > s , int n ) { while ( n > 1 ) { s . add ( spf [ n ] ) ; n /= spf [ n ] ; } return s ; } static int MinimumSteps ( int n , int m ) { Queue < pair > q = new LinkedList < > ( ) ; HashSet < Integer > s = new HashSet < Integer > ( ) ; q . add ( new pair ( n , 0 ) ) ; while ( ! q . isEmpty ( ) ) { int newNum = q . peek ( ) . first ; int distance = q . peek ( ) . second ; q . remove ( ) ; HashSet < Integer > k = findPrimeFactors ( s , newNum ) ; for ( int i : k ) { if ( newNum == m ) { return distance ; } else if ( newNum > m ) { break ; } else { q . add ( new pair ( newNum + i , distance + 1 ) ) ; } } } return - 1 ; } public static void main ( String [ ] args ) { int N = 7 , M = 16 ; sieve ( ) ; System . out . print ( MinimumSteps ( N , M ) ) ; } }