Euler's totient function

Sep 03, 22

오일러 피 함수

오일러 피 함수란?

ϕ(n)=ϕ(n)=1이상 n이하의 정수 중 n과 서로소인 수의 개수

소스 코드

1≤i≤n1≤i≤n인 ii에 대해 ϕ(i)ϕ(i)를 O(nlogn)O(nlogn)으로 구하기

for (int i = 1; i <= n; ++i) {
    phi[i] += i;
    for (int j = 2 * i; j <= n; j += i) {
        phi[j] -= phi[i];
    }
}

그냥 구하기

int phi(int n) {
    int ret = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ret = ret / i * (i - 1);
        }
        while (n % i == 0) {
            n /= i;
        }
    }
    if (n > 1) ret = ret / n * (n - 1);
    return ret;
}