정수론

소수 구하기

소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.

같은 의미로 1과 자기 자신 이외에 약수가 존재하지 않는 수를 말한다.

에라토스테네스의 체

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

에라토스테네스의 시간 복잡도

이중 for문을 사용하므로 O(N^2) 으로 판단할 수 있지만 실제 시간 복잡도는 일반적으로 O(Nlog(logN)).

이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하기 때문.

int k = 20; // 1부터 20 사이의 소수를 구한다.
int[] arr = new int[k + 1]; // 배열의 크기는 0부터 k까지. 즉, k + 1

for (int i = 2; i < k + 1; i++) {
    arr[i] = i;
}

// 전체 배열을 확인하지 않고 제곱근(Math.sqrt())까지만 연산!
for (int i = 2; i < Math.sqrt(k + 1); i++) { 
    if (arr[i] == 0) continue;
    // arr[i]의 배수를 0으로 지운다
    // 아래는 배수에만 접근하는 for문 조건!
    for (int j = i + i; j < k + 1; j = j + i) {
        arr[j] = 0;
    }
}

for (int i = 2; i < k + 1; i++) {
    if (arr[i] != 0 && arr[i] >= n) System.out.println(arr[i]);
}

오일러 피

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

*pass

유클리드 호제법

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

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

1. 큰 수를 작은 수로 나누는 MOD(%) 연산을 수행
2. 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 다시 MOD 연산을 수행
3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

private static int ea(int big, int small) {
    int namerge = 0;
    while (true) {
        namerge = big % small;
        if (namerge == 0) return small;
        else {
            big = small;
            small = namerge;
        }
    }
}

private static int ea_recursive(int big, int small) {
    if(small == 0) return big;
    return ea_recursive(small, big % small);
}

확장 유클리드 호제법

*pass