본문 바로가기
알고리즘/[python] 백준 BOJ

[python] 백준 11689 GCD(n, k) = 1

by Alan_Kim 2023. 2. 24.
728x90
반응형

https://www.acmicpc.net/problem/11689

 

11689번: GCD(n, k) = 1

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

문제 풀이

  • n의 약수 중 소수인 것을 $p_{1}, p_{2}, ... p_{a}$ 라 할 때 소수의 개수는 다음과 같이 구할 수 있다.
    • $\phi$ (n) = n $\times \prod_{i=1}^{a} (1-\frac{1}{p_{i}})$
  • 시간초과가 나지 않게 리스트를 사용하지 않고 for문을 돌면서 소수를 찾으면 ans -= ans/p 를 한 다음 n에서 소수 p의 흔적을 없앤다. p를 약수로 갖지 않을 때 까지 계속 나눠준다는 것이다.

CODE

import sys
input = sys.stdin.readline
import math
n = int(input())
ans = n
for i in range(2,int(math.sqrt(n))+1):
    if n%i ==0:
        ans -= ans/i
        while n%i ==0:
            n/=i
if n>1:
    ans -= ans/n
print(int(ans))
728x90
반응형

댓글