[JAVA]유클리드 알고리즘(최대공약수 구하기)

개념

A와 B의 최대공약수를 구하는 알고리즘 중 하나이다. 요약하면 아래와 같다.

 

1. A를 B로 나눈 나머지를 구하여 R이라 한다.

2-1. 만약 R(나머지)이 0이라면 A와 B의 최대공약수는 B이다.

2-2. 아니라면 B를 R로 나눈 나머지를 구하고, 나머지가 0이 될 때까지 위 과정을 반복한다.

 

예시 코드

두 가지 방법으로 구현해 보았는데, 재귀함수를 이용하는 것이 조금 더 직관적인 것  같다.

코드를 실행하고, 두 수를 공백을 두고 입력하면 된다.(ex : 30 20 --> 10 출력)

 

1. 반복문(while)을 이용한 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int result = getG(A, B);
        System.out.println(result);
    }
    public static int getG(int A, int B) {
        while(B != 0) {
            int R = A % B; // 1. A를 B로 나눈 나머지를 구하여 R이라 한다.

            A = B;
            B = R; // R == 0이면 반복문이 끝난다.
        }
        return A; // 반복문이 끝날 시점의 나누는 수였던 B를 리턴한다.(23째줄에서 A에 B를 대입함)
    }
}

2. 재귀함수를 이용한 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int result = getG(A, B);
        System.out.println(result);
    }
    public static int getG(int A, int B) {
        int R = A % B; // 1. A를 B로 나눈 나머지를 구하여 R이라 한다.

        if(R == 0) return B; // 2-1. 만약 R(나머지)이 0이라면 A와 B의 최대공약수는 B이다.
        else return getG(B, R); // 2-2. 아니라면 B를 R로 나눈 나머지를 구하고, 나머지가 0이 될 때까지 위 과정을 반복한다.
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.

제가 이해한 내용을 간단히 요약하여 기록해 두고, 기억이 나지 않을 때마다 찾아보려는 목적으로 작성하는 글입니다.

따라서 설명이 부족할 수 있으니 양해 부탁드리고, 궁금한 부분이 있으시면 자유롭게 댓글 남겨주세요!