[개념 학습 및 정리] 정수론

1. 정수론

정수의 성질을 연구하는 분야이다.

• 약수
• 배수

 

 

 

2. 약수

특정 정수를 나누어 떨어지게 하는 수이다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        for(int i = 1; i <= n; i++) {
            if(n % i == 0) {
                bw.write(i + " ");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

3. 소수

약수가 1과 자기 자신뿐인 정수이다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        boolean flag = false;
        for(int i = 2; i <= n; i++) {
            if(n % i == 0) {
                flag = true;
            }
        }

        if(!flag) bw.write("소수가 아님");
        else bw.write("소수임");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

4. 에라토스테네스의 체

특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식이며 일종의 노가다 방식이라 상당히 무식한 방법이지만 이 방식이 프로그래밍에서는 상당히 효율적인 방법론이다. 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧다.

 

특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우에 효율적인 알고리즘이다. 시간 복잡도는 O(NlogN)이다.

 

• 2를 제외한 모든 2의 배수를 체크한다.
• 3을 제외한 모든 3의 배수를 체크한다.
• 4는 아까 체크당했으므로 소수 아님.
• 5를 제외한 모든 5의 배수를 체크한다.
• ...

 

에라토스테네스의 체

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        boolean[] arr = new boolean[n+1];
        for(int i = 0; i < n+1; i++) {
            arr[i] = true;
        }

        for(int i = 2; i < n+1; i++) {
            for(int j = i*i; j < n+1; j+=i) {
                arr[j] = false;
            }
        }

        // 2부터 n 사이의 소수 출력
        for(int i = 2; i < n+1; i++) {
            if(arr[i]) bw.write(i + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

5. 소인수 분해

숫자 N을 소수의 곱으로 나타낸다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        int i = 2;
        while(n > 1) {
            if(n % i != 0) {
                i++;
                continue;
            }
            bw.write(i + " ");
            n /= i;
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

6. 유클리드 호제법

유클리드 호제법 사전 지식은 다음과 같다.

• 공약수(공통된 약수)
• 공배수(공통된 배수)
• 최대공약수 (공통된 약수의 최대 값, GCD - Greatest Common Divisor)
• 최대공배수 (공통된 배수의 최솟 값, LCM - Least Common Multiplier)

 

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다. 일반적인 방법이라면 소인수 분해를 하고 공통된 소수를 찾지만, 유클리드 호제법은 더 효율적으로 구할 수 있다.

 

• 큰 수를 작은 수로 나눈 나머지를 구한다. (MOD)
• 나눴던 수와 나머지로 MOD 연산을 한다.
• 과정 반복 (나머지가 0이 되면 마지막으로 나눴던 수가 최대공약수가 된다.)

 

최소공배수는 각 주어진 숫자에서 유클리드 호제법으로 구한 최대공약수로 구할 수 있다. 일반적으로 최소공배수를 구할 때 각 숫자를 최대공약수로 나눈뒤, 곱한 값에 최대공약수를 또 곱하는데 이 과정은 결국, 주어진 두 숫자의 곱에서 최대공약수로 나눈 값이다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int gcd;
        int mCopy = m;
        while(true) {
            int r = n % mCopy;
            if(r == 0) {
                gcd = mCopy;
                break;
            }
            n = mCopy;
            mCopy = r;
        }
        
        int lcm = n * m / gcd;

        bw.write(gcd + ", " + lcm);
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

7. 파스칼의 삼각형

파스칼의 삼각형을 이해하기 위해서는 먼저 조합(Combination)의 개념을 알아야 한다. 

 

조합의 예시는 다음과 같다.

• 3개의 공 중 2개를 고를 때의 경우의 수는 {1 2}, {1 3}, {2 3}
• 5개의 공 중 3개를 고를 때의 경우의 수는 {1 2 3}, {1 2 4}, {1 2 5},  {1 3 4}, {1 3 5}, {1 4 5}, {2 3 4}, {2 3 5}, {2 4 5}, {3 4 5}

 

이어서 파스칼의 삼각형과 조합을 살펴보면 관련이 되어있음을 확인할 수 있다. 예를 들어 파스칼의 삼각형 6번째 줄을 보면 정확히 조합(Combination)을 계산한 값과 동일함을 확인할 수 있다.

파스칼의 삼각형

1

5

10

10

5

1

조합

이번에는 조합 계산법을 확인을 해보면 왜 파스칼의 삼각형이 필요한지 알 수 있다. n이 20이라면 계산시 분자의 값은 20 팩토리얼 값을 계산해야한다. 20 팩토리얼은 어마어마한 숫자이지만, 파스칼의 삼각형을 이용한다면 단순히 더하는 것만으로 쉽게 구할 수 있다.

조합 계산법

예를 들어, 20개의 공 중에서 12개를 뽑는 경우의 수를 구하고, 구한 경우의 수의 끝자리 세 숫자만 알고자 하는 문제에서는 파스칼의 삼각형에서 가장 끝의 세개만 생각하면 된다.