최대 공약수(GCD), 최소 공배수(LCM) 구하기, 유클리드 호제법 - JAVA

최대 공약수와 최대 공배수의 개념

1) 공약수

두 정수의 공통 약수를 공약수라고 한다.
두 정수 a, b에 대하여 e가 a의 약수이면서 b의 약수일 때 e를 a, b의 공약수라고 한다.

2) 최대공약수

두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다.
또한 최대공약수는 다음의 성질을 만족한다.
a, b의 최대공약수가 g이다. ⇔ a = ga′, b = gb′이면 a′, b′는 서로소이다.

3) 공배수

두 정수의 공통 배수를 공배수라고 한다.
두 정수 a, b에 대하여 c가 a의 배수이면서 b의 배수일 때 c를 a, b의 공배수라고 한다.

4) 최소공배수

양의 공배수 중 가장 작은 것을 최소공배수라고 한다.

[네이버 지식백과] 최대공약수와 최소공배수 (통합논술 개념어 사전, 2007. 12. 15., 한림학사)

 

코드

내가 이것을 보고 생각했을 때 짠 코드이다.

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int num1 = 1250;
		int num2 = 80;
        	int g = gcd(num1, num2, num2);
        	int l = (num1*num2)/g;
		System.out.println("1250과 80의 GCD : "+g);
		System.out.println("1250과 80의 LCM : "+l);
	}
    public static int gcd(int num1, int num2, int n)
    {
        if(num1%n == 0 && num2%n == 0)
        {
            return n;
        }
        return gcd(num1, num2, n-1);
    }
}

 

유클리드 호제법

정의

두 양의 정수 A, B (A > B)에 대하여 A = BQ + R (0 ≤ R < B)이라 하면,

A, B의 최대 공약수는 B, R의 최대 공약수와 같다.

즉, gcd(A, B) = gcd(B, R)

R = 0이라면, A, B의 최대 공약수는 B가 된다.

여기서  Q = A/B(A를 B로 나눈 몫), R = A%B (나머지) 이다.

 

예시

 1250과 580의 최대공약수를 구하라.

• A = B X Q + R
• 1250 = 580 X 2 + 90
• 580 = 90 X 6 + 40
• 90 = 40 X 2 + 10
• 40 = 10 X 4

4번째에서 R = 0 가 되니까, 직전의 R 인 10이 1250과 580의 최대공약수가 됩니다.

 

코드

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int num1 = 1250;
		int num2 = 80;
        	int g = gcd(num1, num2);
        	int l = (num1*num2)/g;
		System.out.println("1250과 80의 GCD : "+g);
		System.out.println("1250과 80의 LCM : "+l);
	}
    public static int gcd(int num1, int num2)
    {
        if(num1%num2 == 0)
        {
            return num2;
        }
        return gcd(num2, num1%num2);
    }
}

다음에 또 봐요