[C++] 오일러 피 (서로소)

 

 

 

이 포스터에선 오일러 피에 대해 알아보도록 하겠다.

먼저, 오일러 피가 무엇인지 살펴보도록 하자.

 

오일러 피 함수 P[N]은 다음과 같이 정의된다.

P[N] = [1, N] 범위에서 N과 서로소인 자연수의 개수

(1와 N 포함)

 

오일러 피 함수의 증명 과정을 공부해야 완벽하게 이해할 수 있지만

이 포스터에서는 구현 부분만 알아보도록 할 것이다.

 

 

 

 

 

오일러 피 함수 원리

오일러 피는 이전 포스터에서 봤던 에라토스테네스의 체와 매우 유사하다.

 

1. 사전에 미리 N개의 int 배열 메모리를 할당한다.

2. 각 배열의 값은 K로 초기화한다.

3. K의 배수에 해당하는 자리마다 P[K] = P[K] - P[K] / K을 수행한다.

4. K를 2부터 N까지 해당하는 범위에 대해 3번을 반복한다.

 

 

 

과정은 매우 간단하다.

이 과정을 거치면 오일러 피 함수가 완성된다.

그림을 통해 좀 더 살펴보자.

 

 

 

1. 메모리를 할당하고 K = 2로 설정한다.

 

 

 

 

 

2. 2의 배수마다 P[i] = P[i] - P[i] / 2을 해준다.

 

예를 들어 P[6]의 경우, 다음과 같게 된다.

P[6] = 6 - 6 / 2 = 6 - 3 = 3

이 의미는 무엇일까?

 

원소의 개수가 아닌, 집합 형태로 나타내면 다음과 같다.

P[6] = { 1, 2, 3, 4, 5, 6 } 

 

공식을 거치고 나면 다음과 같다.

P[6] = { 1, 3, 5, }

 

즉, 우리는 2의 배수에 해당하는 원소들을 모두 제거한 것이다.

 

 

 

 

 

3. K = 3으로 설정하고 2번과 같이 수행한다.

 

이어서 P[6]의 경우로 살펴보자.

현재 P[6] = { 1, 3, 5 } 다.

 

P[6] = P[6] - P[6] / 3 = 3 - 3 / 3 = 3 - 1 = 2가 된다.

즉, P[6] = { 1, 5 } 가 된다.

 

이후 K = 4, 5, 6에 대해서는 값이 감소하지 않는다.

이것은 모든 P에 대해 동일하게 적용한다.

 

 

 

이 원리는 정확히 이해되지 않을 수 있다.

 

위 예시를 보면 P[6]에 각각 다음과 같이 조치된다고 볼 수 있다.

• 2의 배수 탈락: {1, 3, 5}
• 3의 배수 탈락: { 1, 5 }

3의 배수를 탈락시킬 때, 우리는 { 1, 3, 5 }에 대해서 처리한다.

그 이유는 3과 2의 공배수(ex. 6)는 이미 2의 배수에서 삭제됐기 때문이다.

정확한 원리는 따로 공부하길 바란다.

 

 

 

 

 

오일러 피 코드

#include <iostream>
#include <vector>

using namespace std;

// 메모리 할당
int P[10001];

int main()
{
	ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

	int N;
	cin >> N;

	// 초기화
	for (int i = 1; i <= N; i++)
		P[i] = i;

	// 오일러 피 함수 수행
	for (int i = 2; i <= N; i++)
		for (int j = i; j <= N; j += i)
			P[j] -= P[j] / i;
	
	cout << P[N] << endl;

	return 0;
}