[Java] 자바 최대공약수 최소공배수 구하는법!/ 빠르게 구해보자!

2020-09-05

---

최소공배수 정의

 

수론에서, 여러 개의 정수/다항식/환의 원소의 공배수(公倍數, 영어: common multiple)는

그들 모두의 배수가 되는 정수/다항식/환의 원소이다. 

최소공배수(最小公倍數, 영어: least common multiple/ lowest common multiple, 약자 LCM)는

양의 공배수 가운데 가장 작은 하나이다. 

유클리드 정역에서 0으로 나누기를 정의하지 않으므로,

이 정의는 오직 다루고자 하는 정수들이 0이 아닐 때 의미가 있다. 

 

최대공약수 정의

 

수론에서, 정수들의 공약수(公約數, 영어: common divisor)는

동시에 그들 모두의 약수인 정수다.

적어도 하나가 0이 아닌 정수들의 최대공약수

(最大公約數, 문화어: 련속나눔셈; 영어: greatest common divisor, 약자 GCD)는

공약수 가운데 가장 큰 하나다. 

다항식이나 환의 원소에 대해서도 정의할 수 있다.

 

출처: 위키피디아

---

소스코드

※풀이

 

구하고자 하는 두 수중 큰 수에서 작은 수를 나누어주고, 

이후 큰 수는 작은 수가 되고, 작은 수는 둘을 나눈 나머지가 된다.

나머지가 없을 때 까지 해당 작업을 반복한다.

해당 시점에서의 작은 수가 최대공약수가 되며,

처음에 주어진 두 수를 곱한 후 최대공약수로 나누면,

해당 수가 최대공배수가 된다.

 

 

ex) 10 , 8  → 10이 큰 수 8이 작은 수

 둘을 나눈 후 큰 수 8 작은 수 나머지 값 2

이후 나머지 0이 될때 까지 반복

		int a = scan.nextInt();
		int b = scan.nextInt();
		//입력될 두 수
		
		int big, small;
		//두 수 중 큰 수와 작은 수가 저장될 변수
		
		int mok, nmg;
		//몫과 나머지가 저장될 변수
		
		int	minM, maxD ;
		//최소공배수와 최대공약수가 저장될 변수
		
		
		if(a >= b) {
			big = a;
			small = b;
		}else {
			big = b;
			small = a;
		}
		
		while(true) {
			mok = big / small;
			nmg = big - mok * small;
				if(nmg == 0) {
					maxD = small;
					minM = a * b / maxD;
					System.out.println(maxD + "  " + minM);
					break;
				}else {
					big = small;
					small = nmg;
				}
		
		
		}