Greatest Common Factor

Question

I wrote this program to determine the Greatest Common Factor of any 2 given numbers, and would like to know of any improvements that can be made. I have tested it using a loop and 2 randomly generated numbers and it seems to work perfectly:

import java.util.ArrayList;
import java.util.Scanner;

public class GreatestCommonFactor
{
    public static void main(String[] args)
    {
        System.out.println("Please enter 2 numbers:");
        Scanner in = new Scanner(System.in);

        int a = Integer.parseInt(in.nextLine());
        int b = Integer.parseInt(in.nextLine());
        int greatestCommonFactor = gcf(a,b);

        System.out.println(greatestCommonFactor);
        in.close();
    }

    public static int gcf(int a, int b)
    {
        int result = 0;
        ArrayList<Integer> factorsA = factorise(a);
        ArrayList<Integer> factorsB = factorise(b);

        for (int i = 0; i < factorsA.size(); i++)
            if (factorsB.contains(factorsA.get(i)))
                result = factorsA.get(i);
        return result;
    }

    public static ArrayList<Integer> factorise(int num)
    {
        ArrayList<Integer> factors = new ArrayList<Integer>();
        int bounds = num/2;
        for (int i = 1; i <= bounds; i++)
            if (num % i == 0)
                factors.add(i);
        factors.add(num);
        return factors;
    }
}

Answer 1

Good job on closing your Scanner! I see a lot of people forget/miss that.

An alternative, just for your information, is using try with resources so you don't have to worry about closing/remembering to close it. As an aside, in general, you want to use more meaningful names than just 'a' and 'b' in your code (Though I'm totally going to be a hypocrite in a second, names are hard).

I would consider using Scanner's nextInt() method, you're using integers, using nextLine() isn't intuitive. As it is, despite your request for two numbers(should specify integers), if a user actually tries to input two space delimited numbers it'll throw an error.

Here's what the start of your code would look like with these suggestions:

        int first;
        int second;
        System.out.print("Please enter 2 integers: ");

        try(Scanner in = new Scanner(System.in)) {
            first = in.nextInt();
            second = in.nextInt();
        }

As for the actual logic of your code, You can use the Euclidean algorithm

// Greatest Common Denominator
public int computeGCD(int a, int b) {
    return b == 0 ? a : computeGCD(b, a % b);
}

Answer 2

Sure, the Euclidean algorithm is the way to go. Actually the Binary GCD algorithm is even faster.

Some points I can't see in the other reviews:

• I don't know what happens for negative numbers, do you? As there's no sane GCD definition working for them, you should throw an IAE.
• int bounds = num/2; Here, (int) Math.sqrt(num) suffices. For more efficiency the bound should get updated whenever a divisor gets found.
• if (num % i == 0) factors.add(i); This must be a loop, otherwise strange things happen.
• Actually, for numbers with factors contained with a higher power, strange things happen. Very strange, I think.
• If we had to factorize the numbers, it'd probably more efficient (but less modular) to factorize both numbers at once. You'd save yourself the trouble with lists.
• The method should be declared to return a List rather than ArrayList.

I have tested it using a loop and 2 randomly generated numbers and it seems to work perfectly:

Does it? How did you verify you missed no factor?

Answer 3

Good separation of input/output and calculation.

   int a = Integer.parseInt(in.nextLine());
   int b = Integer.parseInt(in.nextLine());

My first confusion was, since you create a Scanner, why aren't you using the .nextInt() method? My second confusion is, What if the user types something that doesn't parse as an Integer? What code is there that will handle the java.lang.NumberFormatException , (or the java.util.InputMismatchException if you're using in.nextInt())?

   for (int i = 0; i < factorsA.size(); i++)
       if (factorsB.contains(factorsA.get(i)))

A bit of inefficiency here as you're not exploiting the monotonicity of factorsB, and searching from the beginning each time instead of from the last place you found.

 public static ArrayList<Integer> factorise(int num)

This whole function is inefficient for multiple reasons. It's also misnamed. You're getting the list of all factors of the number, not factorising it (showing which prime numbers multiply to it).

Answer 4

Use Euclid's algorithm, it's much simpler and much much faster.

public static int gcf(int a, int b){
  return b == 0 ? a : gcf(b, a % b);
}