문제
오일러 피 함수 φ(n)은 1 ≤ k ≤ n이고 gcd(k, n) = 1인 정수 k의 개수입니다. 예를 들어 1, 2, 4, 5, 7, 8은 9와 서로소이므로 φ(9) = 6입니다.
eulers_totient(n) 함수를 구현하세요.
n이 최대 10^12이므로 k를 하나씩 세면 너무 느립니다. 대신 곱 공식 φ(n) = n × (1 − 1/p)를 쓰세요. 여기서 (1 − 1/p)는 n을 나누는 서로 다른 소수 p마다 하나씩 곱합니다. 정수로 n / p × (p − 1)처럼 계산하면 분수를 쓰지 않아도 됩니다.
입력
n: 양의 정수입니다.
출력
φ(n)을 반환합니다. 정의에 따라 φ(1) = 1입니다.
제약 조건
1 ≤ n ≤ 10^12
예시
입력:
n = 36
예상 출력:
expected = 12
입력:
long long n = 36;
예상 출력:
long long expected = 12;
입력:
long n = 36;
예상 출력:
long expected = 12;
설명
36 = 2² × 3²이므로 φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12입니다.
입력:
n = 13
예상 출력:
expected = 12
입력:
long long n = 13;
예상 출력:
long long expected = 12;
입력:
long n = 13;
예상 출력:
long expected = 12;
설명
13은 소수이므로 1부터 12까지의 모든 k가 13과 서로소이고, φ(13) = 12입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
√n까지 나누어 보며 n을 소인수분해하세요.
힌트 2
서로 다른 소수 p마다 결과를 결과 / p × (p − 1)로 바꾸세요. 먼저 나누어야 값이 작게 유지됩니다.
힌트 3
반복문이 끝난 뒤 남은 1보다 큰 인수도 소수입니다.
예상 복잡도
시간 O(√n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.