7088 : 오일러 피 함수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 3
•통과: 1
•만든사람: suakii
문제 설명
오일러 피 함수(Euler's phi function) φ(n)은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수를 나타내는 함수입니다.
자연수 n이 주어졌을 때, φ(n)을 계산하는 프로그램을 작성하십시오.
[제약 조건]
• 자연수 $n$: $1 \le n \le 1{,}000{,}000$
자연수 n이 주어졌을 때, φ(n)을 계산하는 프로그램을 작성하십시오.
[제약 조건]
• 자연수 $n$: $1 \le n \le 1{,}000{,}000$
입력 설명
첫째 줄에 자연수 $n$이 주어집니다. ($1 \le n \le 1{,}000{,}000$)
출력 설명
$\phi(n)$의 값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
오일러 피 함수의 공식은
φ(n)을 소인수분해 알고리즘을 변형하여 구할 수 있습니다.
φ(n) = n * ∏ (1 - 1/p) (단, p는 n의 소인수) 입니다.φ(n)을 소인수분해 알고리즘을 변형하여 구할 수 있습니다.