Finding the Greatest Common Divisor in Java: A Beginner's Guide

[JaysFan31]

I am a beginner programmer in Java. Just started learning the past few weeks.

I'm taking a class and need to create a method that finds the greatest common divisor of two integers. I can assume that both are positive, but I cannot use the Euclidean Algorithm.

I'm sort of lost, but I think I'm on the right track, although this may look confusing:

public static int gcd(int a, int c)
{
int gcd;
int attempt;
if (a > c)
{
 if (a % c == 0)
{
gcd = c;
return gcd;
}
else
{
for (attempt = c; attempt = 1; attempt--)
do
{
if (c % attempt == 0 && a % attempt == 0)
{
gcd = attempt;
return attempt;
}
}
while (c % attempt != 0 || a % attempt == 0);
}
}

And then I basically copied the code with an else statement if c > a.

I'm sure there are a lot of mistakes. Could someone just point them out and offer a simpler way of doing it (possibly without using the Euclidean Algorithm)?

Thanks.
Michael

 

[AKG]

If you have a for loop, I don't think you want to use a variable with a larger scope as the counter variable. And you also don't need to copy the code for the case c > a. You can say "if a % c == 0 || c % a = 0 {return min(a,c);}" and make the for loop only run up to min(a,c). This isn't too creative though, as you can guess. But other than your straightforward approach above and the Euclidean Algorithm, I can't think of any other ways to find the gcd.

 

[AlephZero]

The way you used a local variable "int gcd" inside the function with the same name "public static int gcd(...)" is confusing (though not actually wrong).

In Java you can just say

return c;

instead of

gcd = c;
return gcd;

I wonder if you found some Fortran code and tried to translate it into Java. In Fortran you would write something like

function gcd(...)
integer gcd
...
gcd = c
return

But that (slightly strange) syntax is specific to Fortran, Java and C are different.

The efficient way to find the GCD is Euclid's algorithm (look it up on Google). You can either write the code using a loop, or use a recursive function. (If you haven't gone recursion yet, come back to this later.)

 

[JaysFan31]

OK. I think this is a lot better. It compiles and makes sense to me at least. However, it doesn't work properly for more difficult integers like 20, 30. Can anyone spot the problem (as I said nothing wrong with compiling, just doesn't work logically). As I said before, I can't use the Euclidean Algorithm, so I basically had to write the simplest program to find gcd.

public static int gcd(int a, int b)
{
int gcd;
if (a > b && a % b == 0)
{
gcd = b;
return gcd;
}
else if (b > a && b % a == 0)
{
gcd = a;
return gcd;
}
else if (a > b && a % b != 0)
{
int count = b;
do
{
count = count - 1;
}
while (b % count != 0 && a % count != 0);
gcd = count;
return gcd;
}
else if (b > a && b % a != 0)
{
int count = a;
do
{
count = count - 1;
}
while (b % count != 0 && a % count != 0);
gcd = count;
return gcd;
}
else
{
gcd = a;
return gcd;
}
}

 

[AlephZero]

You have got confused between "&&" to "||" which is a common mistake. Often in English you say "and" when you really mean "or", and vice versa.

Actually, the "do {...} while(...)" statement with a complicated "while(...)" condition is often hard to understand, and it is quite a rare statement in most Java programs.

A loop which tests at the top, "while(...) { ... }" is much more common. If you use that form of loop, then "&&" is the correct operator and the statement means the same read "in English" and "in Java".

There is another advantage of testing at the start of the loop - it gives you the possibility of doing nothing, if the condition is true before you get to the loop. That is often useful.

It's certainly useful calculating the gcd, because it handles all your special cases like a = b, a > b and a & b = 0, etc.

I came up with this version, which handles all the cases the same way:

public static int gcd(int a, int b)
{
int count = a;
if (b < a)
{
count = b;
}

while (a % count != 0 && b % count != 0)
{
count = count - 1;
}
return count;
}

A recursive function using Euclid's algorithm is even shorter:

public static int gcd(int a, int b)
{
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}