1. GCD(Greatest Common Divisor) [최대공약수]

• 두 자연수의 공통된 약수 중 가장 큰 수를 의미함

• ex) 72와 30의 최대공약수는 6이다

• ex2) 10의 약수 = 1,2,5,10

• 14의 약수 = 1,2,7,14

• 공통되는 약수 = 1,2 ⇒ “2”가 큰 수 임

• 10과 15의 최대공약수는? 2가 되는 것임을 알 수 있음

• [예제]

  // 최대 공약수
  int gcdNumOne = 20;
  int gcdNumTwo = 30;
  
  int gcdMax = 0;
  
  while(gcdNumTwo != 0) {
  	gcdMax = gcdNumOne % gcdNumTwo;
  	gcdNumOne = gcdNumTwo;
  	gcdNumTwo = gcdMax;
  }
  
  // 최대공약수 결과
  System.out.println(gcdMax); // 10
  

2. LCM(Least Common Multiple) [최소공배수]

• 두 자연수의 공통된 배수 중 가장 작은 수를 의미함

• [공식] 최소 공배수 = 두 자연수의 곱 / 최대 공약수

• ex) 72와 30의 최소 공배수는 360이다

• ex2) 4의 배수 = 4,8,12,16,20,24, …

• 6의 배수 = 6,12,18,24,30,36,…

• 공통되는 배수 = 12, 24, … ⇒ “12”가 작은 수 임

• 4과 6의 최소공배수는? 12가 되는 것임을 알 수 있음

• [예제]

  // 최소 공배수
  
  int gcdNumOne = 20;
  int gcdNumTwo = 30;
  
  int gcdMax;
  int gcdMin = 0;
  
  // 값 gcdNumOne는 gcdNumTwo 보다 크거나 같은가?
  if(gcdNumOne >= gcdNumTwo) {
  	// True
  	gcdMax = gcdNumOne; // 20
  } else {
  	// False
  	gcdMax = gcdNumTwo; // 30
  }
  
  // for문으로 gcdMax으로 최소 공배수를 구함
  for (int i = gcdMax; i >= gcdMax; i++) {
  	// 값 gcdNumOne, gcdNumTwo를 비교하여 0과 같으면?
  	if (i % gcdNumOne == 0 && i % gcdNumTwo == 0) {
  			// gcdMin에게 현재 i의 값을 대입해주고
  			gcdMin = i;
  			// 종료함
  			break;
  	}
  }
  
  // 최소공배수 결과
  System.out.println(gcdMax); // 60
  

3. 유클리드 호제법(Euclidean Algorithm)

• 2개의 자연수를 받아 최대 공약수를 받기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나눠보면서 가장 큰 공약수를 구하는 것을 말함
• 즉 이 방법으로 문제를 풀면 시간복잡도는 **O(N)**이 됨