[PS]오일러 피 함수(Euler phi function)

정수론 문제 풀다가 자주 보여서 복습 겸 작성

1. 오일러 피(파이) 함수(Euler phi function)

---

• 오일러 피(n) : n이 양의 정수일 때 모든 n 이하 자연수인 k에 대해 n과 서로소인 k의 개수

  $ϕ(n) = n이하\ 양의\ 정수\ 중\ n과\ 서로소인\ 수의\ 개수$

PS 풀면서 자주 활용되는 함수로 주요한 성질들은 다음과 같다.

1. p가 소수일 때

$ϕ(p)=p-1$

-> p는 소수이기 때문에 1 ~ (p-1)은 전부 p와 서로소이다.

$ϕ(p^a)=p^a-p^{a-1}=p^{a-1}(1-p)$

-> $p^a이하\ p의\ 배수의\ 개수는\ p^{a-1}개$

2. n, m은 서로소일 때

$ϕ (nm)=ϕ (n)ϕ (m)$

-> 생략

3. p1, p2는 m의 소인수일 때

$ϕ(n)=ϕ(p_1^a \times p_2^b) = ϕ(p_1^a)ϕ(p_2^b) = (p_1^a - p_1^{a-1})\times (p_2^a - p_1^{a-2})$

-> 1, 2 참고


즉 아래와 같은 식을 얻을 수 있다.

$\\ \phi(n)=\phi(p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\dots \times p_k^{a_k}) \\ = \phi(p_1^{a_1})\times \phi(p_2^{a_2})\times \phi(p_3^{a_3})\dots \times \phi(p_k^{a_k})$

$\\\phi(n)=(p_1^{a_1}-p_1^{a_1 - 1})\times (p_2^{a_2}-p_2^{a_2 - 1})\times (p_3^{a_3}-p_3^{a_3 - 1})\times \dots (p_k^{a_k}-p_k^{a_k - 1})$

2. 코드로 구현

---

1. 에라토스테네스의 체 구현 (n 이하의 소수들을 찾기 위함)

int prime[1000000];

void f1(long long n) {
	int x = (int)sqrt(n);
	for (int i = 2; i <= x; i++)
		if (!prime[i])
			for (int j = i * i; j <= x; j += i)
				prime[j] = 1;
}

2. 오일러 피 구하기

long long phi(long long n) {
	if (n == 1)return 0;
	
	long long x = (long long)sqrt(n),res = 1;
	
	for (long long i = 2; i <= x; i++) {
		long long a = 0;
		if (!prime[i] && (n % i) == 0) {
			while (n % i == 0) {
				a++;
				n /= i;
			}
			res *= ((i - 1) * pow(i, a- 1));
		}
		if (n == 1)break;
	}
	if (n > 1)
		res *= (n - 1);
	return res;
}

• i 는 sqrt(n)보다 작은 모든 소수
• i 가 n의 소인수인지 판단 후 while()을 통해 소인수 i 제거
• $\phi(i^{a}) = (i-1)\times i^{a- 1}$ 적용 후 res에 값 누적
• for()문 종료 후 n >1 이라면 현재 n의 값은 sqrt(n)보다 큰 소인수
  -> $\phi(p)=p-1$ 을 적용하여 res에 값 누적

3. 관련 문제

---

백준 11689번 : GCD(n, k) = 1

https://www.acmicpc.net/problem/11689

#include <stdio.h>
#include<math.h>
typedef long long ll;
int prime[1000000];

void f1(ll n) {
	ll x = (ll)sqrt(n);
	for (ll i = 2; i <= x; i++)
		if (!prime[i])
			for (ll j = i * i; j <= x; j += i)
				prime[j] = 1;
}

ll f2(ll n) {
	ll x = (ll)sqrt(n), res = 1;
	for (ll i = 2; i <= x; i++) {
		int a = 0;
		if (!prime[i] && (n % i) == 0) {
			while (n % i == 0) {
				a++;
				n /= i;
			}
			res *= ((i - 1) * pow(i, a - 1));
		}
		if (n == 1)break;
	}
	if (n > 1)res *= (n - 1);
	return res;
}

int main() {
	ll n;
	scanf("%lld", &n);
	f1(n);
	printf("%lld", f2(n));
}

백준 4355번 : 서로소

https://www.acmicpc.net/problem/4355

#include <stdio.h>
#include<math.h>
int prime[100000];

void f1(int n) {
	int x = (int)sqrt(n);
	for (int i = 2; i <= x; i++)
		if (!prime[i])
			for (int j = i * i; j <= x; j += i)
				prime[j] = 1;
}

int f2(int n) {
	if (n == 1)return 0;
	int x = (int)sqrt(n), res = 1;
	for (int i = 2; i <= x; i++) {
		int a = 0;
		if (!prime[i] && (n % i) == 0) {
			while (n % i == 0) {
				a++;
				n /= i;
			}
			res *= ((i - 1) * pow(i, a - 1));
		}
		if (n == 1)break;
	}
	if (n > 1)res *= (n - 1);
	return res;
}

int main() {
	int n;
	f1(1000000000);
	while (1) {
		scanf("%d", &n);
		if (n == 0)break;
		printf("%d\n", f2(n));
	}
	return 0;
}