[Do it! 알고리즘 코딩테스트 with C++] 5장. 정수론

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 5장. 정수론

5-1. 소수 구하기
5-2. 오일러 피
5-3. 유클리드 호제법

---

📌 5-1. 소수 구하기

* 소수
- 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수
- 1과 자기 자신 외에 약수가 존재하지 않는 수

* 에라토스테네스의 체
- 시간 복잡도: O(Nlog(logN))

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

---

📌 5-2. 오일러 피

* 서로소
- 공약수가 1 이외에는 존재하지 않는 두 수

* 오일러 피 함수 P[N]
- 1부터 N까지 범위에서 N과 서로소인 자연수의 개수

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

---

📌 5-3. 유클리드 호제법

* 유클리드 호제법
- 두 수의 최대 공약수를 구하는 알고리즘

* 유클리드 호제법 동작 원리
1. 큰 수를 작은 수로 나누는 MOD 연산 수행
2. 앞 단계에서의 작은 수와 MOD 연산 결과(나머지)로 MOD 연산 수행
3. 단계 2를 반복하다가 나머지가 0이 되는 순간의 작은수 = 최대 공약수

* 최소 공배수 구하기
- 최소 공배수 = A * B / 최대 공약수

---