Count of prime factors of N to be added at each step to convert N to M | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int spf [ 100009 ] ; void sieve ( ) { memset ( spf , -1 , 100005 ) ; for ( int i = 2 ; i * i <= 100005 ; i ++ ) { for ( int j = i ; j <= 100005 ; j += i ) { if ( spf [ j ] == -1 ) { spf [ j ] = i ; } } } } set < int > findPrimeFactors ( set < int > s , int n ) { while ( n > 1 ) { s . insert ( spf [ n ] ) ; n /= spf [ n ] ; } return s ; } int MinimumSteps ( int n , int m ) { queue < pair < int , int > > q ; set < int > s ; q . push ( { n , 0 } ) ; while ( ! q . empty ( ) ) { int newNum = q . front ( ) . first ; int distance = q . front ( ) . second ; q . pop ( ) ; set < int > k = findPrimeFactors ( s , newNum ) ; for ( auto i : k ) { if ( newNum == m ) { return distance ; } else if ( newNum > m ) { break ; } else { q . push ( { newNum + i , distance + 1 } ) ; } } } return -1 ; } int main ( ) { int N = 7 , M = 16 ; sieve ( ) ; cout << MinimumSteps ( N , M ) ; }