[Algorithm] 자바/ 최대공약수, 최소공배수 - 유클리드 호제법

유클리드 호제법이란 2개의 자연수를 받아 최대공약수를 구하기 위해 2부터 두 자연수 중 가장 작은 자연수까지 나누어 최대공약수를 구하는 방법이다. 

이를 이용하여 최대공약수 구하는 알고리즘을 정리하고자 한다.  

 

public static void main(String[] args){
	int a = sc.nextInt();
	int b = sc.nextInt();
    
	int gcd = gcd(a,b); // 최대공약수
	int d = (a*b/gcd); // 최소공배수
    
}

public static int gcd(int a, int b){
	if(b == 0) return a;
	// GCD(a,b) = GCD(b, r) r = a% b
	return gcd(b, a%b);
}

 

- 백준 2609번

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

2609번: 최대공약수와 최소공배수

 

 

추가

- 문제들을 풀다보니 두 수에 대한 최대공약수, 최소공배수 뿐만 아니라 숫자 3개 이상에 대한 최대공약수와 최소공배수를 구하라는 문제들을 만났다. 그럴 경우, 앞의 두 수에 대한 값들을 먼저 구하고, 배열 끝까지 반복하여 값을 구하면 된다.

class Solution{
	public int solution(int[] arr){
    	int answer =0;
        
        // 앞에 두 원소에 대한 최대공약수와 최소공배수를 먼저 구한다.
        int gcd = gcd(arr[0], arr[1]);       // 최대공약수
        int answer = (arr[0] * arr[1])/gcd   // 최소공배수
        
        if(arr.length>2){
          for(int i=2; i<arr.length; i++){
          	gcd = gcd(answer, arr[i]);
            answer = (answer * arr[i])/gcd;
          }
        }
        
        return answer;
    }
    
    public static int gcd(int a, int b){
    	if(b == 0) return a;
        return gcd(b, a%b);
    }
}

 

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=java 

프로그래머스