백준 골드1 11689번 Python

틀린 문제

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

 

풀이

import math


n = int(input())
# 소인수 분해 
# 소인수 분해한 결과를 오름차순으로 정렬, set 을 이용해 중복이 없게 처리

def get_unique_prime_factors(n: int) -> list[int]:
    """
    주어진 양의 정수 n을 소인수 분해하여 
    중복 없이 오름차순으로 정렬된 소인수 리스트를 반환합니다.
    """
    if n <= 1:
        return []

    # 1. 중복을 자동으로 제거하기 위해 set을 사용합니다.
    unique_factors = set()
    
    # 2. 나누는 수 (제수)를 가장 작은 소수인 2부터 시작합니다.
    d = 2
    
    # 3. d * d <= n 일 때까지만 반복합니다. (효율성을 위한 최적화)
    # n의 소인수는 sqrt(n) 이하에 적어도 하나 있거나, n 자체가 소수입니다.
    while d * d <= n:
        # n이 d로 나누어 떨어지는 경우:
        if n % d == 0:
            # d는 소인수이므로 set에 추가 (중복 방지)
            unique_factors.add(d)
            
            # d로 더 이상 나누어 떨어지지 않을 때까지 계속 나눕니다.
            # 이 과정이 d의 거듭제곱 인수를 모두 제거해줍니다.
            while n % d == 0:
                n //= d
        
        # 나누어 떨어지지 않으면 다음 수로 넘어갑니다.
        d += 1
        
    # 4. 반복문 종료 후 n이 1보다 크다면,
    # 남아있는 n은 (sqrt(최초의 N)보다 큰) 마지막 소인수입니다.
    if n > 1:
        unique_factors.add(n)
        
    # 5. set을 list로 변환하고 오름차순으로 정렬하여 반환합니다.
    return sorted(list(unique_factors))

num = get_unique_prime_factors(n)


ans = n 

for i in range(len(num)):
    ans *= (1 - (1/num[i]))

print(math.floor(ans))

 

- 왜 못풀었는가?

오일러 피 함수의 개념을 알지 못했다. 

- 새롭게 무엇을 알았는가?

오일러 피 함수를 이용해 GCD 의 개수를 구할 수 있음을 알았다. 

- 다음에 비슷한 유형을 반드시 풀려면 어떤 점을 기억해야할까?

오일러 피 함수 공식을 기억해야 한다. 

소인수 분해하는 법을 기억해야 한다. 

 

오릴러 피 함수 공식:

parray = [N을 소인수 분해한 것을 오름차순으로 정렬한 것]

GCD(N)의 개수 = N(1-1/p1)*(1-1/p2)...(1-1/pn)

 

소인수 분해하는 함수에서, 처음에는 왜 d*d <= n 까지만 고려하면 되는지 이해를 못했다. 

그러나 해당 반복문에서 하는 역할이 "가장 작은 소인수를 찾는 것" 이고, 

모든 소인수가 루트n 보다 크다면, 2개만 곱해도 n을 넘어버리기 때문에 불가함을 알게 되었다. 

따라서 가장 작은 소인수는 무조건 루트 n보다 작거나 같을 수 밖에 없던 것이다. -> 이 부분 이해가 어려운 것이 맞다. 

 

또, 소인수 분해하는 함수에서 왜 마지막에 n이 1보다 크면, 그것을 마지막 소수라고 생각하는지 이해를 못했다. 

그러나 반복문에서 하는 것은, 루트 N보다 작은 모든 수로 더이상 나눠떨어지지 않을 때까지 나누는 것이었고, 그렇기 때문에 결국 마지막에 나온 소수는, 루트N보다 큰 소수 하나밖에 없음을 알게 되었다. -> 이 부분 이해가 어려운 것이 맞다. 

 

그런데 이 두 헷갈리는 포인트는 사실, 하나의 가정에서 출발했다. 즉 N을 소인수 분해 한 결과는 모두 루트 N이하이거나, 루트N보다 큰 소인수는 1개 밖에 없다는 것이다. 

이것을 다음과 같이 증명할 수 있다. 

만약 루트 N보다 큰 소인수가 2개 이상 있었다고 가정해보자. 

그럼 이 둘을 곱한 결과 이미 N을 넘어버리게 된다. 따라서 루트N보다 큰 소인수는 많아야 1개뿐이다. (없을 수도 있다.)