C++ 코딩테스트 강좌, 오일러 피

안녕하세요! 이번 강좌에서는 C++를 사용하여 오일러 피(Euler’s Totient Function) 문제를 해결하는 방법에 대해 알아보겠습니다. 이 문제는 숫자 n이 주어졌을 때, n보다 작거나 같은 정수 중에서 n과 서로소인 정수의 개수를 구하는 함수입니다.

오일러 피 함수란?

오일러 피 함수 φ(n)은 숫자 n과 서로소인 숫자들의 개수를 나타내는 함수입니다. 예를 들어:

  • φ(1) = 1 (1은 항상 자신과 서로소)
  • φ(2) = 1 (2보다 작은 수 중 2와 서로소인 수는 1)
  • φ(3) = 2 (1과 2가 3과 서로소)
  • φ(4) = 2 (1과 3이 4와 서로소)
  • φ(5) = 4 (1, 2, 3, 4가 5와 서로소)

문제 설명

주어진 n에 대해 φ(n)의 값을 계산하는 알고리즘을 작성하세요. 입력은 정수 n (1 ≤ n ≤ 106)입니다.

예제 입력

10

예제 출력

4

Explanation: 1, 3, 7, 9가 10과 서로소입니다.

문제를 푸는 과정

1단계: 프로퍼티 이해하기

오일러 피 함수의 값은 다음과 같은 프로퍼티를 가지고 있습니다:

  • p가 소수일 때, φ(p) = p – 1
  • p가 소수일 때, φ(pk) = pk – pk-1 = pk(1 – 1/p)
  • 두 소수 p와 q가 서로소일 때, φ(p*q) = φ(p) * φ(q)

2단계: 에라토스테네스의 체를 활용한 구간 계산

n까지의 모든 수의 오일러 피 값을 구하기 위해, 에라토스테네스의 체 방법을 사용하여 합성수를 찾아고, 피 값을 계산할 수 있습니다. 이 방법은 시간복잡도가 O(n log log n)입니다.

3단계: 알고리즘 구현

다음은 C++로 오일러 피 함수를 계산하기 위한 구현입니다:


#include <iostream>
#include <vector>

using namespace std;

void eulerTotient(int n, vector<int>& phi) {
    for (int i = 0; i <= n; i++) {
        phi[i] = i; // initialize phi
    }
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // i가 소수인 경우
            for (int j = i; j <= n; j += i) {
                phi[j] *= (i - 1); // 소수 p가 들어가므로 (1 - 1/p) 곱하기
                phi[j] /= i;
            }
        }
    }
}

int main() {
    int n;
    cout << "n의 값을 입력하세요: ";
    cin >> n;

    vector<int> phi(n + 1);
    eulerTotient(n, phi);

    cout << "φ(" << n << ") = " << phi[n] << endl;
    return 0;
}

4단계: 코드 설명

위 코드에서:

  • 첫 번째로, 각 수에 대해 φ[i]를 초기화합니다.
  • 그 다음으로, 소수 i를 찾아서 모든 배수 j에 대해 φ[j]를 업데이트합니다.
  • 최종적으로, n의 오일러 피 값은 φ[n]에 저장됩니다.

5단계: 성능 개선

이 알고리즘은 O(n log log n)의 성능을 보입니다. 이는 최대 106 범위에서도 효율적으로 동작합니다.

결론

이번 강좌에서는 C++를 사용하여 오일러 피 함수를 효율적으로 계산하는 방법을 다뤘습니다. 에라토스테네스의 체를 이용한 방법은 빠르고 유용하며, 코딩 테스트에서도 유용하게 사용될 수 있습니다. 앞으로도 다양한 알고리즘을 공부하며 코딩 실력을 키워보세요!

참고 문헌