LCM of Two Numbers

PHOTO EMBED

Sun Feb 06 2022 04:00:19 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #euclidean #optimisedeuclidean #lcm

// Efficient Solution : Time Complexity : O(log(min(a,b)))
// a * b = gcd(a,b) * lcm(a,b)

import java.io.*;
import java.util.*;

public class Main {
	
	static int gcd(int a, int b)
	{
		if(b==0)
			return a;

		return gcd(b, a % b);
	}

	static int lcm(int a, int b)
	{
		return (a * b) / gcd(a, b); // constant no. of operations
	}
	
	public static void main (String[] args) {
		
		int a = 4, b = 6;

		System.out.println(lcm(a, b));

	}
}

// Naive Method : Time Complexity : O(a*b-max(a,b))


	static int lcm(int a, int b)
	{
		int res = Math.max(a,b);
		
		while(res > 0)
		{
		    if(res%a == 0 && res%b == 0)
		    {
		        return res;
		    }
		    res++;
		}
		return res;
	}
content_copyCOPY

Efficient Method: ------------------- a=4, b=6 gcd = 2 lcm = (4 * 6) / 2 = 12 Naive Method: ----------------- a=4, b=6 res=6 res=7 res=8 res=9 res=10 res=11 res=12