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
반응형
'알고리즘 > [python] 백준 BOJ' 카테고리의 다른 글
[python] 백준 1033 칵테일 (2) | 2023.02.24 |
---|---|
[python] 백준 1850 최대공약수 (0) | 2023.02.24 |
[python] 백준 1747 소수&팰린드롬 (0) | 2023.02.23 |
[python] 백준 1456 거의 소수 (0) | 2023.02.23 |
[python] 백준 1744 수 묶기 (0) | 2023.02.23 |
댓글