[Python] 백준 4355번(서로소) 문제 풀이

 

def power(A, n):
    res = 1
    while n:
        if n % 2 != 0:
            res *= A
        A *= A
        n //= 2
    return res

def factorization(x): 
    d = 2 
    factorization = []
    while d <= x: 
        if x % d == 0: 
            factorization.append(d)
            x = x / d 
        else: 
            d = d + 1
    return factorization
    
    
while True:
    n = int(input())
    if n == 0:
        break
    primes = factorization(n)
    k = 1
    for p in set(primes):
        k *= power(p, (primes.count(p)-1)) * (p-1)
    print(k)

 

오일러 피 함수(Euler's phi function)와 분할 정복을 이용한 거듭제곱 알고리즘을 사용하여 해결했다.

 

---

 

이 글을 쓰는 데 도움이 되었던 자료들:

 

https://zoosso.tistory.com/243

오일러 피(파이) 함수(Euler's phi function)

 

https://hbj0209.tistory.com/43

[Algorithm] 분할정복을 이용한 거듭제곱