LCM of Two Numbers in C, C++, Java and Python

To find the LCM of two numbers in C or any other language, compute the GCD with Euclid's algorithm, then LCM(a, b) = a ÷ GCD(a, b) × b. Python 3.9+ and C++17 have it built in; in C and Java you write the two short functions yourself.

Why Use the GCD Formula Instead of Listing Multiples?

The GCD formula needs one short loop, while listing multiples can need millions of steps. Listing multiples of 12 and 18 reaches 36 quickly, but for two large coprime numbers the LCM is their product, and a loop that counts up to it is slow.

• Speed: Euclid's algorithm needs at most 45 steps for any two numbers up to 9 digits (Lamé's theorem: at most 5 steps per digit).
• One loop: the GCD is the only loop; the LCM is a single expression after it.
• Overflow: dividing by the GCD first keeps every intermediate value no larger than the LCM itself.

The identity behind it, LCM × GCF = a × b, is explained on LCM vs HCF (GCF); the methods by hand are onHow to Find the LCM.

Euclid's GCD Algorithm in 6 Lines

Replace (a, b) with (b, a mod b) until b is 0; the last a is the GCD. For 12 and 18: (12, 18) → (18, 12) → (12, 6) → (6, 0), so the GCD is 6.

function gcd(a, b):
    while b ≠ 0:
        (a, b) = (b, a mod b)
    return |a|

function lcm(a, b):
    return |a| / gcd(a, b) * |b|

Every version below is this pseudocode in a different language.

LCM in Python

Use math.lcm on Python 3.9 and later; on older versions, divide by math.gcd. Both accept negative numbers and return a non-negative result.

import math
from functools import reduce

print(math.gcd(12, 18))         # 6
print(math.lcm(12, 18))         # 36  (Python 3.9+)
print(math.lcm(4, 6, 10))       # 60  (any number of arguments, 3.9+)

def lcm(a, b):                  # works on every Python 3 version
    return abs(a // math.gcd(a, b) * b)

print(reduce(lcm, [4, 6, 10]))  # 60

math.lcm takes any number of arguments, so a list needs no loop: math.lcm(*numbers).

LCM in Java

Java has no built-in LCM: write gcd and lcm as two static methods on long. For numbers beyond the range of long, BigInteger has gcd() built in.

import java.math.BigInteger;

public class Lcm {
    static long gcd(long a, long b) {
        while (b != 0) { long t = a % b; a = b; b = t; }
        return Math.abs(a);
    }

    static long lcm(long a, long b) {
        return Math.abs(a / gcd(a, b) * b);
    }

    public static void main(String[] args) {
        System.out.println(lcm(12, 18));                       // 36
        BigInteger x = BigInteger.valueOf(8), y = BigInteger.valueOf(12);
        System.out.println(x.multiply(y).divide(x.gcd(y)));    // 24
    }
}

How to Find the LCM of Two Numbers in C

C has no LCM in its standard library, so the program defines gcd and lcm on long long. This is the program most tutorials ask for: it reads two numbers and prints their LCM.

#include <stdio.h>

long long gcd(long long a, long long b) {
    while (b != 0) { long long t = a % b; a = b; b = t; }
    return a < 0 ? -a : a;
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;          /* no LCM with 0; 0 by convention */
    long long l = a / gcd(a, b) * b;         /* divide first: no overflow */
    return l < 0 ? -l : l;
}

int main(void) {
    long long a, b;
    printf("Enter two numbers: ");
    if (scanf("%lld %lld", &a, &b) != 2) return 1;
    printf("LCM of %lld and %lld = %lld\n", a, b, lcm(a, b));
    return 0;
}

Input 12 18 prints LCM of 12 and 18 = 36. The same gcd answers "LCM and GCD in C" in one program.

LCM in C++

Since C++17, std::lcm and std::gcd live in <numeric>. For an array, fold it with a loop.

#include <iostream>
#include <numeric>   // std::gcd, std::lcm (C++17)
#include <vector>

int main() {
    std::cout << std::lcm(12, 18) << '\n';    // 36
    std::cout << std::gcd(12, 18) << '\n';    // 6

    std::vector<long long> v{4, 6, 10};
    long long l = 1;
    for (long long x : v) l = std::lcm(l, x);
    std::cout << l << '\n';                   // 60
}

LCM in C# and JavaScript

Neither language has an LCM function; the GCD formula is two lines in each.

static long Gcd(long a, long b) => b == 0 ? Math.Abs(a) : Gcd(b, a % b);
static long Lcm(long a, long b) => Math.Abs(a / Gcd(a, b) * b);

const gcd = (a, b) => (b ? gcd(b, a % b) : Math.abs(a));
const lcm = (a, b) => Math.abs((a / gcd(a, b)) * b);

In JavaScript, numbers above 2⁵³ lose precision; the same two lines work on BigInt values (12n, 18n) once Math.abs is replaced by a sign check.

LCM of a List or Array

Fold the list: LCM(a, b, c) = LCM(LCM(a, b), c). For [4, 6, 10]: LCM(4, 6) = 12, then LCM(12, 10) = 60.

Python's reduce(lcm, numbers), the C++ loop above and a simple loop in C or Java all do this. Start from the first element, or from 1.

Common Mistakes in LCM Code

• Integer overflow: a * b / gcd(a, b) multiplies first. 50,000 × 60,000 = 3,000,000,000 is larger than a 32-bit int (2,147,483,647); a / gcd(a, b) * b gives 300,000 safely.
• Integer division in the wrong place: a / (gcd(a, b) * b) is not the same expression; keep the division on a alone.
• Negative inputs: % can return a negative remainder in C, C++, Java and JavaScript. Take the absolute value of the result, as every version above does.
• Zero: the LCM with 0 is undefined (0 has no positive multiple). Python's math.lcm and C++'s std::lcm return 0 by convention, so check for 0 if your program must reject it. More on LCM Edge Cases: One Number, Zero, and Negative Numbers.

Check Your Answer With the Calculator

Paste your test numbers into the LCM calculator with 12 and 18 loaded: it shows the GCF method step by step, so you can compare every intermediate value with your program's output.

Least Multiple Calculator: the LCM of 2 to 15 numbers, worked out six ways.

Frequently asked questions

Sources

• Wikipedia: Least common multiple: definition, notation, LCM × GCD = a × b
• Wolfram MathWorld: Least Common Multiple: formal properties
• Common Core 6.NS.B.4: GCF and LCM in grade 6