107. 2609(최대공약수와 최소공배수)

import java.util.*;
import java.io.*;

class Main{
	public static void main(String args[])throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sBits = br.readLine().split(" ");
		int x = Integer.parseInt(sBits[0]);
		int y = Integer.parseInt(sBits[1]);
		
		System.out.println(gcd(x,y));
		System.out.println(lcm(x,y));
	
	}
	
	static int gcd(int x, int y) {
		while(y!=0) {
			int r = x%y;
			x = y;
			y = r;
		}
		return x;
	}
	
	static int lcm(int x, int y) {
		return x * y / gcd(x,y);
	}
}

문제요약

최대공약수와 최소공배수를 구하는 문제

설명

gcd => 최대 공약수

lcm => 최소 공배수

 

최대공약수는 x % y 를 진행하다가 0이나올 때 x의 값이 최대 공약수이다.

예를 들어 24 18이 들어오면,

1)

24 % 18 = 6 = r

x = 18

y = 6

 

2) 18 % 6 = 0 = r

x = 6

y = 0

 

y가 0이 되었으므로 x값을 리턴한다.

 

최소 공배수는 x와 y를 곱한 값에서 최대공약수로 나누어지면 값이 나온다.