Euler's phi function / N이하의 서로소의 개수 구하기

$p_1, p_2, ... p_k$를 $N$의 소인수라고 할 때, Euler's phi function에 의해 다음이 성립한다.

 

$\Phi (N) = N \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2})\times ... \times (1 - \frac{1}{p_k}) $

 

이때, $\Phi(N)$은 1 이상 $N$이하의 수 중 $N$과 서로소인 수의 개수를 의미한다.

$p_1, p_2, ... p_k$는 모두 $N$의 소인수이기 때문에 결과값은 항상 정수임을 확인할 수 있다.

 

이를 구현하면 다음과 같다.

수를 소인수 분해 한 뒤, 소인수들로 식을 형성한다.

https://int-p.tistory.com/21

정수의 소인수분해 알고리즘

long long N;
vector <long long> primeNum;
vector <long long> p;

int main(void) {	
	long long x = N;
	for (int i = 0; i < primeNum.size(); i++) {
		long long now = primeNum[i];
		if (now * now > x) break;
		if (x % now == 0) {
			p.push_back(now);
			while (1) {
				if (x % now == 0) x /= now;
				else break;
			} 
		}
	}
	if (x != 1) p.push_back(x);
	long long ans = N;
	for (int i = 0; i < p.size(); i++) {
		ans /= p[i];
		ans *= (p[i] - 1);
	}
	return 0;
}

식을 변형하여 다음과 같은 형태로 활용하였다.

$\Phi (N) = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times ... \times\frac{p_k - 1}{p_k} $