Find the Least Common Multiple (LCM) in C

Introduction

In this lab, you will learn how to find the Least Common Multiple (LCM) of two integers using C programming. The lab covers the step-by-step process, starting with reading two integers from user input, then implementing the formula LCM = (a*b)/GCD(a,b) to calculate the LCM, and finally printing the result. By the end of this lab, you will have a solid understanding of how to apply number theory concepts, such as the Euclidean algorithm for finding the Greatest Common Divisor (GCD), to solve practical problems in C.

Skills Graph

Read Two Integers

In this step, you will learn how to read two integers from user input in C programming, which is the first step in calculating the Least Common Multiple (LCM).

First, let's create a new C file for our LCM program:

cd ~/project
nano lcm.c

Now, add the following code to read two integers:

#include <stdio.h>

int main() {
    int a, b;

    printf("Enter two positive integers:\n");
    printf("First number: ");
    scanf("%d", &a);

    printf("Second number: ");
    scanf("%d", &b);

    printf("You entered: %d and %d\n", a, b);

    return 0;
}

Compile and run the program:

gcc lcm.c -o lcm
./lcm

Example output:

Enter two positive integers:
First number: 12
Second number: 18
You entered: 12 and 18

Let's break down the code:

• scanf() function is used to read integer input from the user
• %d format specifier is used for integer input
• &a and &b pass the memory addresses where the input values will be stored

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

In this step, you will implement the Least Common Multiple (LCM) calculation using the formula LCM(a,b) = (a*b)/GCD(a,b). We'll first create a function to calculate the Greatest Common Divisor (GCD) using the Euclidean algorithm.

Update the lcm.c file with the following code:

#include <stdio.h>

// Function to calculate GCD using Euclidean algorithm
int calculateGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Function to calculate LCM
int calculateLCM(int a, int b) {
    return (a * b) / calculateGCD(a, b);
}

int main() {
    int a, b, lcm;

    printf("Enter two positive integers:\n");
    printf("First number: ");
    scanf("%d", &a);

    printf("Second number: ");
    scanf("%d", &b);

    lcm = calculateLCM(a, b);

    printf("The Least Common Multiple of %d and %d is: %d\n", a, b, lcm);

    return 0;
}

Compile and run the program:

gcc lcm.c -o lcm
./lcm

Example output:

Enter two positive integers:
First number: 12
Second number: 18
The Least Common Multiple of 12 and 18 is: 36

Let's break down the key components:

• calculateGCD() implements the Euclidean algorithm to find the Greatest Common Divisor
• calculateLCM() uses the formula LCM(a,b) = (a*b)/GCD(a,b)
• The Euclidean algorithm efficiently finds GCD by repeatedly taking the remainder

Print the LCM

In this final step, you will run the LCM program and verify its output for different input combinations. We'll test the program with various integer pairs to demonstrate the LCM calculation.

Compile the program (if not already compiled):

cd ~/project
gcc lcm.c -o lcm

Run the program with different input combinations:

./lcm << EOF
12
18
EOF

Example output for 12 and 18:

Enter two positive integers:
First number: 12
Second number: 18
The Least Common Multiple of 12 and 18 is: 36

Let's try another example:

./lcm << EOF
15
25
EOF

Example output for 15 and 25:

Enter two positive integers:
First number: 15
Second number: 25
The Least Common Multiple of 15 and 25 is: 75

Key points to understand:

• The LCM is the smallest positive integer that is divisible by both input numbers
• For 12 and 18, the LCM is 36
• For 15 and 25, the LCM is 75
• The program uses the formula LCM(a,b) = (a*b)/GCD(a,b)

To make the program more robust, you can add input validation:

nano lcm.c

Update the main() function to include input validation:

int main() {
    int a, b, lcm;

    printf("Enter two positive integers:\n");
    printf("First number: ");
    scanf("%d", &a);

    printf("Second number: ");
    scanf("%d", &b);

    // Input validation
    if (a <= 0 || b <= 0) {
        printf("Error: Please enter positive integers only.\n");
        return 1;
    }

    lcm = calculateLCM(a, b);

    printf("The Least Common Multiple of %d and %d is: %d\n", a, b, lcm);

    return 0;
}

Recompile and test the updated program:

gcc lcm.c -o lcm
./lcm

Summary

In this lab, you will learn how to find the Least Common Multiple (LCM) of two integers in C programming. First, you will read two integers from user input. Then, you will implement the formula LCM(a,b) = (a*b)/GCD(a,b) by creating a function to calculate the Greatest Common Divisor (GCD) using the Euclidean algorithm. Finally, you will print the calculated LCM.

The key learning points are: reading integer input using scanf(), implementing the Euclidean algorithm to find the GCD, and using the formula to calculate the LCM. By the end of this lab, you will have a solid understanding of how to find the LCM of two numbers in C.