최대공약수, 최소공배수

유클리드 호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

• 서로소: 서로 공약수가 없는 수
• 공약수: 두 수의 공통된 약수
• 최대공약수: 공약수의 가장 큰 수
• 공배수: 두 수의 공통된 배수
• 최소공배수: 공배수의 가장 작은 수

최대공약수

int gcd(int a, int b){
  int c;
  while (b != 0){
    c = a % b;
    a = b;
    b = c;
  }
  return a;
}

최소공배수

int lcm(int a, int b){
	return a * b / gcd(a, b);
}