약수의 합이 자기자신이 되는 수를 퍼펙트 넘버라고 하고, 약수의 합이 자기 자신보다 클때는 abundant, 약수의 합이 원래수 보다 작으면 deficient 라고 합니다.
예를 들어, 28은 약수가 1, 2, 4, 7, 14이고, 약수들의 합은 원래수인 28이 되어 퍼펙트 넘버가 되고, 12는 1 + 2 + 3 + 4 + 6 = 16 >12 이 되어, abundant 입니다. 또 18의 약수의 합이 1+2+3+6+9 =21 로 abundant입니다.
그래서 24는 abundant인 12와 12의 합으로, 30은 12와 그다음 abundant인 18의 합으로 나타낼수 있습니다.
문제는 이런식으로 28123까지의 수중에서 두 abundant의 합으로 나타낼수 없는 수를 찾는 것입니다. 범위가 28123까지인 이유는 수학적으로 28123 보다 큰 모든 수는 abundant 한 두수의 합으로 표현이 가능하다고 합니다.
일단 abundant 한 숫자들을 찾아야겠네요.(약수의 합이 자기자신보다 큰숫자들)
약수의 합
def divisors(n):
i=2;total={1}
loop = n**0.5
while i<=loop:
if n%i==0:
total.add(i)
total.add(n/i)
i+=1
return sum(total)
divisors(12)
16
12는 가장 작은 abundant 입니다. 약수 합산 코드는 21번 문제에서 가져왔습니다. 속도가 이미 개선된 코드입니다.(제곱근을 취해서 루프크기를 줄인 상태입니다.)
abundant 리스트 만들기
abun=set()
for i in range(1,28124):
if i<divisors(i):
abun.add(i)
len(abun)
6965
28213개의 숫자를 하나씩 다 조사해서, 별도의 변수에다 저장해줬습니다. 6965개의 데이터가 변수안에 저장된거면 맞게 한겁니다. 변수타입은 셋(집합) 말고도 리스트를 사용해도 되는데, 이문제에서는 셋이 편합니다.
메인 루프문
numbers=set(range(28123))
for i in abun:
for j in abun:
if (i+j) in numbers:
numbers.remove(i+j)
그다음은 앞에서 만든 abundant 리스트를 가지고 두개의 중첩된 루프문을 만듭니다. abundant 한 두수의 합을 만드는 코드입니다. 이제 이 코드가 28123의 범위안에 있는지 확인해서, 있으면 미리 만들어 놓은 리스트에서 삭제를 해줍니다. 그러면 남는 숫자가 abundant한 두수의 합으로 나타낼수 없는 숫자입니다.
전체 코드
def divisors(n):
i=2;total={1}
while i<=n**0.5:
if n%i==0:
total.add(i)
total.add(n/i)
i+=1
return sum(total)
abun=set()
for i in range(1,28123):
if i<divisors(i):
abun.add(i)
numbers=set(range(28123))
for i in abun:
for j in abun:
if (i+j) in numbers:
numbers.remove(i+j)
print(sum(numbers))
최적화
def divisors(n):
i=2;total={1}
loop = n**0.5 // while문에서 조건문 분리
while i<=loop:
if n%i==0:
total.add(i)
total.add(n/i)
i+=1
return sum(total)
abun=set()
numbers=set(range(28123))
for i in range(1,28123):
if i<divisors(i):
abun.add(i)
for j in abun:
if (i+j) in numbers:
numbers.remove(i+j)
print(sum(numbers))
비슷한 코드인데, 메인 루프문을 하나로 합쳐주고, 루프를 돌면서 abun 리스트를 동시에 하나씩 추가하는 형태여서, 불필요한 루프문을 줄여서, 계산해야할 루프크기가 절반으로 줄어들었습니다. (사각형 모양에서 절반인 삼각형 모양으로 줄어들었습니다.)
