java 13241번 최소공배수 (백준)

import java.util.Scanner;

public class Main {
	public static long gcd(long a, long b) { //유클리드 호제법
		long r = a%b;
		if(r==0) return b; //나머지가 0일 경우 최대공약수를 반환
		else return gcd(b, r); //몫과 나머지의 최대공약수를 찾으러 감
	}
	
	public static void main(String[] args) { 
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong();
		long m = scan.nextLong();
		long gcd = gcd(n, m); //최대공약수 구하기
		System.out.print(n*m/gcd); //최소공배수 * 최대공약수 = 두 수의 곱을 이용합니다.
	}
}

 

풀이 : 유클리드 호제법

 

1. 유클리드 호제법을 메서드로 구현합니다.

2. long type으로 두 정수를 입력받습니다.

3. 입력 받은 두 수로 최대공약수를 구합니다.

4. 최소 공배수 * 최대공약수 = 두 수의 곱 이므로, 최소 공배수는 = 두수의 곱 / 최대 공약수  입니다. 이를 출력하면 됩니다.

 

https://www.acmicpc.net/problem/13241

13241번: 최소공배수