Daily Algorithm - Day 20

Amicable Numbers

Let $d(n)$ be defined as the sum of proper divisors of $n$ (numbers less than $n$ which divide evenly into $n$).
If $d(a)=b$ and $d(b)=a$, where $a \neq b$, then $a$ and $b$ are an amicable pair and each of $a$ and $b$ are called amicable numbers.

For example, the proper divisors of $220$ are$1,2,4,5,10,11,20,22,44,55$ and $110$;
therefore $d(220)=284$ . The proper divisors of $284$ are $1,2,4,71$ and $142$; so $d(284)=220$.

Evaluate the sum of all the amicable numbers under $10000$.

10000 이하의 친화수(우애수)를 모두 찾아서 그 합을 구하는 문제이다.

내가 생각한 구현 순서는 다음과 같다.

1. $n$의 진약수를 모두 구해 그 합을 출력해주는 함수를 작성
2. $n$이 친화수에 포함되는지 확인해주는 함수를 작성
3. $n$ 이하의 모든 진약수를 합해주는 함수를 작성.

먼저 $n$의 진약수를 모두 합한 값을 출력해주는 함수이다.

//Python

def proper_divs(n):
    divisors = set() # 중복 값을 방지하기 위해 set을 활용
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:  # 사실 필요 없는 부분이지만 divisors의 타입을 바꿀 때를 대비해서
                divisors.add(n // i)
    divisors.discard(n)
    return sum(divisors)

다음은 $n$이 친화수에 포함되는지를 확인해주는 함수다.

def is_amicable(n):
    couple = proper_divs(n)
    if proper_divs(couple) == n:
        return True
    else:
        return False

이제 답을 구할 차례다.

def solution(n):
    result = 0
    for i in range(1, n +1):
        if is_amicable(i):
            result += i
    return result
    
 >>> 40285	# wrong answer

오답이 나와버렸다. 구현 자체는 문제가 없어보이는데... 하고 코드를 리뷰했는데 $a \neq b$ 부분을 놓쳐버렸다. 생각해보니 그건 친화수가 아니라 완전수잖아. 이 부분을 고쳐서 나온 최종 코드는 다음과 같다.

def proper_divs(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:  # 제곱근 중복 제거
                divisors.add(n // i)
    divisors.discard(n)
    return sum(divisors)

def is_amicable(n):
    couple = proper_divs(n)
    if couple != n and proper_divs(couple) == n:
        return True
    else:
        return False
    
def solution(n):
    result = 0
    for i in range(1, n +1):
        if is_amicable(i):
            result += i
    return result

print(solution(10000))

>>> 31626	# correct

오늘은 여기까지
-2025.01.10-