오일러 함수 φ(n)은 1부터 n까지 n과 서로 소인 수의 개수를 나타냅니다. 두 수 a와 b가 서로 소일 때 gcd(a,b)=1이 성립합니다.

재귀적 계산식
임의의 양의 정수 a에 대해 다음 식이 성립합니다:

증명
n을 소인수 분해한 후 φ(n)을 계산하는 방식을 통해 증명할 수 있습니다. d = gcd(a,b)라고 하면:

일반항 공식
n의 소인수 분해 결과를 기반으로 다음과 같이 계산할 수 있습니다:

증명 방법
n = p₁^b₁ × p₂^b₂ × ... × p_k^b_k 형태로 표현하면:

포함-배제 원리 활용
n의 소인수 p₁,p₂,...,p_k에 대해:

효율적인 계산
소인수 분해 시간 복잡도 O(√n)을 갖는 알고리즘으로 φ(n)을 구현할 수 있습니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int num;
        cin >> num;
        int result = num;
        for (int i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                result = result / i * (i - 1);
                while (num % i == 0) num /= i;
            }
        }
        if (num > 1) result = result / num * (num - 1);
        cout << result << endl;
    }
    return 0;
}

선형 체계 활용
O(n) 시간 복잡도를 가진 선형 체계 기반 알고리즘입니다:

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1000010;
vector<int> primeList;
bool sieveFlags[MAX];
int phiValues[MAX];

int main() {
    int n;
    cin >> n;
    phiValues[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!sieveFlags[i]) {
            primeList.push_back(i);
            phiValues[i] = i - 1;
        }
        for (int j = 0; j < primeList.size() && i * primeList[j] <= n; j++) {
            sieveFlags[i * primeList[j]] = true;
            if (i % primeList[j] == 0) {
                phiValues[i * primeList[j]] = phiValues[i] * primeList[j];
                break;
            } else {
                phiValues[i * primeList[j]] = phiValues[i] * (primeList[j] - 1);
            }
        }
    }
    cout << accumulate(phiValues, phiValues + n + 1, 0) << endl;
    return 0;
}