[Algorithm] 오일러 피 함수로 서로소의 개수 구하기 with JAVA

Algorithm/Math

[Algorithm] 오일러 피 함수로 서로소의 개수 구하기 with JAVA

jundyu 2025. 6. 30. 14:07

들어가며

처음으로 수학과 관련된 알고리즘을 다뤄보게 되었습니다. 사실 정확히 말하자면 오일러 피 함수는 알고리즘이라기보단 정수론에서 배우는 수학 개념입니다. 의미는 단순하지만 증명은 어렵고 복잡하기 때문에 함수를 외운 뒤 구현하는 법만 이해하면 충분합니다.

오일러 피 함수 : Euler Phi Function

1. 정의

오일러 피 함수는 자연수 n이 주어졌을 때 n 이하의 자연수 중에 n과 서로소인 수의 개수를 구하는 데 사용됩니다.

2. 표기

$$\Large \phi(n)$$

함수의 표기는 위와 같고 피(phi)라고 읽습니다. $\phi(6)$이라면 6 이하의 자연수 중 6과 서로소인 자연수는 1, 5가 있으므로 2를 값으로 가집니다.

3. 수식

$$\large\phi(x)=n\prod_{p|n}(1-\frac{1}{p})=n(1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})\cdots(1-\frac{1}{p})$$

위의 수식에서 p는 n의 소인수에 해당합니다. n에 각 p에 대한 $1-\frac{1}{p}$를 전부 곱하면 n 이하의 서로소의 개수를 알 수 있습니다.

주의!

n이 24인 경우 소인수분해하면 n = 2*2*2*3입니다. 2가 3번 등장하지만 $1-\frac{1}{2}$는 수식에서 한 번만 등장합니다. 즉, 소인수가 여러번 등장하더라도 수식에는 한 번만 등장합니다.

4. 성질

1. 곱셈적 성질

$$\Large\phi(\alpha\beta)=\phi(\alpha)\phi(\beta)$$

오일러 피 함수는 곱셈적 함수이므로 위의 성질을 만족합니다. 단, $gcd(\alpha, \beta) = 1$인 경우(=서로소)라는 조건이 붙습니다.

2. 소수

$$\Large \phi(n)=n-1$$

n이 소수인 경우 오일러 피 함수의 값은 항상 위의 수식을 만족합니다.

5. 예시

$\large \phi(210)=210\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{3})\cdot(1-\frac{1}{5})\cdot(1-\frac{1}{7}) =48$

$\large \phi(495)=495\cdot(1-\frac{1}{3})\cdot(1-\frac{1}{5})\cdot(1-\frac{1}{11}) =240$

오일러 피 함수 알고리즘

1. 개요

오일러 피 알고리즘은 오일러 피 함수의 값을 구하기 위한 알고리즘입니다.

2. 시간복잡도

i) n에 대한 단일 계산

$\large O(n)=\sqrt{n}$

ii) 1부터 n까지 계산

$\large O(n)=n \log{\log {n}}$

1부터 n까지의 모든 자연수에 대해 오일러 피 값을 구할 땐 에라토스테네스의 체 알고리즘으로 효율적으로 구할 수 있습니다. 자세한 설명은 후술하겠습니다.

3. 동작 원리

초기에 결과값 result를 n으로 초기화해두고 n의 소인수를 발견할 때마다 서로소의 개수인 result를 줄여나가는 방식입니다. 가볍게 읽어본 뒤 하단의 구현 코드를 읽어보길 바랍니다.

i) n에 대한 단일 계산

자연수 n의 소인수 쌍 $n=a\cdot b$에서 a와 b 중에 항상 $\sqrt{n}$보다 작은 수가 하나 존재합니다. 따라서 1부터 $\sqrt{n}$까지 증가시키면서 n의 소인수 p를 찾습니다.
자연수 n은 소인수 p를 여러번 제곱했을 수 있기 때문에 n이 p로 나누어 떨어지지 않을 때까지 n을 나눠줍니다.
오일러 피 함수에선 소인수 p가 여러번 등장하더라도 한번만 사용하기 때문에 2번 동작이 끝나면 result에서 $result(1-\frac{1}{p})$로 값을 갱신합니다.
1~3번 과정을 n이 소수 또는 1이 될 때까지 반복합니다. 이때, n은 계속 나눠지므로 1번 단계의 $\sqrt{n}$ 값은 계속 바뀝니다.
4번 과정이 끝났을 때 n은 1 또는 소수의 값을 가지고 있게 됩니다. 만약 $n > 1$이라면 n은 소수이므로 마지막으로 한 번 더 result에 $1-\frac{1}{p}$를 곱해줍니다.
결과적으로 $\phi(n) = result$

ii) 1부터 n까지 계산

1부터 n까지 오일러 피 함수값을 저장할 배열 phi를 생성하고 초기화합니다. 위에서 result = n으로 초기화했던 것과 같은 이유입니다.
인덱스 i를 2부터 n까지 증가시키면서 소수를 찾습니다. 만약 phi[i] == i라면 i는 소수입니다. 그 이유는 아래에서 코드를 보면 명확해집니다.
현재 찾아낸 소수에 대해서 소수의 배수인 j에 대해 전부 $phi[j](1-\frac{1}{i})$로 값을 갱신해줍니다. 이렇게 j가 n보다 작을 때까지 반복합니다.
2~3번 과정을 i가 n 이하일 때까지 반복합니다. 여기서 phi[i] == i라면 i는 소수인 점이 자명해집니다.
결과적으로 phi 배열의 i 인덱스에는 $\phi{i}$의 값이 저장됨

$\phi(n)$을 구하는 구현 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int result = n;

        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) {
                while(n % i == 0) {
                    n /= i;
                }

                result -= result/i;
            }
        }
        
        if(n > 1) {
            result -= result/n;
        }

        System.out.println(result);
    }
}

1. n과 result 변수

int n = Integer.parseInt(br.readLine());
int result = n;

n은 우리가 구할 $\phi(n)$의 n에 해당합니다. n의 크기에 맞게 int 또는 long으로 선언하면 됩니다.

result는 $\phi(n)$의 값이 될 변수입니다.

2. for문

for(int i = 2; i <= Math.sqrt(n); i++) {
    // 생략
}

for문의 목적은 처음 입력된 n의 소인수를 전부 찾는 것입니다. 이때, i를 2부터 시작하는 이유는 1은 어떤 수의 소인수도 될 수 없기 때문입니다.

그리고 i를 Math.sqrt(n)까지 반복하는 이유는 위에서도 언급했다시피 n의 소인수와 n을 소인수로 나눈 수 중에 하나는 반드시 Math.sqrt(n) 이하의 값이기 때문입니다.

참고로 Math.sqrt(n)의 값은 반복문이 끝날때마다 점점 작아집니다.

3. if문

for(int i = 2; i <= Math.sqrt(n); i++) {
    if(n % i == 0) {
        // 생략
    }
}

for문의 i를 점차 증가시키며 n의 소인수를 찾습니다. n % i == 0이 TRUE일 때 GCD(n, i) = 1입니다.

4. while문

for(int i = 2; i <= Math.sqrt(n); i++) {
    if(n % i == 0) {
        while(n % i == 0) {
            n /= i;
        }
        
        // 생략
    }
}

n의 소인수인 i를 하나 발견했습니다. n은 i가 여러번 곱해졌을 수 있기 때문에 while문으로 더이상 나눌 수 없을때까지 n을 i로 나눕니다.

5. result 갱신

result -= result/i;

오일러 피 함수의 정의에 따르면 n의 모든 소인수로 $1-\frac{1}{i}$ 를 곱한다고 했습니다. 이때, result는 n에서 시작해 최종 오일러 피 함수값을 찾아가는 과정의 값입니다.

따라서, 소인수를 발견할 때마다 i가 몇번 곱해졌는지와는 상관없이 result에 $1-\frac{1}{i}$를 한 번만 곱하면 됩니다.

이때 $result\cdot(1-\frac{1}{i})=result - \frac{result}{i}$이므로 아래와 같이 구현할 수 있습니다.

// 1)
result = result - result/i;
// 2) 1번을 간단히 표현하면
result -= result/i;

6. if문

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

초기의 n이 $2^2\cdot3^2\cdot5^3$과 같았다면 for문이 끝났을 때의 n값은 1이 될 것입니다.

하지만 n이 $2^2\cdot3^2\cdot5$과 같았다면 for문이 끝났을 때 n은 5가 될 것입니다. 만약 그렇게 되는 이유를 모르겠다면 아래의 접은 글을 참고해주세요

i) n = $2^2\cdot3^2\cdot5^3$

for문은 현재 n 값의 제곱근까지만 반복함. 이때 $sqrt{n}\approx67$이므로 첫 반복에서 내부의 while문에 의해 2가 2번 제거됨.

$n = 3^2\cdot5^3$으로 변하게 되고 이제 $sqrt{n}\approx33$이므로 다시 while문에 의해 3이 2번 제거됨.

$n = 5^3$으로 변하게 되고 이제 $sqrt{n}\approx11$이므로 다시 while문에 의해 5가 3번 제거됨.

for문이 끝난 직후의 n은 1이 됨

ii) n = $2^2\cdot3^2\cdot5$

i번 케이스와 마찬가지로 동작을 따라가보면 $sqrt{n}\approx13$이므로 첫 반복문에서 내부의 while문에 의해 2가 2번 제거됨.

$n=3^2\cdot5$로 변하게 되고 이제 $sqrt{n}\approx6$이므로 다시 while문에 의해 3이 2번 제거됨.

이제 n은 5가 됐으므로 $sqrt{n}\approx2$가 되고 n=5인 채로 반복문이 종료됨.

이렇게 n의 마지막 소인수까지 result에 반영해줍니다. 현재 n 값 자체가 초기 n의 소인수이므로 result/n값을 뺍니다.

7. result 도출

이렇게 result를 구하는데 성공했습니다.

이제 단순하게 하나가 아니라 1부터 n까지의 모든 오일러 피 함수값을 구해보겠습니다.

$\phi(1)$ ~ $\phi(n)$을 구하는 구현 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] phi = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            phi[i] = i;
        }

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

단일 $\phi{n}$를 구하는 과정에서 동일한 내용을 생략하고 설명하겠습니다.

1. phi 배열 초기화

for (int i = 0; i <= n; i++) {
    phi[i] = i;
}

phi[i] 값은 $\phi{i}$를 의미합니다. 각 phi[i]에 [i]를 저장해줍니다.

2. for문

for (int i = 2; i <= n; i++) {
    // 생략
}

소인수는 소수로만 구성됩니다. 따라서 각 소수의 배수에 대해서만 $1-\frac{1}{i}$ 연산을 해줍니다.

3. if문

for (int i = 2; i <= n; i++) {
    if (phi[i] == i) {
        // 생략
    }
}

phi[i] == i일 때 i가 소수인 이유는 자명합니다. 각 소수의 배수들에 대해서만 phi[i] 값을 갱신하고 있으므로 한 번도 변하지 않았다면 소수입니다.

4. 내부 for문

for (int j = i; j <= n; j += i) {
    phi[j] -= phi[j] / i;
}

소수 i의 배수인 j를 구해서 phi를 갱신하는 반복문입니다.

7. result 도출

이렇게 result를 구하는데 성공했습니다.

마치며

오일러 피 함수 알고리즘을 직접 구현해서 풀어볼만한 문제를 추천드립니다.

11689번 GCD(n, k) = 1 : https://www.acmicpc.net/problem/11689
4335번 서로소 : https://www.acmicpc.net/problem/4355
23832번 서로소 그래프 : https://www.acmicpc.net/problem/23832
19577번 수학은 재밌어 : https://www.acmicpc.net/problem/19577

위의 2문제는 단일 n을 구하는 문제이고, 3번째 문제는 1부터 n까지의 $\phi{n}$을 구하는 문제입니다. 마지막 문제는 오일러 피 함수를 응용해서 풀어볼만한 문제이니 도전해보세요!

질문이나 피드백은 댓글로 환영합니다😊

현재글[Algorithm] 오일러 피 함수로 서로소의 개수 구하기 with JAVA

jundyu 님의 블로그

현재는 알고리즘과 Java 언어 위주로 블로그를 작성하고 있습니다. 백엔드 개발자를 준비 중입니다.

Today :
Yesterday :

jundyu 님의 블로그