041 GCD(n, k) = 1

첫번째 코드

 

사실 오일러의 피 개념에 대해서는 어느정도 이해를 했는데

결과가 결국 어떤 것을 의미하는 것인지에 대해서 의문이었다.

 

이 책의 코드를 통해서 이해가 되었다.

특정 값의 소인수의 개수를 말해주는 것이었다.

 

이 코드에서 n과 result를 따로 움직인다.

그리고 마지막에 1개의 누락된 소인수를 챙겨주는 과정을 거친다.

 

개념에 대한 이해가 되어 코드 구성은 이해가 되지만

소소하게 챙길 부분이 좀 있다고 생각이 들었다.

이번에 존재와 이해정도로 만족하고 다음에 다시 풀면서 온전한 이해와 코드 구성을 기대한다.

 

import sys
import math
input = sys.stdin.readline

n = int(input())
result = n

for i in range(2, int(math.sqrt(n)+1)):
    if n % i == 0:
        result -= result/i
        while n % i == 0:
            n /= i

if n > 1:
    result -= result / n

print(int(result))

 

통과:_

---

링크

https://github.com/ornni/programmers/blob/main/%EB%B0%B1%EC%A4%80/Gold/11689.%E2%80%85GCD%EF%BC%88n%EF%BC%8C%E2%80%85k%EF%BC%89%E2%80%85%EF%BC%9D%E2%80%851/GCD%EF%BC%88n%EF%BC%8C%E2%80%85k%EF%BC%89%E2%80%85%EF%BC%9D%E2%80%851.py

programmers/백준/Gold/11689. GCD（n， k） ＝ 1/GCD（n， k） ＝ 1.py at main · ornni/programmers