백준 2609번

최대공약수와 최소공배수

문제

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

입력

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

출력

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

풀이

우선 두가지 경우로 나눴는데, 처음 입력한 두 수 중 첫번째 수가 큰 경우, 두번째 수가 큰 경우로 나눴다.

각 경우에서 최대공약수는 변수 i를 1부터 두 수중 작은 수까지 증가시키면서 두 수를 i로 나눴을때 나머지가 둘다 0이 나오는 경우를 구했다.
공약수 중 최대값이기 때문에 i를 끝까지 더하면서 max에 중복으로 할당했다.
마지막에 할당된 값이 최대공약수이다.

최소공배수는 변수 k를 두 수중 큰 수 부터 증가시키면서 k를 두 수로 나눴을때 나머지가 0이 나오는 경우를 min에 할당한다.
공배수 중 최소값을 구해야 하므로 처음 할당한 순간 break로 반복문을 탈출하게 했다.
처음 할당된 값이 최소 공배수이다.

코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num1 = sc.nextInt();
		int num2 = sc.nextInt();
		
		sc.close();
		
		int max = 0;
		int min = 0;
		int k = 0;
		
		if(num1 >= num2) {
			for(int i=1; i<=num2; i++) {
				if(((num1 % i) == 0) && ((num2 % i) == 0))
					max = i;
			}
			
			k = num1;
			while(true) {
				if(((k % num1) == 0) && ((k % num2) == 0)) {
					min = k;
					break;
				}
				k++;
			}
		}
		else {
			for(int i=1; i<=num1; i++) {
				if(((num1 % i) == 0) && ((num2 % i) == 0))
					max = i;
			}
			
			k = num2;
			while(true) {
				if(((k % num1) == 0) && ((k % num2) == 0)) {
					min = k;
					break;
				}
				k++;
			}
		}
		
		System.out.println(max);
		System.out.println(min);	
	}
}