백준 2609번 : 최대공약수와 최소공배수(Java)

4523 단어 백준백준

유클리드 호제법이라는 알고리즘을 사용하여 최대공약수를 구하고, 최대공약수를 사용해 최대공배수를 구하는 문제였습니다.

import java.util.Scanner;
 
public class p2609 {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		int b = in.nextInt();
 
		int d = gcd(a, b);	// 최대공약수
		
		// 최대공약수 출력
		System.out.println(d);
		// 최대공배수 출력
		System.out.println(a * b / d);
 
	}
	
	// 최대공약수 반복문 방식
	// 유클리드호제법
	public static int gcd(int a, int b) {
 
		while (b != 0) {
			int r = a % b; // 나머지를 구해준다.
 
			// GCD(a, b) = GCD(b, r)이므로 변환한다.
			a = b;
			b = r;
		}
		return a;
	}
}

좋은 웹페이지 즐겨찾기