알고리즘으로 기강 잡기 - 정수론

소수 구하기

소수를 구하는 대표적인 판별법으로 에라토스테네스의 체가 있다. 에라토스테네스의 체 원리는 다음과 같다.

에라토스테네스의 체 핵심 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
2. 2 부터 시작하여 현재 숫자가 지워지지 않을 때, 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지운다. 이 때 처음으로 선택된 수는 지우지 않는다.
3. 배열의 끝까지 두 번째 단계를 반복한 후 배열에서 남아 있는 모든 수를 출력

에라토스테네스의 체를 사용할 때 시간 복잡도는 최적화 정도에 따라 다르지만, 일반적으로 O(Nlog(logN))이다.

소수 구하기 구현

백준 1929번 - 소수 구하기

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);    
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            a[i] = i;
        }
        
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (a[i] == 0) continue;
            for (int j = i+i; j <= n; j += i) {
                a[j] = 0;
            }
        }
        
        for (int i = m; i <= n; i++) {
            if (a[i] > 1) {
                System.out.println(a[i]);
            }
        }
    }
}

오일러 피

오일러 피 함수 P[N]의 정의는 1 부터 N까지의 범위에서 N과 서로소(공약수가 1이외에 없는 수)인 자연수의 개수를 뜻한다.

오일러 피 핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 자기 자신의 인덱스값으로 초기화
2. 2 부터 시작하여 배열의 값과 인덱스가 같으면(소수일 때) 현재 선택된 수(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하여 P[i] = P[i] - P[i]/k 연산 수행
3. 배열의 끝까지 두 번째 단계를 반복하며 오일러 피 함수를 완성

유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘으로, 소인수 분해를 이용한 공통된 소수들의 곱으로 표현하는 것 보다 좀 더 간단한 방법을 제시한다.

유클리드 호제법 핵심 이론

유클리드 호제법을 수행하기 위해서는 먼저 최대 공약수를 구하는데 사용할 MOD 연산(두 값을 나눈 나머지를 구하는 연산 - 10 % 4 = 2)을 이해하고 있어야 한다.

MOD 연산을 통해 구현하는 유클리드 호제법

1. 큰 수를 작은 수로 나누는 MOD 연산 수행
2. 이전 단계에서의 작은 수와 MOD 연산의 결과값으로 MOD 연산 수행
3. 두 번째 단계를 반복하며 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택