알고리즘 - 오일러 피 함수

오일러 피 함수 (Euler phi function)

---

알고리즘 문제에서 주로 나오는 정수론 중 하나인 오일러 피 함수입니다.

 

오일러 피 함수란 다음과 같습니다.

 

오일러 피 함수

쉽게 말해, 1부터 n까지 범위에서 n과 서로소인 자연수의 개수를 뜻합니다.

 

🎈 서로소란 공약수가 1뿐이 없는 두 정수를 의미합니다.

 

예를 들어, 1 ~ 10 까지 범위에서 10과 서로소인 자연수를 나열해보면 다음과 같습니다.

 

• 1 , 3, 7, 9

 

 

🔨 구현

---

다음과 같은 과정을 통해 오일러 피 함수를 프로그래밍 언어로 구현할 수 있습니다.

 

📌 1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화

 

 

 

📌 2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = P[i] - P[i] / K 연산을 수행 (i는 K의 배수)

 

N = P[N] = 2이기 때문에 연산 수행

N = P[N] = 3 이기 때문에 연산 수행

 

 

📌 3. 배열의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성

 

최종 결과

 

배열에 완성된 값들은 N이 가지는 서로소의 개수를 의미합니다.

 

위의 과정을 자바 코드로 구현하면 다음과 같습니다.

public class EulerPhi {

   // 단순 반복문 계산
   public static int func1(int N) {

      int[] arr = IntStream.range(0, N + 1).toArray();

      for (int i = 2; i < arr.length; i++) {
         if (arr[i] == i) {

            for (int j = i; j < arr.length; j += i) {
               arr[j] = arr[j] - arr[j] / i;
            }
         }
      }

      return arr[N];
   }

}

 

위의 코드는 배열을 이용해서 구하는데, 이렇게 구하게 되면 여러 수들의 서로소가 몇 개인지 한 번에 알 수 있습니다. 

다만, N값이 큰 값이 주어졌을 때, 배열을 이용하지 못하는 경우가 생깁니다.

 

그럴 땐, 다음과 같이 구현하면 됩니다.

 

public class EulerPhi {

   // 소인수 분해 이용

   /**
    * 1보다 큰 모든 정수는 소수이거나 합성수이며, 합성수는 소수들의 곱(소인수)으로 이루어져있다.
    * rp = 서로소 개수
    * k = 인덱스(소수)
    * pf = 소인수로 이루어져있는 수(합성수)
    */
   public static int func2(int N) {

      int rp = N;
      int pf = N;

      // 소수는 주어진 값의 제곱근까지만 돌려보면 알 수 있기 때문에 루트 N까지만
      for (int k = 2; k <= Math.sqrt(N); k++) {
         // 소인수로 구성된 수가 k로 나눠 떨어진다면, k는 소인수 중 하나
         if (pf % k == 0) {
            // 오일러의 피 함수 연산
            rp = rp - rp / k;

            // 소인수 분해 하여 해당 회차에서 이용한 소인수를 제거
            while (pf % k == 0) {
               pf /= k;
            }
         }
      }

      // 소인수가 1보다 크면 소인수가 아직 남아있다는 소리이므로 연산 진행
      if (pf > 1) {
         rp = rp - rp / pf;
      }

      return rp;
   }

}

 

위의 코드는 소인수 분해를 이용하여 작성한 코드입니다.