최대 최소 공약수

최대공약수

• 두 수 A,B의 공통 약수 중 가장 큰 정수

• 2부터 min(A,B) 까지 계속 나누기

  • A, B의 약수가 두 수 보다 클 수 없기 때문에. A,B중 가장 작은수까지만 계산.

// x,y가 약수로 나눠지기 때문에 계속 작아진다.
 while(mod <= min(x, y)) {
  if(x % mod == 0 && y % mod == 0) {
      modList.push_back(mod);

      x /= mod;
      y /= mod;

  } else {
      mod += 1;
  }
}

최소 공배수

• 두 수 A,B의 공통 배수 중 가장 작은 정수

• 최대 공약수가 g일 때, g(A/g)(B/g)가 최소공약수