오일러 피 - 서로소

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

✅ 오일러 피의 핵심 이론

• 오일러 피의 함수의 원리는 에라토스테네스의 체와 비슷하다.

오일러 피 함수의 원리

① 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 한다.

② 2부터 시작해 현재 배열의 값과 인덱스가 같으면( = 소수 일때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K연산을 수행한다. (i는 K의 배수)

③ 배열의 끝까지 ②를 반복하여 오일러 피 함수를 완성한다.

<aside> 📌

P[i] = P[i] - P[i]/k의 의미

이 식은 현재 수 i에서 k의 배수인 수들의 개수를 제거하는 연산입니다.

• P[i]는 현재 i의 서로소 개수 추정치
• k는 현재 소수
• P[i]/k는 i보다 작거나 같은 수 중 k의 배수 개수 ≈ i에서 k와 공약수를 가지는 수의 개수

따라서

P[i] = P[i] - P[i]/k는

👉 “i에서 소수 k와 공약수를 가지는 수는 제외하고, 나머지만 남긴다”는 의미입니다.

예: P[6] = 6 일때, (현재 선택된 수가 2인 상태에서 P[6]의 값을 갱신 중)

• P[6] = 6인 것은 현재까지 1~6까지의 수 중 6과 서로소인 자연수의 갯수는 6개이다라는 의미이다.
• 현재 선택된 숫자인 2는 소수이다.
• P[6]/2는 6보다 작거나 같은 수 중 2의 배수 개수 (6 / 2 = 3개 → 2, 4, 6) </aside>

✅ 오일러 피 함수의 원리 이해하기

1. 구하고자 하는 범위까지 배열을 생성한 후 2를 선택한다. (1부터 15까지 범위에서 15와 서로소인 자연수 갯수, 2부터 시작한다.)

1. 2의 모든 배수마다 P[i] = P[i] - P[i]/2 연산을 수행해 값을 갱신한다. 예를 들어 P[8] = 8 - (8 / 2)를 통해 4를 계산한다. (N=2, 4, 6, 8, 10, 12, 14에 대해서 수행하여 값을 갱신한다.즉, 위의 연산을 통해 2의 배수들을 제거해준다.)

1. 소수 구하기에서 배수를 지우는 부부만 P[i] = P[i] - P[i] / K로 변경하면 오일러 피 함수를 간단히 구현할 수 있습니다. 탐색을 계속 진행하면서 N = ∅(N)인 곳(소수)을 찾아 값을 갱신한다.

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