[정수론] 유클리드 호제법

유클리드 호제법

유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다.

 

유클리드 호제법의 핵심이론

유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야한다. MOD연산이 최대 공약수를 구하는 데 핵심 연산이기 때문이다.

 

MOD 연산으로 구현하는 유클리드 호제법

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.

2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.

3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

 

 

 

 

예제 1

 

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int result = a * b / gcd(a,b);
            System.out.println(result);
        }
    }

    public static int gcd(int a, int b) {
        if(b==0) {
            return a;
        }
        else {
            return gcd(b, a%b);
        }
    }
}

 

 

 

예제 2

https://www.acmicpc.net/problem/1850

1850번: 최대공약수

 

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long a = sc.nextLong();
        long b = sc.nextLong();
        long result = gcd(a,b);

        while(result > 0) {
            bw.write("1");
            result--;
        }
        bw.flush();
        bw.close();
    }

    public static long gcd(long a, long b) {
        if(b==0) {
            return a;
        }
        else {
            return gcd(b, a%b);
        }
    }
}