Java | 재귀, 반복, Euclidean-Algorithm

유클리드 호제법 ?

유클리드 호제법은 두 수의 최대공약수(GCD)를 구하는 알고리즘이다.

두 수 A, B에 대하여 (A>B 라고 가정) A를 B로 나눈 나머지가 0이면 B, 아니면 나머지와 B의 최대공약수가 답이다

1. 만일 A < B이면, A와 B를 바꾼다.
2. A % B(나머지)를 계산한다.
3. 만일 나머지가 0이면 B를 출력하고 끝난다.
4. 아니면 B와 나머지 중 큰 수를 A, 작은 수를 B에 저장한다.
5. 2번 부터 반복한다.

두 수 503과 56이 있다고 가정

2. 1520 % 36 = 8
4. A = 36, B = 8
2. 36 % 8 = 4
4. A = 8, B = 4
2. 8 % 4 = 0

: 4 출력

---

코드

반복문

	static int GCD(int A, int B) {
		int temp, r;
		if (A < B) { // A에 큰 값 넣기
			temp = A;
			A = B;
			B = temp;
		}

		while (B != 0) { // B가 0이 될 때 까지
			r = A % B;
			A = B;
			B = r; // 나머지, B가 0일 때 리턴
		}
		return A;

	}

		

재귀함수

	static int RecursionGCD(int A, int B) {
		if (A < B) {
			int temp = A;
			A = B;
			B = temp;
		}
		int r = A % B;
		if (r == 0)
			return B;
		else
			return RecursionGCD(B, r);
	}