(JavaScript) 정수론 - 오일러 피

백준 11689번 문제인 GCD(n, k) = 1 문제는 정확히 오일러 피를 묻는 문제이다.

 

오일러 피 공식만 코드로 구현하면 끝나는데 난이도가 골드1로 꽤 높은 편이다. 주어지는 수의 범위가 10의 12승으로 매우 커서 오일러 피의 원리를 모르고 단순히 탐색으로 문제를 풀면 시간초과가 발생하기때문에 그런것 같다.

 

 

1. 오일러 피 함수란?

오일러 피 함수란 자연수 n에 대해 n과 서로소(공약수가 1뿐인 수)인 n이하의 자연수 개수를 구하는 함수이다.

 

ex) n=12 일때

• n 이하의 자연수중 n과 서로소인 수 : 1, 5, 7, 11
• 12에 대한 오일러 피 함수 결과 = 4

 

 

2. 오일러 피 함수의 원리와 사용법

먼저 오일러 피 함수를 구현한 코드를 보면 아래와 같다.

function eulerPhi(n) {
  let result = n;

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

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

  return result;
}

 

작동원리를 알아보자.

 

 

2-1. 핵심 작동 원리 : 소인수들의 배수들을 빼서 서로소를 찾자

주어진 수 이하에서 주어진 수와 서로소인 수를 구해야 한다.

다르게 말하면, 서로소가 아닌 수를 제거하면 서로소의 수를 구할 수 있다.

 

주어진 수와 서로소가 아닌수는 주어진 수의 소인수의 배수이다.

문장이 어려운데 이를 예시로 보면

 

ex) n = 30일때 φ(30) 구하기

• 30은 2 * 3 * 5 이므로 30의 소인수는 2, 3, 5 이다.
• 30 이하의 수 중 30과 서로소인 수의 개수를 구하는것이 목표이다.
• 반대로 말하면 30개의 수중 30과 서로소가 아닌 수의 개수를 빼면 된다.
• 30과 서로소가 아닌 수는 2의 배수, 3의 배수, 5의 배수 이다.

30이하의 수 중 2의 배수는 15개, 3의 배수는 10개, 5의 배수는 6개 이다. 하지만 이를 전부 빼면 중복을 빼게 된다.

• 예를들어 2의 배수에서도 10이 제외되고 5의 배수에서도 10이 제외되어 같은수가 여러번 제외된다.

그렇기 때문에 중복이 제거되지 않도록 처리를 해줘야한다. 여기서는 포함-배제 원리를 사용한다.

 

• 2 ∩ 3 = 6의 배수: 5개
• 2 ∩ 5 = 10의 배수: 3개
• 3 ∩ 5 = 15의 배수: 2개
• 2 ∩ 3 ∩ 5 = 30의 배수: 1개

최종적으로 서로소가 아닌 수의 개수는 다음과 같다.

• (2의 배수) + (3의 배수) + (5의 배수) - (2 ∩ 3) - (2 ∩ 5) - (3 ∩ 5) + (2 ∩ 3 ∩ 5)
• 15 + 10 + 6 - 5 - 3 - 2 + 1 = 22

30에서 서로소가 아닌 수를 빼면 30 이하에서 30과 서로소인 수를 구할 수 있다.

• 30 - 22 = 8
• φ(30) = 8

 

 

2-2. 공식으로 일반화하기

위의 과정을 공식으로 만들어야한다.

주어진 수 n의 소인수가 {p1, p2, ..., pk} 라고 하면 전체 수 n개 중에서

 

• p1의 배수 = n / p1 개
• p1 ∩ p2의 배수 = n / (p1 * p2) 개
• ...

이를 식으로 정리하면 다음과 같다.

φ(n) = n × (1 - 1/p1 - 1/p2 + 1/(p1p2) + ...)
식을 전개하면
φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)

 

정리된 식을 보면 주어진 수 n에 (1 - 1/n의 소인수)를 모두 곱해주면 된다. 위에서 본 오일러 피 함수 소스코드는 이 과정을 반복문으로 작성한것이다.

 

 

2-3. 소스코드 해석

function eulerPhi(n) {
  // 주어진 수 n
  let result = n;

  // 1은 제외하고 2부터 소인수를 찾는다.
  for(let p = 2;p*p <= result;p++) {
    if (n % p === 0) {
    // p가 소인수이면 연산을 수행
      while (n % p === 0) {
      // 나눗셈 후 남은 소수를 연산하기 위한 while문
        n /= p;
      }
      // 오일러 피 공식 계산
      result -= result / p;
    }
  }
  
  // 계산 후 남은 소수 오일러 피 공식 계산
  if (n > 1) result -= result / n;

  return result;
}

• 주어진 수 n에 대해 오일러 피 계산을 수행한다.
• 약수를 찾을때는 주어진 수의 제곱근까지만 계산하면 된다.
  ( (JavaScript) 정수론 - 소수 판별하기 정수론 - 소수 판별 참조)
• p가 소인수이면 연산을 수행한다. 여기서 오일러 피 연산부분은 result -= result / p 이다.

while문과 뒤의 if문은 제곱근까지 약수를 계산하는 소스코드 특성상 한계를 보완하기위한 장치이다. 제곱근까지의 약수로 수를 나눌 수 있을때까지 나누면 소수가 남게된다. 약수로 나누지 못한 수 이기 때문이다. 마지막 조건문은 남아있는 소수에 대해 마지막 오일러피 연산을 진행한다.

• while문은 소인수를 발견하면 주어진 수를 나눌 수 있을때까지 나눈다.
• 이 과정을 반복하면 제곱근까지의 약수로 주어진수를 나눌수있을때까지 나눈 결과가 된다.
• 예를들어 주어진수가 99 라면 3으로 두번 나누어 11이 되고 for문은 제곱근까지 연산하므로 11을 연산하지 않고 n이 11로 남는다.
• 마지막 if문에서 11에 대해 오일러피 연산을 진행한다.

입력한 수가 소수인 경우에도 이 과정이 필요하다. 소수이면 반복문 내에서 약수로 판단되는 수가 없어 아무런 연산이 진행되지 않으므로 자기 자신에 대해 오일러 피 연산 한번만 수행하면 된다.

(소수는 약수가 없으므로 소수의 서로소개수는 주어진수-1 이다.)

 

 

 

3. 예제

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

• 소스코드

const readline = require("readline");

const solution = (input) => {
    input = Number(input[0]);
    let result = input;

    for (let p = 2; p * p <= input; p++) {
        if (input % p === 0) {
            while (input % p === 0) {
                input /= p;
            }
            result -= result / p;
        }
    }

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

    return result;
};

const input = [];
readline
    .createInterface({
        input: process.stdin,
        output: process.stdout,
    })
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        console.log(solution(input));
    });

• 설명

백준 입력부분을 제외하고는 위에 작성한 오일러 피 함수와 같은 내용이다.

 

 

 

 

 

📖 이 글은 학습 과정에서 정리한 내용이라 부족한 점이 있을 수 있습니다.
☑️ 틀린 부분이 있다면 편하게 알려주셔도 괜찮습니다.
😊 읽어주셔서 감사합니다.