[PE] Project Euler 21

프로젝트 오일러 21번 문제에서 말하는 amicable numbers란, 다음 조건을 만족해야 한다.

- d(x)란 x의 진약수(proper divisor, x를 제외한 x의 양의 약수)들의 합

- x != y 이고, d(x)==y, d(y)==x이면 x, y 둘 다 amicable number

 

이 문제는 10000보다 작은 amicable number들의 합을 구하는 것이 목표다. 이를 위해서 문제를 아래의 과정들로 쪼개겠다.

- 10000보다 작은 양의 정수들을 소인수분해한 결과를 담아놓는 list를 만들고,

- 각 양의 정수마다 d(x)를 계산하는 함수를 만들어서 이 값을 담아놓는 list를 만들고,

- x를 정해서 y=d(x), z=d(y)를 만족하면서 x != d(x)를 만족하는 x들을 찾아 더한다.

 

첫 번째 단계에서 각 숫자마다 소인수분해하는 함수를 만들어서 적용하지 않는 이유는, 이보다 더 유용한 접근 방법이 있기 때문이다. 

n = 10000
 
p = [True for _ in range(n)] # i가 소수인지 여부를 저장한다.
pl = [{} for _ in range(n)] # i를 소인수분해한 결과를 저장한다.
 
for i in range(2,n):
    # p[i]가 소수면 p[i]보다 작은 숫자들의 배수가 아니므로 값이 true다.
    if p[i]:
        for j in range(i, n, i):
            p[j] = False # i의 배수들은 소수가 될 수 없다.
        x = i
        while x<n:
            for j in range(x, n, x):
                if i in pl[j]: # j를 소인수분해한 딕셔너리에 소수 i가 키로 존재하면
                    pl[j][i]+=1 # i로 또 한번 나뉜다는 것이니 1을 더해준다.
                else: # 소인수분해한 딕셔너리에 소수 i가 키로 존재하지 않으면
                    pl[j][i]=1 # i로 나뉜다. 아직은 1번 나뉘므로 1로 초기화.
            x*=i # 어떤 수 j가 i로 k번 나뉘면 이 while문을 돌면서 pl[j][i]=k가 될 것이다.

def divisor_sum(d):
    x = 1
    for k in d:
        x *= (k**(d[k]+1)-1)//(k-1)
    return x
 
ds = [divisor_sum(d)-i for i,d in enumerate(pl)]

해당 함수에 대해서는 이번 글에서 자세히 설명하고 넘어가진 않으려 한다. 이후 정리할 일이 있으면 정리하겠다. 이 함수는 어떤 수 x에 대해서 x의 약수들을 모두 더한 값을 계산해주는데, x도 x의 약수이므로 x까지 더한다. 그렇기 때문에 문제에서 원하는 진약수의 합을 얻기 위해서는 x를 빼주어야 하고, 이를 ds리스트를 만들 때에 반영했다. enumerate 함수를 유용하게 활용했는데, 해당 함수는 이 글에 설명해두었다.

 

여기까지 왔으면 이제 마지막 단계만 수행하면 된다. 이 단계는 앞서 써놓은 수식을 그대로 코드로 옮기면 된다.

n = 10000
 
p = [True for _ in range(n)] # i가 소수인지 여부를 저장한다.
pl = [{} for _ in range(n)] # i를 소인수분해한 결과를 저장한다.
 
for i in range(2,n):
    # p[i]가 소수면 p[i]보다 작은 숫자들의 배수가 아니므로 값이 true다.
    if p[i]:
        for j in range(i, n, i):
            p[j] = False # i의 배수들은 소수가 될 수 없다.
        x = i
        while x<n:
            for j in range(x, n, x):
                if i in pl[j]: # j를 소인수분해한 딕셔너리에 소수 i가 키로 존재하면
                    pl[j][i]+=1 # i로 또 한번 나뉜다는 것이니 1을 더해준다.
                else: # 소인수분해한 딕셔너리에 소수 i가 키로 존재하지 않으면
                    pl[j][i]=1 # i로 나뉜다. 아직은 1번 나뉘므로 1로 초기화.
            x*=i # 어떤 수 j가 i로 k번 나뉘면 이 while문을 돌면서 pl[j][i]=k가 될 것이다.
 
def divisor_sum(d):
    x = 1
    for k in d:
        x *= (k**(d[k]+1)-1)//(k-1)
    return x
 
ds = [divisor_sum(d)-i for i,d in enumerate(pl)]
 
res = []
for x in range(n):
    y = ds[x]
    if x!=y and y<n: # y값이 리스트 크기를 넘어서면 안된다.
        z = ds[y]
        if z<n and z==x:
            res.append(x) # x, y를 다 더할 필요 없다. 나중에 for문이 y로 돌때 추가될 것.
 
print(res) # [0, 1, 220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
print(sum(res)) # 31627

여기서, 0, 1은 amicable number라고 할 수 있을까? 0의 진약수는 없으므로 0이 되어야 하지만 위의 divisor_sum 함수에 {}를 넣으면 1을 리턴할 것이기 때문에 ds[0]값이 1-0 = 1이 되고, 1의 경우에는 divisor_sum 함수에서 1을 리턴하는데 ds[1]값이 1-1 = 0이 되어 두 수가 서로 amicable number가 된다고 해당 코드에서는 판단하게 된다. 이를 고려하여 마지막에서 구한 sum 값에 0, 1을 빼주면 답을 구할 수 있다.