[알고리즘][GCD] 재귀를 이용한 유클리드 호제법

[알고리즘][GCD] 재귀를 이용한 유클리드 호제법

• GCD (Greatest Common Divisor) ; 최대공약수
• A와 B의 공통된 약수 중 가장 큰 정수
• 최대 공약수가 1인 두 수를 서로소
• 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법 = 가장 쉬운 방법
• 유클리드 호제법 = 가장 빠른 방법

• 유클리드 호제법
• int a, b 와 나머지 r
• GCD(a, b) = GCD(b, r)
• r이 0이면 그 때의 b가 최대공약수 이다.
• EX > GCD(42, 24) = GCD(24, 18) = GCD(18, 6) = GCD(6, 0) = 6

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
public class gcd_01 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num1 = scan.nextInt();
        int num2 = scan.nextInt();
        System.out.println(calc(num1, num2));
        
    }
 
    public static int calc(int num1, int num2) {
        if(num1<num2) {
            int tmp = num1;
            num1=num2;
            num2=num1;
        }
        int ans=num1%num2;
        if(ans==0) {
            return num2;
            
        }
        return calc(num2, ans);
    }
}