[JAVA] 백준 13241 최소공배수

13241번: 최소공배수 (acmicpc.net)

13241번: 최소공배수

 

풀이 과정 

 

- 유클리드 호제법으로 풀이 

 

유클리드 호제법 

 

유클리드 호제법 (개념 이해하기) | 모듈로 연산 | Khan Academy

 

- 두 개의 자연수가 주어졌을 때 최대공약수(GCD)를 구하는 알고리즘 

- 재귀적인 방법을 활용하여 동작

- 두 수를 서로 나누고 나머지를 계산하여 나머지가 0이 될 때까지 반복 

 

- 두 정수 a 와 b의 최대 공약수 GCD(a,b)를 찾을 때, b가 0이 될 때까지 a를 b로 나눈 나머지를 계산 

- 나머지가 0이 되면 그때의 b가 GCD(a,b) 

 

최대 공약수 GCD(Greatest Common Divisior)

 

- 두 자연수의 공통된 약수 중 가장 큰 수 

 

최소 공배수 LCM(Least Common Multiple)

 

- 두 자연수의 공통된 배수 중 가장 작은 수 

- 최소 공배수 = 두 자연수의 곱 / 최대 공약수 

 

- A와 B의 최대 공약수는 A를 B로 나눈 나머지가 r 일 때 B와 r의 최대 공약수와 같다 

 

//최대공약수 
public static int gcd(int a, int b)
{
	if(b==0) {
    	return a;
    }
    else
    {
    	return gcd(b,a%b);
    }
}

 

 

//최소공배수 
public static int lcm(int a, int b)
{
 	int gcd = gcd(a,b);
    return (a*b) /gcd;
}

 

 

정답 

 

import java.util.Scanner;

public class Main {
    //최대 공약수 
    public static long gcd(long a, long b)
    {
        if(b==0)
        {
            return a;
        }
        else
        {
            return gcd(b,a%b);
        }
    }
    
    //최소 공배수 
    public static long lcm(long a, long b)
    {
        long gcd = gcd(a,b);
        return (a*b)/gcd;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        long a = sc.nextLong();
        long b = sc.nextLong();
        
        System.out.println(lcm(a,b));
       

    }
}