Fix GCD of two integers

Question

I am a beginner in Java. I was asked to write a program that finds the GCD of two numbers entered by the user. I tried this but no output, how to fix it?

import java.util.Scanner;

public class myclass {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);

        int a = scan.nextInt();
        int b = scan.nextInt();

        if (a < b) {
            for (int c = a; c < 0; c--) {
                if (a % c == 0 && b % c == 0) {
                    System.out.print(c);
                }
            }

            if (b < a) {
                for (int c = b; c < 0; c--) {
                    if (b % c == 0 && a % c == 0) {
                        System.out.print(c);
                    }
                }
            }
        }
    }
}

Answer 1

Others have fixed your code already. If you would like a shorter approach you can look at this example:

public static void main(String[] args) {
    int a = 60;
    int b = 24;

    for(int i = Math.min(a, b); i > 0; i--){
        if(a % i == 0 && b % i == 0){
            System.out.println("GCD: " + i);
            break;
        }
    }
}

Output:

GCD: 12

By using Math.min() you don't have to create two loops to see whether a is where you should start, or b.

Answer 2

The bigger issue is that your loop condition is incorrect:

for (int c = a; c < 0; c--)

should be

for (int c = a; c > 0; c--)

and vice versa. Although it's good to handle the b < a problem, as well as a == b by simply using else for the second clause (with proper bracketing of course).

Then there's the issue of printing out incorrect solutions after the GCD has been found. To do this, use break; after the print statement.

Answer 3

You have the two ifs within each other, and somewhat incorrect for-loop comparisons. Try:

 import java.util.Scanner;

  public class myclass {

public static void main(String args[]) {

    Scanner scan = new Scanner(System.in);

    int a = scan.nextInt();
    int b = scan.nextInt();

    if (a < b) {
        for (int c = a; c > 0; c--) {
            if (a % c == 0 && b % c == 0) {
                System.out.print(c);
            }
        }
    }
    if (b < a) {
        for (int c = b; c > 0; c--) {
            if (b % c == 0 && a % c == 0) {
                System.out.print(c);
            }
        }

    }

}
}

Anyway, there's a better, more efficient algorithm out there for GCD. I won't code it up for you, but it is done by subtracting the smaller number from the larger, as many times as possible without making the final difference negative. If the last number is non-zero, the numbers are switched and this continues. When you finally get the two numbers equal to each other, that is the GCD.

Answer 4

your loop condition is incorrect:

for (int c = b; c < 0; c--)

it should be the following to make some sense:

for (int c = b; c > 0; c--)

However, i would go for a Euclid's Algorithm recursive approach, effective and simpler:

  public static int gcd(int p, int q) {
    if (q == 0) {
      return p;
    }
    return gcd(q, p % q);
  }

Answer 5

Your for loops never execute on typical (read: positive) input from the user.

c will typically not be below 0 and the loop will terminate, before it is even run once. See also this java tutorial.