LCM of Two Numbers in Python: 3 Methods Explained

LCM of two numbers is the smallest positive integer divisible by both, and placement aptitude tests in India test it in two ways: as a maths problem and as a Python implementation question.

Three methods cover every scenario. The brute-force loop is the easiest to understand. The GCD-based formula is the one placement coding rounds expect. The math.lcm builtin, added in Python 3.9, is the cleanest option when you are writing real code rather than demonstrating algorithmic reasoning.

What LCM Is and How It Connects to GCD

The least common multiple of two positive integers a and b is the smallest positive integer that both a and b divide without remainder.

A few concrete cases before the formula:

• LCM(4, 6) = 12. Multiples of 4: 4, 8, 12. Multiples of 6: 6, 12. First overlap: 12.
• LCM(6, 9) = 18. Multiples of 6: 6, 12, 18. Multiples of 9: 9, 18. First overlap: 18.
• LCM(7, 11) = 77. Both are prime with no common factor, so their LCM is their product.

The relationship between LCM and GCD (Greatest Common Divisor) follows from prime factorisation. For every prime p appearing in a or b with exponent alpha in a and exponent beta in b:

• The LCM takes the higher exponent: max(alpha, beta)
• The GCD takes the lower exponent: min(alpha, beta)
• max(alpha, beta) + min(alpha, beta) = alpha + beta

This means LCM(a, b) times GCD(a, b) equals a times b, which rearranges to:

LCM(a, b) = (a * b) / GCD(a, b)

Python exposes GCD computation via math.gcd from the standard math module, available since Python 3.5. That one function is the key to the efficient implementation below.

One terminology note: GCD is also called HCF (Highest Common Factor) in Indian school syllabi and placement aptitude papers. Both terms refer to the same value.

Method 1: Brute-Force Multiple Search

The simplest approach: start from max(a, b) and increment by 1 each step until you find a number divisible by both inputs.

def lcm_brute(a, b):
    candidate = max(a, b)
    while True:
        if candidate % a == 0 and candidate % b == 0:
            return candidate
        candidate += 1

What happens in practice:

• For lcm_brute(12, 18), the loop starts at 18 and reaches 36 after 19 iterations.
• For lcm_brute(7, 11), the loop starts at 11 and needs 67 iterations to reach 77.
• For two large primes with no common factor, the loop runs for their full product minus the larger value in iterations.

The practical limits of this approach:

• Time complexity is O(LCM(a, b) / max(a, b)), which degrades badly when inputs share no common factors.
• For inputs above 100,000 in a timed coding round, the loop will typically time out on standard online judges.
• Use it only when you need to explain the concept clearly or when inputs are guaranteed small.

Method 2: GCD-Based Formula (The Efficient Approach)

The formula LCM(a, b) = (a * b) // GCD(a, b) runs in O(log(min(a, b))) time, because the Euclidean algorithm for GCD terminates in at most logarithmically many steps.

The Euclidean Algorithm for GCD

The algorithm relies on the property that GCD(a, b) = GCD(b, a % b). The remainder shrinks each step, and the loop terminates when the remainder reaches zero.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Combining GCD and the LCM Formula

def lcm(a, b):
    return (a * b) // gcd(a, b)

Two implementation details worth noting:

• Use integer floor division (//), not /. The formula always produces an integer, but floating-point division can introduce rounding errors for very large inputs.
• The formula handles the case where one number divides the other cleanly. lcm(6, 12) computes GCD(6, 12) = 6, then 6 times 12 divided by 6 = 12. Correct.

This is the implementation placement coding rounds expect to see. It shows awareness of algorithmic efficiency, uses a standard mathematical identity, and works for all positive integer inputs.

Method 3: math.lcm, Python’s Builtin (Python 3.9+)

math.lcm was added to the Python 3.9 release (October 2020) and accepts any number of non-negative integer arguments.

import math

print(math.lcm(12, 18))        # 36
print(math.lcm(15, 25))        # 75
print(math.lcm(7, 11))         # 77
print(math.lcm(8, 12))         # 24
print(math.lcm(12, 18, 24))    # 72

Behaviour at the edges:

• Zero arguments: returns 1 (the identity element for LCM).
• One argument: returns that argument.
• Two or more: returns their LCM, computed internally via the GCD relationship.

All major placement test platforms (AMCAT, CoCubes, and company-specific portals for TCS, Infosys, and Wipro) support Python 3.9 or later, so math.lcm is available in any timed session. If the question explicitly asks you to implement the algorithm from scratch rather than call a builtin, use Method 2 instead.

The from math import lcm import style also works and saves the math. prefix in repeated calls.

Four Worked Examples, Verified by Hand

Each example below is solved using the GCD formula and confirmed by independent prime factorisation. The worked GCD steps show the Euclidean algorithm running manually.

• LCM(12, 18)

  • GCD steps: GCD(12, 18) to GCD(18, 12) to GCD(12, 6) to GCD(6, 0) = 6
  • LCM = (12 times 18) // 6 = 216 // 6 = 36
  • Factorisation check: 12 = 2 squared times 3; 18 = 2 times 3 squared. LCM = 2 squared times 3 squared = 4 times 9 = 36. Matches.

• LCM(15, 25)

  • GCD steps: GCD(15, 25) to GCD(25, 15) to GCD(15, 10) to GCD(10, 5) to GCD(5, 0) = 5
  • LCM = (15 times 25) // 5 = 375 // 5 = 75
  • Factorisation check: 15 = 3 times 5; 25 = 5 squared. LCM = 3 times 5 squared = 3 times 25 = 75. Matches.

• LCM(7, 11)

  • GCD steps: GCD(7, 11) to GCD(11, 7) to GCD(7, 4) to GCD(4, 3) to GCD(3, 1) to GCD(1, 0) = 1
  • LCM = (7 times 11) // 1 = 77 // 1 = 77
  • Coprime check: 7 and 11 are both prime. Their GCD is 1, so their LCM is their product. 7 times 11 = 77. Matches.

• LCM(8, 12)

  • GCD steps: GCD(8, 12) to GCD(12, 8) to GCD(8, 4) to GCD(4, 0) = 4
  • LCM = (8 times 12) // 4 = 96 // 4 = 24
  • Factorisation check: 8 = 2 cubed; 12 = 2 squared times 3. LCM = 2 cubed times 3 = 8 times 3 = 24. Matches.

All four agree between the Euclidean formula and prime factorisation. These are the examples that appear most often in placement aptitude papers and coding round problem sets.

LCM of N Numbers with functools.reduce

LCM of N numbers extends naturally from the two-number case, because LCM is associative: LCM(a, b, c) = LCM(LCM(a, b), c). Apply the two-number function pairwise, accumulating left to right.

Python’s functools.reduce automates this:

from functools import reduce
from math import gcd

def lcm(a, b):
    return (a * b) // gcd(a, b)

numbers = [12, 18, 24]
result = reduce(lcm, numbers)
print(result)  # 72

Verification of that result:

• Step 1: lcm(12, 18) = 36 (as confirmed in the worked examples above)
• Step 2: lcm(36, 24): GCD(36, 24) to GCD(24, 12) to GCD(12, 0) = 12. LCM = 36 times 24 // 12 = 864 // 12 = 72.

In Python 3.9 and above, math.lcm handles this directly without reduce:

import math
print(math.lcm(12, 18, 24))  # 72

LCM of N numbers appears as a follow-up question in placement coding rounds at companies that test quantitative aptitude alongside programming. If the two-number version is the first sub-problem, the N-number generalisation is often the second. The reduce approach shows functional-programming fluency on top of the mathematical knowledge.

LCM is also the shortcut method for time and work problems in placement aptitude, where the LCM of individual work cycle lengths gives the point at which all workers finish together. Quantitative aptitude sections in campus placement evaluation tests regularly include both the maths variant and the coding variant in the same session. Tests such as the Mu Sigma MuAPT include LCM-type computation under their numerical reasoning section.

The reduce-over-accumulator pattern that extends two-number LCM to an arbitrary list is the same pattern used in production Python pipelines for batch processing, scheduling, and token-budget allocation in LLM APIs. If you want to move that Python fluency from aptitude prep to applied AI work, TinkerLLM is the practical starting point at ₹299.