Minimize steps required to make two values equal by repeated division by any of their prime factor which is less than M

import java.util.*;

public class GFG {

    

    static int primes[] = new int[1000006];

    

    static int gcd(int a, int b)

    {

        

        if (b == 0)

            return a;

        

        else

            return gcd(b, a % b);

    }

    

    

    static 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;

                }

            }

        }

    }

    

    

    static int Steps(int x, int m)

    {

        

        int steps = 0;

        boolean flag = false;

        

        while (x > 1) {

            if (primes[x] > m) {

                flag = true;

                break;

            }

            

            

            x /= primes[x];

            steps++;

        }

        

        

        if (flag)

            return -1;

        

        return steps;

    }

    

    

    static 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;

    }

    

    public static void main(String args[])

    {

        int X = 160;

        int Y = 180;

        int M = 10;

        System.out.println(

            minimumSteps(X, Y, M));

    }

}

Let's block ads! (Why?)