How to find GCD, LCM on a set of numbers

Question

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?

Heretical

Answer 1

I've used Euclid's algorithm to find the greatest common divisor of two numbers; it can be iterated to obtain the GCD of a larger set of numbers.

private static long gcd(long a, long b)
{
    while (b > 0)
    {
        long temp = b;
        b = a % b; // % is remainder
        a = temp;
    }
    return a;
}

private static long gcd(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
    return result;
}

Least common multiple is a little trickier, but probably the best approach is reduction by the GCD, which can be similarly iterated:

private static long lcm(long a, long b)
{
    return a * (b / gcd(a, b));
}

private static long lcm(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}

Snoop

Is there a faster approach in terms of complexity? – Lanchow

@binaryBaBa, faster than linear in the number of integers would be impossible since you'd have to skip examining some. As for the GCD itself, binary GCD may be faster for arbitrary-precision numbers since it shifts instead of dividing. – Snoop

See also Lehmer's GCD which avoids division when the quotient would be small. I don't know that either of these would improve the asymptotic worst case bound, though. – Snoop

@Jeffrey Hantin Nonsense. There are often less-than-linear ways to determine divisors, based on the properties of the number under examination, which do indeed skip some integers. Example: if the number is odd, one can bypass even multiples of even numbers. Etc. There are many such shortcuts. – Teamwork

@JeffreyHantin Pardon, but Stack has changed its editing system so I have no way to correct the above but must amend it here. That should have read "bypass multiples of even numbers", as opposed to "even multiples of even numbers". The point was: there are many shortcuts to get around a linear search for divisors. Some of them are known to gradeschoolers. – Teamwork

I suppose this assumes all the numbers are non-negative to begin with and needs adjustment for negatives? – Brakpan

@LonnyEachus, the OP asked for the easiest GCD/LCM, not the most efficient; that probably belongs in its own question instead of a comment thread. – Snoop

Is there a reason behind the parentheses in a * (b / gcd(a, b)) (in your lcm(long, long))? – Ardennes

@PEMapModder, if a * b is evaluated first the resulting temporary is almost surely greater than the result and thus more likely to overflow long. By definition gcd(a, b) evenly divides both a and b, so we can divide before multiplying and avoid this. The same logic applies if using BigInteger, except instead of avoiding overflow you are reducing the computational overhead by keeping numbers smaller. – Snoop

@JeffreyHantin thanks. You should probably add it to your answer. – Ardennes

@JeffreyHantin Does your code create and destroy temp at each iteration of the while loop? Is there an overhead due to memory allocation associated with that? Would it be better to define long temp; outside the loop first and then just assign new values to it throughout the calculation? – Incinerate

@Kagaratsch, there is negligible practical difference between the two cases; long is a primitive rather than a class, so there can't be a heap allocation. A decent runtime will automatically reuse the local variable space just as if it was declared outside the loop, or even stuff it in a register for its brief lifetime instead of allocating local variable space. Declaring it inside the loop also clarifies (at least to the reader) that its value need not be retained across iterations. – Snoop

@JeffreyHantin My reply appears here because it was concerning your own original comment on Jan. 5 '15, which was simply incorrect. – Teamwork

The last two edits do not make sense at all! The last function does not compute the gcd, but the lcm. – Krouse

@Krouse I thought same as you, I think there was an error in code. I think last method's name should be lcd, but in lcm(long a, long b) , gcd should be used. – Expander

For calculating the greatest common divisor of two numbers, the Guava library has IntMath.gcd (for ints) and LongMath.gcd (for longs). (Since Guava 11.0, released in Dec 2011.) – Photopia

Answer 2

There is an Euclid's algorithm for GCD,

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

By the way, a and b should be greater or equal 0, and LCM = |ab| / GCF(a, b)

Separation

Answer 3

There are no build in function for it. You can find the GCD of two numbers using Euclid's algorithm.

For a set of number

GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n )

Apply it recursively.

Same for LCM:

LCM(a,b) = a * b / GCD(a,b)
LCM(a_1,a_2,a_3,...,a_n) = LCM( LCM(a_1, a_2), a_3, a_4,..., a_n )

Kabyle

The BigInteger class has a gcd method. +1 for answering the question for a set of integers rather than just a pair. – Meteoric

Answer 4

If you can use Java 8 (and actually want to) you can use lambda expressions to solve this functionally:

private static int gcd(int x, int y) {
    return (y == 0) ? x : gcd(y, x % y);
}

public static int gcd(int... numbers) {
    return Arrays.stream(numbers).reduce(0, (x, y) -> gcd(x, y));
}

public static int lcm(int... numbers) {
    return Arrays.stream(numbers).reduce(1, (x, y) -> x * (y / gcd(x, y)));
}

I oriented myself on Jeffrey Hantin's answer, but

• calculated the gcd functionally
• used the varargs-Syntax for an easier API (I was not sure if the overload would work correctly, but it does on my machine)
• transformed the gcd of the numbers-Array into functional syntax, which is more compact and IMO easier to read (at least if you are used to functional programming)

This approach is probably slightly slower due to additional function calls, but that probably won't matter at all for the most use cases.

Krouse

Very clean loved it – Macymad

Answer 5

int gcf(int a, int b)
{
    while (a != b) // while the two numbers are not equal...
    { 
        // ...subtract the smaller one from the larger one

        if (a > b) a -= b; // if a is larger than b, subtract b from a
        else b -= a; // if b is larger than a, subtract a from b
    }

    return a; // or return b, a will be equal to b either way
}

int lcm(int a, int b)
{
    // the lcm is simply (a * b) divided by the gcf of the two

    return (a * b) / gcf(a, b);
}

Justinn

This is an implementation of the Euclidean Algorithm. To find the GCF of two numbers, subtract the larger number from the smaller number while the two numbers are not equal. For example: Find the GCF of 6 and 10: 10 6 // 10 is larger than 6, so subtract 6 from 10; 4 6 // 6 is now larger than 4, so subtract 4 from 10; 4 2 // 4 is larger than 2, so subtract 2 from 4; 2 2 // the two numbers are now equal, and that's the GCF; The LCM in mathematics is simply the first number times the second number divided by their GCF. – Justinn

This is also a really slow implementation of gcf. Using % would make things much faster (and make this no different than two other answers). – Scarlatina

Answer 6

int lcmcal(int i,int y)
{
    int n,x,s=1,t=1;
    for(n=1;;n++)
    {
        s=i*n;
        for(x=1;t<s;x++)
        {
            t=y*x;
        }
        if(s==t)
            break;
    }
    return(s);
}

Pony

Answer 7

With Java 8, there are more elegant and functional ways to solve this.

LCM:

private static int lcm(int numberOne, int numberTwo) {
    final int bigger = Math.max(numberOne, numberTwo);
    final int smaller = Math.min(numberOne, numberTwo);

    return IntStream.rangeClosed(1,smaller)
                    .filter(factor -> (factor * bigger) % smaller == 0)
                    .map(factor -> Math.abs(factor * bigger))
                    .findFirst()
                    .getAsInt();
}

GCD:

private static int gcd(int numberOne, int numberTwo) {
    return (numberTwo == 0) ? numberOne : gcd(numberTwo, numberOne % numberTwo);
}

Of course if one argument is 0, both methods will not work.

Reld

Why do you code the lcm so complicated? It is shorter and less error prone to reduce the lcm to the gcd. Your gcd algorithm does work if one argument is zero. – Krouse

Answer 8

for gcd you cad do as below:

    String[] ss = new Scanner(System.in).nextLine().split("\\s+");
    BigInteger bi,bi2 = null;
    bi2 = new BigInteger(ss[1]);
    for(int i = 0 ; i<ss.length-1 ; i+=2 )
    {
        bi = new BigInteger(ss[i]);
        bi2 = bi.gcd(bi2);
    }
    System.out.println(bi2.toString());

Sibert

Answer 9

public class HcfLcm {
    public static void main(String[] args) {
        System.out.println("HCF: "+ getHcf(20, 15)); //5
        System.out.println("LCM: "+ getLcm2(20, 15)); //60
    }

    private static Integer getLcm2(int n1, int n2) {
        int lcm = Math.max(n1, n2);
        // Always true
        while (true) {
            if (lcm % n1 == 0 && lcm % n2 == 0) {
                break;
            }
            ++lcm;
        }
        return lcm;
    }

    private static Integer getLcm(int i, int j) {
        int hcf = getHcf(i, j);
        return hcf * i/hcf * j/hcf; // i*j*hcf
    }

    private static Integer getHcf(int i, int j) {
        while(i%j != 0) {
            int temp = i%j;
            i = j;
            j = temp;
        }
        return j;
    }
}

Apnea

Answer 10

import java.util.Scanner; public class Lcmhcf {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    Scanner scan = new Scanner(System.in);
    int n1,n2,x,y,lcm,hcf;
    System.out.println("Enter any 2 numbers....");
    n1=scan.nextInt();
    n2=scan.nextInt();
    x=n1;
    y=n2;

    do{
       if(n1>n2){
         n1=n1-n2;
       }
       else{
         n2=n2-n1;
       }
     } while(n1!=n2);
     hcf=n1;
     lcm=x*y/hcf;
     System.out.println("HCF IS = "+hcf);
     System.out.println("LCM IS = "+lcm);

     }
 }
//## Heading ##By Rajeev Lochan Sen

Moskowitz

welcome to SO. Please double check the formatting of your code. – Hydrogeology

Answer 11

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n0 = input.nextInt(); // number of intended input.
        int [] MyList = new int [n0];

        for (int i = 0; i < n0; i++)
            MyList[i] = input.nextInt();
            //input values stored in an array
        int i = 0;
        int count = 0;
            int gcd = 1; // Initial gcd is 1
            int k = 2; // Possible gcd
            while (k <= MyList[i] && k <= MyList[i]) {
                if (MyList[i] % k == 0 && MyList[i] % k == 0)
                    gcd = k; // Update gcd
                k++;
                count++; //checking array for gcd
            }
           // int i = 0;
            MyList [i] = gcd;
            for (int e: MyList) {
                System.out.println(e);

            }

            }

        }

Almazan

Hi, welcome to Stack Overflow. Thanks for posting an answer to this question, but answers which contain code only are generally not that helpful to people. See the accepted answer for an example of a good answer. See How do I write a good answer? for more information. – Neurology

Answer 12

import java.util.*;
public class lcm {
    public static void main(String args[])
    {
        int lcmresult=1;
        System.out.println("Enter the number1: ");
        Scanner s=new Scanner(System.in);
        int a=s.nextInt();
        System.out.println("Enter the number2: ");
        int b=s.nextInt();
        int max=a>b?a:b;
        for(int i=2;i<=max;i++)
        {
            while(a%i==0||b%i==0)
            {
                lcmresult=lcmresult*i;
                if(a%i==0)
                    a=a/i;
                if(b%i==0)
                    b=b/i;
                if(a==1&&b==1)
                    break;
            }
        }
    System.out.println("lcm: "+lcmresult);
}
}

Precise

Answer 13

int lcm = 1;
int y = 0;
boolean flag = false;
for(int i=2;i<=n;i++){
            if(lcm%i!=0){
                for(int j=i-1;j>1;j--){
                    if(i%j==0){
                        flag =true;
                        y = j;
                        break;
                    }
                }
                if(flag){
                    lcm = lcm*i/y;
                }
                else{
                    lcm = lcm*i;
                }
            }
            flag = false;
        }

here, first for loop is for getting every numbers starting from '2'. then if statement check whether the number(i) divides lcm if it does then it skip that no. and if it doesn't then next for loop is for finding a no. which can divides the number(i) if this happens we don't need that no. we only wants its extra factor. so here if the flag is true this means there already had some factors of no. 'i' in lcm. so we divide that factors and multiply the extra factor to lcm. If the number isn't divisible by any of its previous no. then when simply multiply it to the lcm.

Oleander

Hi, welcome to the site. While this code may answer the question, it's better to include some explanation of how it works and how to use it. Furthermore, I don't see how this answer adds anything to this Q&A since there are already answers covering well-understood and well-tested solutions to this problem. – Schrader