모든 챌린지
보통 0명 해결 정답률 0%

오일러 피 함수

1부터 n까지의 정수 중 n과 서로소인 수의 개수를 셉니다.

배우게 될 내용

  • n의 서로 다른 소인수를 구할 수 있습니다
  • 정수 연산만으로 φ(n) = n × Π(1 − 1/p)를 적용할 수 있습니다
  • n = 1과 n이 소수인 경우를 처리할 수 있습니다

문제

원문 보기 (영어)

오일러 피 함수 φ(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

예시

예시 1
입력:
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입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.