# Greatest Common Factor

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)
{
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)
return factors;
}
}

• Factorizing is extremely expensive for large integers (RSA is based on this being hard), computing the GCD via extended euclidean on the other hand is cheap. – CodesInChaos Apr 17 '15 at 7:53

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;

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);
}

• +1 for mention of Euclidean! Makes this problem so much easier and efficient! – Evan Bechtol Apr 16 '15 at 13:32
• Eculidean gives greatest common divisor not denominator right? Or am i wrong? – Sunil B N Sep 26 '18 at 10:03
• divisor = denominator – Legato Sep 26 '18 at 15:19

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?

• Mathematically, signs don't matter; gcd(-42, -49) == gcd(-42,49) == gcd(42,-49) == gcd(42,49). Also, both 7 and -7 are mathematically valid answers for this, although typically one chooses 7. Really, the interesting edge case is gcd(0,0) == 0. (the secret here is that "greatest" isn't meant to be with respect to <; instead, it's with respect to the partial ordering defined by divisibility. That is, x is less than or equivalen to y iff x divides y – Hurkyl Apr 17 '15 at 0:46
• @Hurkyl "although typically one chooses 7" - and that's the problem. You can't return a member of an equivalence class (like {7, -7}), which would be the perfect answer, you have to choose and choosing the non-negative member seems to be a bit arbitrary. Moreover, a negative input is usually an error, anyway. Moreover, it 'd have to be handled in the algorithm and that can be done be the caller equally well. – maaartinus Apr 17 '15 at 8:13
• Seems like we'd have to define further what we'd even want to use it for. If we're pragmatic, the popular method is popular for reasoning parallel to how it was 'arbitrarily' decided that negative numbers aren't prime. It's all about use cases. – Legato Apr 17 '15 at 15:51

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).

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);
}

• I came here to give this exact answer. ++ for beating me to it. – RubberDuck Apr 16 '15 at 21:33