안녕하세요! 오늘은 파이썬으로 오일러 피 함수(Euler’s Totient Function)를 구현하는 방법을 알아보겠습니다. 이 글에서는 오일러 피 함수의 정의와 성질을 살펴보고, 효율적으로 구현하는 방법에 대해 단계적으로 설명할 것입니다.
1. 오일러 피 함수란?
오일러 피 함수 φ(n)은 1과 n 사이의 정수 중에서 n과 서로소인 수의 개수를 나타내는 함수입니다. 즉, φ(n)은 n과 공약수를 가지지 않는 수의 수를 의미합니다. 예를 들어:
- φ(1) = 1 (1은 자신만과 서로소)
- φ(2) = 1 (1만이 2와 서로소)
- φ(3) = 2 (1, 2가 3과 서로소)
- φ(4) = 2 (1, 3이 4와 서로소)
- φ(5) = 4 (1, 2, 3, 4가 5와 서로소)
2. 오일러 피 함수의 성질
오일러 피 함수는 몇 가지 중요한 성질을 가지고 있습니다:
- 만약 n이 소수 p라면, φ(p) = p – 1
- 만약 n이 소수의 거듭제곱 p^k라면, φ(p^k) = p^k(1 – (1/p))
- n이 두 정수 a와 b의 곱이라면, φ(ab) = φ(a) * φ(b) * (1 – (1/gcd(a,b)))
2.1 예시
주어진 수 n의 오일러 피 함수 값 φ(n)을 구해야 한다면, n의 소인수를 찾아야 합니다. 예를 들어 n = 12이 주어진 경우, 소인수는 2와 3이며, 이 두 소수에 대한 φ 값을 사용하여 φ(12)를 계산할 수 있습니다.
3. 오일러 피 함수 구현 방법
지금부터 φ(n)을 효율적으로 구현하는 방법을 알아보겠습니다. 기본적인 접근 방식은 각각의 수를 확인해서 서로소인 수의 개수를 세는 것인데, 이는 비효율적이므로 개선할 필요가 있습니다.
3.1 에라토스테네스의 체 방식
오일러 피 함수를 효율적으로 구현하는 방법 중 하나는 에라토스테네스의 체(Sieve of Eratosthenes)의 개념을 사용하는 것입니다. 다음은 φ(n)을 계산하는 로직입니다:
def euler_totient(n):
# 1부터 n까지의 페어 배열 초기화
phi = list(range(n + 1))
# 에라토스테네스의 체를 사용하여 오일러 피 함수 값 계산
for i in range(2, n + 1):
if phi[i] == i: # i가 소수일 경우
for j in range(i, n + 1, i):
phi[j] *= (i - 1)
phi[j] //= i
return phi3.2 코드 분석
위의 코드는 다음과 같이 작동합니다:
- φ 배열을 1부터 n까지 초기화합니다. 즉, φ[i]는 처음에는 i로 설정됩니다.
- 2부터 n까지의 모든 수 i에 대해, i가 소수인지 확인합니다. 이 경우, φ 배열을 업데이트합니다.
- j는 i의 배수로 설정하여 해당 배수의 φ 값을 갱신합니다.
4. 시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n log log n)입니다. 이는 에라토스테네스의 체와 유사하여, 매우 효율적으로 φ(n)을 계산할 수 있습니다. 작은 n의 경우에만 이 알고리즘을 사용하실 수 있으나, 큰 n의 경우에도 충분히 빠른 성능을 유지합니다.
5. 예제
다음은 이 알고리즘을 사용하여 n = 10까지의 오일러 피 값을 계산하고 출력하는 예제입니다:
if __name__ == "__main__":
n = 10
result = euler_totient(n)
print(f"n = {n} 까지의 오일러 피 함수 값: {result[1:]}")5.1 출력 예시
n = 10 까지의 오일러 피 함수 값: [1, 1, 2, 2, 4, 4, 6, 6, 8, 4]6. 결론
이번 글에서는 오일러 피 함수의 정의, 성질, 구현 방법에 대해 알아보았습니다. 고전적인 방식 대신 에라토스테네스의 체를 활용하면 효율적으로 φ(n)을 구할 수 있다는 점이 인상적입니다. 앞으로 다른 알고리즘과 자료구조를 배우면서 더 복잡한 문제들도 해결해 나가길 바랍니다.
7. 참고 자료
지금까지 함께 해주셔서 감사합니다! 다음 시간에도 더 유익한 알고리즘 강좌로 찾아뵙겠습니다.