[BOJ] 유클리드 호제법

유클리드 호제법이란 두 정수의 최대공약수(GCD)를 구하는 알고리즘으로 나눗셈과 나머지 연산을 반복적으로 사용하여 최대공약수를 계산한다.

 

[백준] 2609 최대공양수와 최소공배수

https://www.acmicpc.net/problem/2609

 

 

일반적으로 최대공약수를 구하기 위해서는 소인수분해를 진행하여 구한다.

소인수분해 방법

 

import java.io.*;
import java.util.*;

public class Main {
  static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static int gcd(int n, int m){
    int answer = 1;
    int divisor = 2;

    while(divisor <= Math.min(n, m)){
      if(n % divisor == 0 && m % divisor == 0){
        n /= divisor;
        m /= divisor;
        answer *= divisor;
      } else {
        divisor ++;
      }
    }
    return answer;
  }

  public static void main(String [] args) throws IOException{
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    int gcd = gcd(n, m);
    int lcm = (n * m) * gcd;

    System.out.println(gcd);
    System.out.println(lcm);
  }
};

 

위와 같은 방법으로 최대공약수를 구하게 되면 수가 커질수록 효율성이 떨어진다. 유클리드 호제법을 사용하면 간결하면서도 효율적으로 최대공약수를 구할 수 있다.

 

유클리드 호제법

import java.io.*;
import java.util.*;

public class Main {
  static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static int gcd(int n, int m){

    while (m != 0) {
      int temp = n % m;
      n = m;
      m = temp;
    }

    return n;
  }

  public static void main(String [] args) throws IOException{
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    int gcd = gcd(n, m);
    int lcm = (n * m) * gcd;

    System.out.println(gcd);
    System.out.println(lcm);
  }
};

 

 

 

[ 프로그래머스 ] N개의 최소공배수

유사한 문제로 프로그래머스의 N개의 최소공배수 문제가 있다.

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

유클리드 호제법

class Solution {
    public int solution(int[] arr) {
        int lcm = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            lcm *= (arr[i] / gcd(lcm, arr[i]));
        }
        
        return lcm;
    }
    
    static int gcd(int n, int m){

        while (m != 0) {
          int temp = n % m;
          n = m;
          m = temp;
        }

        return n;
    }
}