📍 정수론

수의 성질을 탐구하고 공부하는 분야를 말한다.
코딩테스트에서는 소수 부분과 호제법 부분이 가장 많이 등장한다.

📍 소수 구하기

✅ 소수의 정의

소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.
즉, 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다.

✅ 소수 구하기의 핵심 - 에라토스테네스의 체

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

✅ 에라토스테네스의 체 원리 이해하기 - 예시

1부터 30까지의 수 중 소수를 구하는 예시를 보면서 에라토스테네스의 체의 원리를 알아보자.
1. 먼저 주어진 범위까지 배열을 생성한다.
1은 소수가 아니므로 삭제하고, 배열은 2부터 시작한다.

이미지 출처 : https://ezmath.readthedocs.io/en/latest/erathosthenes.html
2. 선택한 수의 배수를 모두 삭제한다.
현재의 경우 2의 배수를 모두 삭제한다.

2의 배수 선택

3. 다음 지워지지 않은 수를 선택한다.
   즉, 3을 선택하고 선택한 수의 모든 배수를 삭제한다.
   이미 지운 수는 다시 지우지 않는다.
   

3의 배수 선택
4. 앞의 과정을 배열의 끝까지 반복한다.

5의 배수 선택

7의 배수 선택
5. 삭제되지 않은 수를 모두 출력한다.

즉, 1부터 30까지의 수 중 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29이다.

📍 오일러의 피

✅ 정의

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

✅ 핵심 이론

오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.
1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다. (i는 K의 배수)
3. 배열의 끝까지 2를 반복하여 오일러 피 함수를 완성한다.

✅ 오일러 피 함수 원리 이해하기 - 예시

1. 구하고자 하는 범위까지 배열을 생성한 후 2를 선택한다.
   

2. 2의 모든 배수마다 P[i] = P[i] - P[i] / 2 연산을 수행해 값을 갱신한다.
   예를 들어 8 = 8 - (8 / 2)를 통해 4를 계산한다.
   

3. 소수 구하기에서 배수를 지우는 부분만 P[i] = P[i] / K로 변경하면 오일러 피 함수를 간단히 구현할 수 있다.
   탐색을 계속 진행하면서 N =
   

4. 배열이 끝날 때까지 반복한다.
   

start index = 5, start index = 7, start index = 11 & start index = 13