Day-12 오일러 피

---

1. 오일러 피

• 오일러 피 함수 P[N]은 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
• 서로소란 공약수가 1 밖에 없는 수를 의미한다.

---

2. 오일러 피 원리

오일러 피 함수의 원리는 소수 구하기에서 사용한 에라토스테네스의 체와 비슷하다.

1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화
2. 2부터 시작해 현재 값이 소수이면, 현재 값의 배수에 해당하는 수에 P[i] = P[i] - P[i] / K 연산을 수행
3. 배열의 끝까지 과정 2를 반복

---

3. 예제 문제

[11689] GCD(n, k) = 1 (JAVA)