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

두 수 A,B가 있다고 하자. 둘의 최대공약수를 G라고 하면

A = G*a

B = G*b 

로 표현할 수 있다.

그리고 

A - B = G*(a-b) 이므로

A와 B의 최대공약수는 A-B와의 최대공약수이기도 하다.

이 원리를 이용해서

62와 28의 최대공약수를 구해보면

(62, 28)

(34, 28)

(6, 28)

(6, 22)

(6, 16)

(6, 10)

(6, 4)

(2, 4)

(2, 2)

(0, 2) 0이 나오면 종료. 최대공약수는 2

그러나 이 방식을 프로그램으로 구현하면 큰 차이가 나는 수들은 루프를 비교적 많이 돌게 된다.

이를 개선시켜 여러번의 뺄셈을 나눗셈으로 줄여 계산하는 방법이 있다.

(62, 28)

62 % 28 = 6   -->   (28, 6)

28 % 6 = 4   -->   (6, 4)

6 % 4 = 2   -->   (4,2)

4 % 2 = 2   -->   (2,2)

2 % 2 = 0   -->   (2,0) 종료

이렇게 하면 연산 수를 많이 줄일 수 있다.

import java.util.Scanner;

public class exercise3_4 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n1, n2, gcd;

        System.out.print("두 수를 입력하시오>>");

        n1 = sc.nextInt();
        n2 = sc.nextInt();

        while (true) {
            if (n1 < n2) {
                int swapTemp = n1;
                n1 = n2;
                n2 = swapTemp;
            }
            n1 = n1 % n2;
            if (n1 == 0) {
                gcd = n2;
                break;
            } else
                continue;
        }
        System.out.println("두 수의 최대공약수는 " + gcd + " 입니다.");
    }

}