Minimize steps required to make two values equal by repeated division by any of their prime factor which is less than M | C ++ program for the above approach ; Stores the prime factor of numbers ; Function to find GCD of a and b ; Base Case ; Otherwise , calculate GCD ; Function to precompute the prime numbers till 1000000 ; Initialize all the positions with their respective values ; Iterate over the range [ 2 , sqrt ( 10 ^ 6 ) ] ; If i is prime number ; Mark it as the factor ; Utility function to count the number of steps to make X and Y equal ; Initialise steps ; Iterate x is at most 1 ; Divide with the smallest prime factor ; If X and Y can 't be  made equal ; Return steps ; Function to find the minimum number of steps required to make X and Y equal ; Generate all the prime factors ; Calculate GCD of x and y ; Divide the numbers by their gcd ; If not possible , then return - 1 ; ; Return the resultant number of steps ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int primes [ 1000006 ] ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ) ; } void preprocess ( ) { for ( int i = 1 ; i <= 1000000 ; i ++ ) primes [ i ] = i ; for ( int i = 2 ; i * i <= 1000000 ; i ++ ) { if ( primes [ i ] == i ) { for ( int j = 2 * i ; j <= 1000000 ; j += i ) { if ( primes [ j ] == j ) primes [ j ] = i ; } } } } int Steps ( int x , int m ) { int steps = 0 ; bool flag = false ; while ( x > 1 ) { if ( primes [ x ] > m ) { flag = true ; break ; } x /= primes [ x ] ; steps ++ ; } if ( flag ) return -1 ; return steps ; } int minimumSteps ( int x , int y , int m ) { preprocess ( ) ; int g = gcd ( x , y ) ; x = x / g ; y = y / g ; int x_steps = Steps ( x , m ) ; int y_steps = Steps ( y , m ) ; if ( x_steps == -1 y_steps == -1 ) return -1 ; return x_steps + y_steps ; } int main ( ) { int X = 160 ; int Y = 180 ; int M = 10 ; cout << ( minimumSteps ( X , Y , M ) ) ; }