오일러 피 함수

오일러 피 함수 $P[N]$는 $[1, N]$의 구간에서 $N$과 서로소인 자연수의 개수를 구하는 함수다.
서로소란 1이 유일한 공약수인 두 수의 관계를 말한다.

오일러 피 함수의 원리

오일러 피 함수는 에라토스테네스의 체와 비슷한 방법으로 접근한다.

먼저 $N$의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화한다.

vector<int> Phi(N + 1);
for(int i = 1; i <= N; i++)
    Phi[i] = i;

그리고 소수들을 골라가며 현재 소수 $K$에 해당하는 배수들을 탐색하며 다음의 연산을 수행한다.
$P[i] = P[i] - \cfrac{P[i]}{K}$

int result = N;

for(int i = 2; i <= N; i++)
{
    if(Phi[i] == i)
    {
        for(int j = i; i <= N; j += i)
            phi[j] -= phi[j] / i;
    }
}