백준 - 2609번 - 최대공약수와 최소공배수

2609번

#1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());

		System.out.println(solve1(A, B));
		System.out.println(solve2(A, B));

	}

	static int solve1 (int A, int B) {
		int N = 1;
		for (int i = 2; i<=10000; i++) {
			while (true) {
				if (A%i==0 && B%i==0) {
					A = A/i;
					B = B/i;
					N *= i;
				} else {
					break;
				}
			}
		}

		return N;
	}

	static int solve2 (int A, int B) {
		int M = 1;
		for (int i = 2; i<=10000; i++) {
			while (true) {
				if (A%i==0 && B%i==0) {
					A = A/i;
					B = B/i;
					M *= i;
				} else {
					break;
				}
			}
		}
		M = M * A * B;

		return M;
	}
}

#2 GCD(a, b) 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
 
		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;
	}
}

풀이

---

최대공약수와 최소공배수를 구하는 메서드를 각각만들었다.

주어진 두수가 10000이하이므로 나눠주는 수를 2부터 10000까지 반복문을 돌렸다. 다만 같은 수로 계속 나눠지는 경우를 내부에 while문으로 구현했다.

GCD(a, b) 유클리드 호제법 (Euclidean algorithm) 방법으로 #2과 같이 간단한 방법으로 풀 수 있다.
유클리드 호제법 참고 사이트