1. 오일러 피 함수란?
φ(n)=n이하자연수중n과서로소인수의개수
φ(12)=4이다.

2. 사전 학습
오일러 피 함수의 증명을 위해서 다음 챕터에서 오일러의 곱 공식
을 살펴볼 것인데, 사전에 학습해야할 내용이 있어서 미리 소개하겠다.
- 1️⃣
소인수
: 임의의 수 K의 소수이면서 인수인 수이다. 예를 들면 12의 소인수는 2와 3 이 있다. - 2️⃣
소인수 분해
: 임의의 수 K를 소수로만 인수 분해하는 것이다. 예를 들어 12를 소인수 분해하면, 12=22∗3이다. - 3️⃣
서로소
: A와 B가 서로소라는 뜻은, A와 B의 공약수가 1말고는 없다는 뜻이다. - 4️⃣ φ(): 오일러 파이라고 읽는다.
- 5️⃣ ∏p∣N: 여러 값의 합을 나타내는 ∑ 처럼 여러 값의 곱셈을 나타내는 수학기호 이다.
3. 오일러의 곱 공식
(1) 정의
ϕ(N)=N×∏p∣N(1−1p)
(2) 해설
오일러의 곱 공식
의 원리는 1부터 N까지의 숫자 중 소인수와 그 배수를 제외
시켜서 결국 소수만 영역안에 남게 하는 것이다. 그리고 그 수를 센다.
위에서 나타낸 p는 N의 소인수를 뜻한다. 해당 식이 파이로 묶여 있으므로 p에는 N의 소인수가 차례대로 들어갈 것이다. 이제 하나씩 드릴링 해보자.
ⓐ N이하의 자연수 중 p의 배수의 개수는 몇 개일까?
그것은 N을 P로 나눈 몫과 같을 것이다. 예를 들어 1이상 12 이하에서 2의 배수의 개수는 6이다. 3의 배수는 4개일 것이다. 따라서 이를 변수화해서 나타낸다면, Np(내림) 로 나타낼 수 있다.
ⓑ 비율화 해서 나타내기
해당 공식에서는 계산하기 쉽게 N개 중에서 소인수의 배수가 아닌 수의 비율 을 구하고 거기에 N을 곱해 최종적으로 N 이하 N과 서로소인 배수를 구한다.
N이하 자연수 중 소인수 p의 배수가 아닌 수의 비율 을 표현하면 1−1p와 같을 것이다. 이를 상세히 설명하면 우리가 구하려는 것은
비율=P의배수가아닌숫자의개수전체숫자의개수
즉,
비율=N−NPN
분모를 정리하면
비율=1−1P
가 된다.
이제 하나의 1−1p의 뜻은 알겠다. 하지만 공식을 보니 파이 기호로 모든 소인수가 아닌 수의 비율을 곱하고 있다. 이건 왜 그럴까?
ⓒ 소인수의 배수가 아닌 수의 비율을 전부 곱하는 이유
이는 포함 배제의 원리 때문이다. 2의 배수와 3의 배수를 지우면서 6의 배수가 2번 지워졌다. 포함 배제의 원리는 집합시간에 배웠을텐데, 기억 안 나는 분이 많을테니 다시 기록하고 가겠다.
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣
즉 두번 중복해서 빼진 값을 한 번 더해서, 계산을 올바르게 유지하는 것이다. 이 포함 배제의 원리는 곱셈 공식에 자연스럽게 녹아 있다.
위의 공식 대로, φ(12)를 구해볼까?
ϕ(12)=12×(1−12)×(1−13)
여기서 곱 공식을 계산해보면
12×(1−12−13+16)
이다. 이를 글로 풀어보면,
12×(100%−2의배수의비율−3의배수의비율+6의배수의비율)
이다. 자연스럽게 포함 배제의 원리 가 들어가 있다. 따라서 파이를 써서 모든 비율을 곱해야 한다.
소결
이렇게 모든 소인수가 아닌 수의 비율을 곱하면 (즉 파이기호까지만 계산하면) N 이하의 수 중 N과 서로소인 수의 비율이 된다. 여기에 전체 개수인 N을 곱하여 서로소의 개수를 구하면 되는 것이다.
이제 오일러피 함수의 원리를 알아봤으니 이를 JAVA로 구현해보겠다.
4. JAVA로 구현하는 법
(1) 원리
위에서 구한 오일러 피 함수(φ(n))는 하나의 N에 대해서 그것과 서로소인 수의 개수를 구했다. 우리가 할 것은 1부터 N까지 자연수 각각의 φ(k)의 값을 구할 것이다.
이를 위해서 에라토스테네스의 체를 활용한다. 에라토스테네스의 체에서 소수의 배수를 소수 판정 배열에서 false
로 바꾸던 것을 소수의 배수가 i이면 arr[i] = arr[i] - arr[i]/P (P는 소수, i는 소수의 배수)
로 바꾸어주면 된다.
이게 왜 가능할까? arr[i] = arr[i] - arr[i]/P1
는 N×(1−1P1)를 풀어 쓴 것과 같다. 여기서 만약 소수 P2도 i를 배수로 가진다면 arr[i] = arr[i] - arr[i]/P2
계산을 한번 더 할 것이다. 이는 N×(1−1P1) 이란 계산이 끝난 곳에, (1−1P2)를 한번 더 곱하는 것이다. 즉 각 배열의 원소마다
ϕ(N)=N×∏p∣N(1−1p)
계산을 해주는 것이 된다.
(2) SUDO CODE
- 0️⃣ 어디까지 서로소의 개수 찾을 건지 N 입력 받기
- 1️⃣ 에라토스테네스의 체 구현해서 N개의 영역 내의 소수 찾기 ➜ 원래 하듯이 소수 판정 배열 만들기
- 2️⃣ 오일러의 피 수행
- 2-1) 1번에서 완성한 소수 판정 배열 조회
- 2-2) 임의의 소수 p를 만나면 해당 소수의 배수들(이하 k)에 대하여 euler_arr[k] = euler[k] - euler_arr[k]/p 해주기
(3) JAVA CODE
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N;
static boolean [] is_prime;
static int [] euler_arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
is_prime = new boolean [N + 1];
prime_sieve(N);
euler_phi_f(N);
System.out.println(Arrays.toString(euler_arr));
}
public static void prime_sieve(int n){
Arrays.fill(is_prime, true);
for (int i = 2; i <= Math.sqrt(n); i++) {
if(is_prime[i]){
for (int j = i*i; j <= n; j*=i) {
is_prime[j] = false;
}
}
}
}
public static void euler_phi_f(int n){
euler_arr = new int[n + 1];
for (int i = 1; i <= N; i++) {
euler_arr[i] = i;
}
for (int i = 2; i <= N; i++) {
if(is_prime[i]){
for (int j = i; j <= N; j+=i) {
euler_arr[j] = euler_arr[j] - euler_arr[j]/i;
}
}
System.out.println("소수: "+i + "배열 상황: " + Arrays.toString(euler_arr));
}
}
}
매번 소수를 활용해 오일러의 피 전용 배열을 돌 때마다 콘솔에 찍도록 했으니, 한 줄 씩 확인하며 이해하길 바란다.