#2609 : 최대공약수와 최소공배수

풀이방법

사용된 것:

수학

 

2022.04.17

간단한 수학 문제이다.

 

최대공약수를 구하는 방법은 다음과 같다.

주어진 두 수 중 작은 쪽의 약수를 모두 구하여, 가장 작은 약수부터 큰 약수까지의 순으로 스택에 넣는다.

스택의 top부터 하나씩 꺼내면서, 즉 가장 큰 약수부터 작은 약수까지의 순서로 꺼내면서

해당 수가 주어진 두 수 중 큰 쪽의 약수인지 확인한다.

주어진 두 수 중 큰 쪽의 약수인 수가 발견되면 즉시 그 수를 최대공약수로 취하고 반복문을 종료한다.

 

최소공배수를 구하는 방법은 다음과 같다.

주어진 두 수 중 작은 쪽에

2, 3, 4, ... 갈수록 1씩 큰 자연수를 곱해가면서

곱의 결과값이 주어진 두 수 중 큰 쪽의 배수인지 확인한다.

주어진 두 수 중 큰 쪽의 배수인 수가 발견되면 즉시 그 수를 최소공배수로 취하고 반복문을 종료한다.

 

 

코드

Java(2022.04.17)

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[2];
		arr[0] = sc.nextInt();
		arr[1] = sc.nextInt();
		
		Arrays.sort(arr);
		
		int a = -1;	//최대공약수
		int b = -1;	//최소공배수
		
		if(arr[1] % arr[0] == 0) {
			System.out.println(arr[0]);
			System.out.println(arr[1]);
			System.exit(0);
		}
		
		//최대공약수 구하기
		//두 수 중 작은 쪽의 약수를 모두 구해놓기
		Stack<Integer> stack = new Stack<Integer>();
		for(int i = 1; i<arr[0]; i++) {
			if(arr[0]%i == 0) stack.add(i);
		}
		//큰 약수부터 시작하여, 두 수 중 큰 쪽의 약수인지 확인
		while(!stack.isEmpty()) {
			if(arr[1] % stack.peek() != 0) stack.pop();
			else {
				//공약수가 발견되면 즉시 a의 값 확정 및 반복문 종료
				a = stack.pop(); break;
			}
		}
		
		//최대공배수 구하기
		int num = 1;
		while(true) {
			num++;	//num은 2에서부터 시작하여 1씩 증가함
			//temp는 주어진 두 수 중 작은 쪽의 num배수
			int temp = num * arr[0];
			//temp가 주어진 두 수 중 큰 쪽의 배수인지 확인
			if(temp<arr[1]) continue;
			else if(temp % arr[1] == 0) {
				//공배수가 발견되면 즉시 b의 값 확정 및 반복문 종료
				b = temp; break;
			}
		}
		
		//정답 출력
		System.out.println(a);
		System.out.println(b);
	}

}