Skip to content
doubtly

2 answers

Best answer

Answer: Find GCD by Euclid's method, then \( \text{LCM} = \frac{a \times b}{\text{GCD}} \).

Logic (12, 18): 18 % 12 = 6, 12 % 6 = 0, so GCD = 6 and LCM = 12 × 18 / 6 = 36.

Program:

#include <stdio.h>

int main()
{
    int a, b, x, y, r, gcd, lcm;

    printf("Enter two positive integers: ");
    scanf("%d %d", &a, &b);

    /* GCD by Euclid's method */
    x = a;
    y = b;
    while (y != 0)
    {
        r = x % y;
        x = y;
        y = r;
    }
    gcd = x;

    lcm = (a / gcd) * b;   /* same as a*b/gcd, avoids overflow */

    printf("GCD = %d\n", gcd);
    printf("LCM of %d and %d = %d\n", a, b, lcm);

    return 0;
}

Sample output (actual run):

Enter two positive integers: 12 18
GCD = 6
LCM of 12 and 18 = 36
Doubtly · 23 Apr 2022 Report
Was this answer helpful?

Answer: find the GCD by Euclid's method, then LCM = (a × b) / GCD.

#include <stdio.h>

int main() {
    int a, b, x, y, t, gcd, lcm;
    printf("Enter two positive integers: ");
    scanf("%d %d", &a, &b);

    x = a;
    y = b;
    while (y != 0) {     /* Euclid's algorithm */
        t = x % y;
        x = y;
        y = t;
    }
    gcd = x;
    lcm = (a / gcd) * b; /* same as a*b/gcd, less overflow */

    printf("LCM of %d and %d = %d\n", a, b, lcm);
    return 0;
}

Explanation: Euclid's algorithm replaces (x, y) by (y, x % y) until y becomes 0; then x is the GCD. Since GCD × LCM = a × b, we get the LCM directly.

Sample: a = 12, b = 18. GCD: (12, 18) → (18, 12) → (12, 6) → (6, 0), so GCD = 6 and LCM = 12/6 × 18 = 36.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.