[백준] 최대공약수와 최소공배수 (2609)(java)

원본 문제 : https://www.acmicpc.net/problem/2609

참고 풀이 : https://itpangpang.xyz/131

 

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6

72

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int val1 = sc.nextInt();
		int val2 = sc.nextInt();

		int bigger = val1, smaller = val2;
	
		if(val1<val2) {		//입력 받은 두 수 중 큰 수를 bigger에 저장
			bigger = val2;
			smaller = val1;
		}
		
		int r = bigger*smaller;	//루프문의 조건을 만족하기 위해 r(나머지값)은 최대값
		while(r>0) {			//유클리드 호제법으로 최대공약수를 구함
			r = bigger % smaller;	//큰 수를 작은 수로 나눈 나머지값을 저장
			bigger = smaller;		//큰 수에 작은 수를 대입
			smaller = r;			//작은 수에 나머지 값을 대입
		}

		System.out.println(bigger);	//최대공약수 출력
		System.out.println((val1*val2)/bigger);	//최소공배수 출력
        //입력 받은 두 수를 곱한 뒤 최대공약수로 나누면 최소공배수가 됨
	}
}