최대공약수(유클리드 호제법), 최소공배수

최대 공약수란?

-> 공약수란 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 공약수 중 가장 큰 것 gcd(a,b) 또는 (a,b)로 표기하며 gcd(a,b) = 1이면 두 수 a,b는 서로소라고 한다.

유클리드 호제법이란?

-> a, b, q, r이 정수라고 가정할 때
a = b * q + r -> a와b의 최대공약수는 b와 r의 최대공약수와 같다라는것이 유클리드 호제법입니다.

최대 공약수 java 구현 예제

class EuclidGCD{

  public int gcdResult(int x, int y){
      if(x<y){
          int temp = x;
          x = y;
          y = temp;
      }

      return gcd(x,y);
  }

  public int gcd(int x, int y){
      if(y==0)
          return y;

      return gcd(y, x%y);
  }
}

최소공배수란?

-> 공배수란 두 수 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수는 공배수 중에서 가장 작은 것, 두 수 a,b의 최소공배수를 기호로 lcm(a,b) 또는 [a,b]로 표기한다.

최소공배수 구하는법

최소공배수 = 두수의 곱 / 두수의 최대공약수

최대 공약수 java 구현 예제

class LcmEx{

  public int lcmResult(int x, int y){
      if(x<y){
          int temp = x;
          x = y;
          y = temp;
      }

      return lcm(x,y);
  }
  
  public int lcm(int x, int y){
  	return x * y / gcd(x, y);
  }

  public int gcd(int x, int y){
      if(y==0)
          return y;

      return gcd(y, x%y);
  }
}