오일러 피 함수

오일러 피 함수 P(N)은 1~ N까지 N과 *서로소인 자연수의 개수를 반환함

*서로소 - 두 수의 최대 공약수가 1인 수 즉, 둘다 소수라는 뜻

 

-  오일러 피 함수 구현

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL); 
	 
	long n;
	cin >> n;
	long result = n;

	for (long p = 2; p <= sqrt(n); p++)
	{
		if (n % p == 0) {
			result -= result / p;
			while (n % p == 0)
				n /= p;
		}
	}

	if (n > 1)
		result -= result / n;

	cout << result << "\n"; 
}

 

오일러 피 함수 ϕ(n)은 n과 서로소인 1부터 n 사이의 자연수의 개수를 반환함

소인수 분해와 오일러 피 함수의 성질을 이용하여 이 값을 계산할 수 있음

 

1. 소인수 분해: 반복문에서 p를 2부터 sqrt(n)​까지 증가시키며 n을 나눔, 만약 n이 p로 나누어진다면, p는 n의 소인수
2. 오일러 피 함수 값의 갱신: n이 p로 나누어지면, result를 result− (result / p)​로 갱신, 만약 n이 어떤 소수 p로 나누어진다면, n과 서로소인 수 중 "p의 배수가 되는 수"는 전체의 1/p​에 해당함 따라서, 이 수들을 제외한 나머지 수의 개수를 구하기 위해 result에서 전체의 1/p​를 뺀 값을 취함
3. 중복 소인수 제거: n이 여전히 p로 나누어진다면, n에서 p의 최고 거듭제곱을 제거, 이 과정은 n을 p의 거듭제곱이 아닌 다른 소인수들로만 구성된 수로 만들기 위함임
4. 남은 소인수 처리: 반복문이 끝난 후, n > 1이라면 n이 가장 큰 소인수, 이 경우, n과 서로소인 수 중 n의 배수를 제외해야 하므로, 마찬가지로 result에서 result− (result / n)​을 수행