Java: get greatest common divisor

java greatest-common-divisor
Albert picture Albert · Oct 24, 2010 · Viewed 211.7k times · Source

I have seen that such a function exists for BigInteger, i.e. BigInteger#gcd. Are there other functions in Java which also work for other types (int, long or Integer)? It seems this would make sense as java.lang.Math.gcd (with all kinds of overloads) but it is not there. Is it somewhere else?

(Don't confuse this question with "how do I implement this myself", please!)

Answer

Matt picture Matt · Oct 24, 2010

As far as I know, there isn't any built-in method for primitives. But something as simple as this should do the trick:

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

You can also one-line it if you're into that sort of thing:

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

It should be noted that there is absolutely no difference between the two as they compile to the same byte code.

Related questions

How to find GCD, LCM on a set of numbers

What would be the easiest way to calculate Greatest Common Divisor and Least Common Multiple on a set of numbers? What math functions can be used to find this information?

Read More
How to write a simple Java program that finds the greatest common divisor between two numbers?

Here is the question: "Write a method named gcd that accepts two integers as parameters and returns the greatest common divisor of the two numbers. The greatest common divisor (GCD) of two integers a and b is the largest integer …

Read More
Using recursion and implementing Euclid's algorithm to find GCD of three numbers from user

I am wanting to ask the user to input three numbers and then have program calculate the GCD using Euclid's algorithm all the while using recursion. My code right now implements two input numbers. I understand the approach of calculating …

Read More