C Exercises: Find the LCM of two numbers

C Recursion: Exercise-13 with Solution

Write a program in C to find the LCM of two numbers using recursion.

Pictorial Presentation:

Sample Solution:

C Code:

#include <stdio.h>
int lcmCalculate(int a, int b);
 
int main()
{
    int n1, n2, lcmOf;
	printf("\n\n Recursion : Find the LCM of two numbers :\n");
	printf("----------------------------------------------\n");
    printf(" Input 1st number for LCM : ");
    scanf("%d", &n1);
    printf(" Input 2nd number for LCM : ");
    scanf("%d", &n2);
// Ensures that first parameter of lcm must be smaller than 2nd
    if(n1 >  n2)
        lcmOf = lcmCalculate(n2, n1);//call the function lcmCalculate for lcm calculation
    else
        lcmOf = lcmCalculate(n1, n2);//call the function lcmCalculate for lcm calculation
    printf(" The LCM of %d and %d :  %d\n\n", n1, n2, lcmOf);
    return 0;
}
int lcmCalculate(int a, int b)//the value of n1 and n2 is passing through a and b
{
    static int m = 0;
    //Increments m by adding max value to it
    m += b;
//  If found a common multiple then return the m.
    if((m % a == 0) && (m % b == 0))
    {
        return m;
    }
    else
    {
        lcmCalculate(a, b);//calling the function lcmCalculate itself
    }
}

Sample Output:

 Recursion : Find the LCM of two numbers :                                                                    
----------------------------------------------                                                                
 Input 1st number for LCM : 4                                                                                 
 Input 2nd number for LCM : 6                                                                                 
 The LCM of 4 and 6 :  12 

Explanation:

int lcmCalculate(int a, int b)//the value of n1 and n2 is passing through a and b
{
    static int m = 0;
    //Increments m by adding max value to it
    m += b;
//  If found a common multiple then return the m.
    if((m % a == 0) && (m % b == 0))
    {
        return m;
    }
    else
    {
        lcmCalculate(a, b);//calling the function lcmCalculate itself
    }
}

This function lcmCalculate() calculates the least common multiple (LCM) of two numbers. It takes two integers ‘a’ and ‘b’ as input and calculates the LCM of these two numbers using recursion.

The function starts by initializing a static variable m to zero. It then increments m by adding the value of b to it. This is done repeatedly until a common multiple of a and b is found.

Once a common multiple is found, the function returns the value of m as the LCM. If a common multiple is not found, the function calls itself recursively to continue the search for a common multiple.

Time complexity and space complexity:

The time complexity of this function is O(a*b), where a and b are the two input numbers.

The space complexity is O(1), as the function uses a static variable to store the value of m.

Flowchart:

C Programming Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a program in C to check a number is a prime number or not using recursion.
Next: Write a program in C to print even or odd numbers in given range using recursion.