C++ 코딩테스트 강좌, 오일러 피 함수 구현하기

코딩 테스트 준비 중 수학과 알고리즘 문제에 대한 이해는 매우 중요합니다. 오늘은 오일러 피 함수에 대해 논의하고 이를 C++로 구현하는 방법을 알아보겠습니다. 오일러 피 함수는 주어진 정수 n보다 작거나 같은 양의 정수와 서로소인 정수의 개수를 반환하는 함수입니다. 이는 수론에 많은 응용이 있으며, 수학적 문제를 해결하는 데 유용합니다.

1. 오일러 피 함수 소개

오일러 피 함수는 다음과 같이 정의됩니다:

  • 주어진 n에 대해서, φ(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk),

여기서 p1, p2, … pk는 n의 서로소인 모든 소수입니다. 예를 들어, φ(6)은 다음과 같이 계산됩니다:

  • n = 6, 소수 p = 2, 3
  • φ(6) = 6 * (1 – 1/2) * (1 – 1/3) = 6 * 1/2 * 2/3 = 2

1.1 오일러 피 함수의 성질

  • φ(1) = 1
  • 만약 p가 소수이고 k가 양의 정수일 때, φ(p^k) = p^k * (1 – 1/p)
  • n의 두 수 a, b가 서로소일 때, φ(ab) = φ(a) * φ(b)

2. 문제 설명

문제: 주어진 정수 n에 대해 오일러 피 함수를 계산하는 C++ 프로그램을 작성하시오.

입력: 정수 n (1 ≤ n ≤ 106)

출력: 정수 φ(n)

3. 알고리즘 설계

오일러 피 함수를 직접 계산하는 방법은 비효율적일 수 있습니다. 소수를 미리 구한 후 위에서 정의한 식을 이용하여 φ(n)을 계산할 수 있습니다. 이를 위해 다음과 같은 단계로 알고리즘을 설계합니다.

  1. 먼저, 에라토스테네스의 체를 사용하여 n 이하의 모든 소수를 구합니다.
  2. 구한 소수를 이용해 φ(n)을 계산합니다.

3.1 에라토스테네스의 체

에라토스테네스의 체는 소수를 신속하게 찾기 위한 고전적인 알고리즘입니다. 이 알고리즘은 시간 복잡도가 O(n log log n)으로 매우 효율적입니다.

4. C++ 코드 구현

이제 전체 알고리즘을 C++ 코드로 구현해 보겠습니다. 다음은 오일러 피 함수를 계산하는 C++ 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

// 오일러 피 함수 계산
int eulerPhi(int n) {
    int result = n; // 초기값은 n
    for (int i = 2; i * i <= n; i++) {
        // 만약 i가 n의 약수라면
        if (n % i == 0) {
            // 소수를 곱해서 결과를 조정합니다
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i; // 결과 계산
        }
    }
    // 마지막에 남은 n이 소수일 경우
    if (n > 1) {
        result -= result / n; // 소수에 대한 결과 처리
    }
    return result;
}

int main() {
    int n;
    cout << "정수를 입력하세요: ";
    cin >> n;
    
    cout << "φ(" << n << ") = " << eulerPhi(n) << endl;
    return 0;
}

5. 코드 설명

위 코드는 다음과 같은 단계로 작동합니다:

  • eulerPhi(int n) 함수는 주어진 정수 n에 대해 오일러 피 함수를 계산하고 반환합니다.
  • 변수 result는 초기값으로 n을 가지며, 소수가 발견될 때마다 이 값을 업데이트합니다.
  • 소수 i가 n의 약수일 경우, n을 i로 나누어가며 i의 배수를 제거합니다. 이 과정에서 소수에 따라 결과를 조정합니다.
  • 모든 소수를 검사한 후, 만약 n이 1보다 큰 경우 (즉, n이 소수인 경우) 추가로 처리합니다.

6. 코드 테스트

코드를 완료한 후, 다양한 테스트 케이스로 함수를 검증해 볼 수 있습니다. 예를 들면:

  • n = 1일 때, φ(1) = 1
  • n = 6일 때, φ(6) = 2
  • n = 9일 때, φ(9) = 6

7. 성능 분석

위 알고리즘은 O(√n)의 시간복잡도를 가지고 있으며, n이 최대 106일 때도 상대적으로 빠르게 작동합니다. 공간 복잡도는 O(1)로 추가적인 메모리 사용이 거의 없습니다. 이러한 이유로 대규모 데이터에서도 효율적으로 사용될 수 있습니다.

8. 결론

오늘의 포스트에서는 오일러 피 함수의 개념과 이를 C++로 구현하는 방법을 배웠습니다. 오일러 피 함수는 다양한 수학적 문제의 해결에 유용하게 사용될 수 있으며, 컴퓨터 프로그래밍에서 큰 역할을 합니다. 이러한 문제를 풀어보는 것은 코딩 테스트 준비에 큰 도움이 될 것입니다.

코드에 대한 질문이나 피드백이 있다면 댓글로 남겨 주세요! 다음 포스트에서는 또 다른 알고리즘 문제를 다룰 예정입니다. 감사합니다!