[java] 두 수의 최대공약수 구하기 - 유클리드 알고리즘

 ▶ 최대공약수란 2개 이상의 수의 공약수 중에서 최대인 수를 말한다. 여기서는 두 수를 입력 받아서 최대공약수를 구하는 프로그램을 알아보겠습니다. 유클리드 알고리즘을 이용하여..


유클리드 알고리즘이란 간단히 말해서 두 개 자연수의 최대공약수를 계산하는 알고리즘 말한다. 
 1. b가 a로 나누어서 떨어지면 두 수의 최대공약수는 b이다.
 2. a를 b로 나누었을 때 나머지가 r이면, 두 수의 최대공약수는 r과 b의 최대공약수와 같다.

Ex5_7.txt

import java.util.Scanner;

public class Ex5_7 {

	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		int temp = 0;
		
		System.out.println("======= 최대공약수 =======");
		System.out.print("첫 번째 자연수 >> ");
		int a = s.nextInt();
		System.out.print("두 번째 자연수 >> ");
		int b = s.nextInt();
		
		while(a != 0) {
			if( a < b) {
				temp = a;
				a = b;
				b = temp;
			}
			a = a - b;
		}
		
		System.out.println("최대공약수: " + b);
	}
}

 첫 번째 수: 200, 두 번째 수: 60
 최대공약수: 20