1002 최대공약수 최소공배수

최대공약수와 최소공배수를 구하는공식은 누구나 알고있을것이다. 하지만 코드에서는 단순히 2개의 숫자를 다루는것이 아닌 3개이상의 숫자들의 최대공약수랑 최소공배수를 구하는부분인데 

... 어렵다..

 

푸는공식은 다음과 같다

 

두 개의 수 A와 B의 최대공약수를 D라 하면, 세 개의 수 A, B, C의 최대공약수는 D와 C의 최대공약수와 같다.

이런 규칙을 이용하면 두 수의 최대공약수를 구하는 함수 한 개만으로도 여러 수의 최대공약수를 구할 수 있다

그리고 최소공배수는 A와 B의 곱을 최대공약수로 나누어주면되서 로직을 짜는것은 그렇게 어렵지 않았다. 코드는 다음과 같다.

 

import java.util.Arrays;
import java.util.Scanner;


public class O1002 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String c = sc.nextLine();
		String[] num = sc.nextLine().split(" ");
		int arr[] = new int[num.length];
		int GCD = 0;
		for (int i = 0; i < num.length; i++) {
			arr[i] = Integer.parseInt(num[i]);
		}
		
		for (int i = 0; i < arr.length; i++) {
			if(i == 0) {
				GGC ggc = new GGC(arr[i], arr[i+1]);
				GCD = ggc.getAnswer();
			}else if(i >= 2){
				GGC ggc = new GGC(GCD, arr[i]);
				GCD = ggc.getAnswer();
			}
		}
		
		int result = 0;
		int GCD2 = 0;
		
		for (int i = 0; i < arr.length; i++) {
			if(i == 0) {
				GGC ggc = new GGC(arr[i], arr[i+1]);
				GCD2 = ggc.getAnswer();
				result = arr[i] * arr[i+1] / GCD2;
			}else if(i >= 2){
				GGC ggc = new GGC(result, arr[i]);
				GCD2 = ggc.getAnswer();
				result = result * arr[i] / GCD2;
			}
		}System.out.println(GCD + " " + result);
		
	}
}

class GGC{
	int num;
	int num2;
	int answer;
	GGC(){}
	GGC(int num, int num2){
		this.num = num;
		this.num2 = num2;
		int num3 = (num > num2)? num:num2;
		for (int i = 1; i <= num3; i++) {
			if(num % i == 0 && num2 % i == 0) {
				answer = i;
			}
		}
	}
	public int getAnswer() {
		return answer;
	}
	public void setAnswer(int answer) {
		this.answer = answer;
	}
	
}

오류가 발생했었는데 최소공배수의 최소공배수를 구하는것을 몰라서 다시 로직을 짰다. 

1. 일단 최대공약수를 구해준다

2. result로 초기화시켜줘서 최소공배수를 구해준다

3. 강제로 최소공배수를 구해주고 다시 GGC클래스에 넣어주고 GCD에 다시 넣어준다. 이걸 배열이 끝날때 까지반복시키면 끗~