문제 설명
오일러의 피 함수(Euler’s totient function) φ(n)은 1부터 n까지의
정수 중 n과 서로소인 수의 개수를 센 함수입니다. 예를 들어,
φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4입니다.
주어진 양의 정수 n에 대해 φ(n) 값을 계산하는 코드를 작성하시오.
단, n은 1과 10^6 사이의 값입니다.
문제 해결 과정
1. 문제 이해하기
이 문제는 오일러의 피 함수의 정의를 기반으로 하며,
n과 서로소인 모든 수를 찾아야 합니다. 서로소란 두 수의
최대공약수가 1인 것을 말하며, 이 조건을 이용해
φ(n)을 구할 수 있습니다.
2. 알고리즘 설계
오일러 피 함수는 기약분수의 형태로 표현할 수 있습니다. 이를 통해 n의 소인수를 찾아
서로소의 개수를 구할 수 있습니다. n의 소인수 p에 대하여,
φ(n) = n × (1 – 1/p)입니다. n의 모든 소인수에 대해 이 식을 적용하면 됩니다.
3. 코드 구현
먼저 소인수를 찾는 함수를 구현한 후, 이를 이용해
φ(n)을 계산하는 코드를 작성하겠습니다.
def euler_totient(n):
result = n # 초기값은 n
p = 2
while p * p <= n: # 소인수를 찾기
if n % p == 0: # p가 n의 소인수인지 확인
while n % p == 0: # p에 해당하는 소인수를 제거
n //= p
result -= result // p # 서로소 개수 계산
p += 1
if n > 1: # 마지막으로 남은 소인수
result -= result // n
return result
4. 예제와 테스트
φ(10)을 계산해보겠습니다. φ(10)은 5와 2의 소인수를 가집니다.
이를 통해 φ(10) = 10 × (1 – 1/2) × (1 – 1/5) = 4가 됩니다.
print(euler_totient(10)) # 출력: 4
5. 결론
오일러 피 함수는 수론에서 매우 중요한 개념으로,
고급 알고리즘을 구현하는 데 있어 필수적인 지식을 제공합니다.
이 문제를 통해 이러한 기반 지식을 확립할 수 있습니다.