**Problem Statement:** Find lcm of two numbers.

**Examples:**

Example 1:Input:num1 = 4,num2 = 8Output:8Example 2:Input:num1 = 3,num2 = 6Output:6

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1:Brute force**

**Intuition: **Simply traverse from 1 to min(a,b) and check for every number.

**Approach**:

- Find gcd using brute force.
- Traverse from 1 to min(a,b).
- And check if i is divisible by both a and b.If yes store it in the answer.
- Find the maximum value of i which divides both a and b.
- To find lcm simply divide (a*b) by gcd of a and b.

**Code:**

## C++ Code

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a = 4, b = 8;
int gcd;
for (int i = 1; i <= min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
gcd = i;
}
}
int lcm = (a * b) / gcd;
cout <<"The LCM of the two given numbers is "<<lcm;
}
```

**Output:**

The LCM of the two given numbers is 8

**Time Complexity:** O(N).

**Space Complexity: **O(1).

## Java Code

```
public class Main {
public static void main(String args[]) {
int a = 4, b = 8;
int gcd = 1;
for (int i = 1; i <= Math.min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
gcd = i;
}
}
int lcm = (a * b) / gcd;
System.out.print("The LCM of the two given numbers is "+lcm);
}
}
```

**Output:**

The LCM of the two given numbers is 8

**Time Complexity:** O(N).

**Space Complexity: **O(1).

**Solution 2: Using Euclidean’s theorem.**

**Intuition: **Gcd is the greatest number which is divided by both a and b.If a number is divided by both a and b,** **it is should be divided by (a-b) and b as well.Using this we can find gcd in log(min(a,b)) and hence lcm.

**Approach:**

- First find gcd using euclidean’s algorithm,

- Recursively call gcd(b,a%b) function till the base condition is hit.
- b==0 is the base condition.When base condition is hit return a,as gcd(a,0) is equal to a.
- Once we get gcd,we can find lcm using formula lcm = (a*b)/gcd.

**Code:**

## C++ Code

```
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main()
{
int a = 4, b = 8;
int g = gcd(a, b);
int lcm = (a * b) / g;
cout <<"The LCM of the two given numbers is "<<lcm;
}
```

**Output:**

The LCM of the two given numbers is 8

**Time Complexity:** O(log_{ɸ}min(a,b)),where ɸ is 1.61.

**Space Complexity:** O(1).

## Java Code

```
public class Main {
static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static void main(String args[]) {
int a = 4, b = 8;
int gcd = gcd(a, b);
int lcm = (a * b) / gcd;
System.out.print("The LCM of the two given numbers is "+lcm);
}
}
```

**Output:**

The LCM of the two given numbers is 8

**Time Complexity:** O(log_{ɸ}min(a,b)),where ɸ is 1.61.

**Space Complexity:** O(1).

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article