[알고리즘] 유클리드 호제법

💡 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘

 

• 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법 → 최대공약수
• 최대 공약수
  • 두 수의 공통된 “약수 중에서 가장 큰 수”
    • 재귀 방식

          // 재귀 방식
      public static int gcd(int a, int b) {
          if (b == 0) return a;
          return gcd(b, a % b);
      }

    • 반복문 방식

      // 반복문 방식
      public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
      }

• 최소 공배수
  • 두 수의 공통된 “배수 중에서 가장 작은 수”

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

• 약수 구하기

int n = 12; // 약수를 구할 수
for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
        System.out.println(i);
    }
}