파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 23번 문제 - abundant number

약수의 합이 자기자신이 되는 수를 퍼펙트 넘버라고 하고, 약수의 합이 자기 자신보다 클때는 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 한 두수의 합으로 표현이 가능하다고 합니다.

1. 첫번째 접근 방법은, 단순하게 1부터 모든 경우를 다 체크하는 방법입니다. 이방법은, 숫자가 커질수로 계산량이 많아져서 시간이 많이 걸리는 단점이 있습니다.
2. 몇번 시행착오끝에, abundant list 가 많지 않다는걸 알게됐고, 이 리스트를 먼저 만들고, 거꾸로 숫자를 조합해서 제외해 가면, 남는 수들이 문제의 답이 되서, 시간이 많이 절약되는걸 알게됐네요.

일단 순서대로 보기로 하죠.

약수의 합
def sumFactors(number):
    total=0
    for i in range(1,number):
        if number%i==0:
            print(i,end=';')
            total+=i
    return total

for i in range(1,20):
    print("loop:",i,end=', ')
    print("  sum:",sumFactors(i))
loop: 1,   sum: 0
loop: 2, 1;  sum: 1
loop: 3, 1;  sum: 1
loop: 4, 1;2;  sum: 3
loop: 5, 1;  sum: 1
loop: 6, 1;2;3;  sum: 6
loop: 7, 1;  sum: 1
loop: 8, 1;2;4;  sum: 7
loop: 9, 1;3;  sum: 4
loop: 10, 1;2;5;  sum: 8
loop: 11, 1;  sum: 1
loop: 12, 1;2;3;4;6;  sum: 16
loop: 13, 1;  sum: 1
loop: 14, 1;2;7;  sum: 10
loop: 15, 1;3;5;  sum: 9
loop: 16, 1;2;4;8;  sum: 15
loop: 17, 1;  sum: 1
loop: 18, 1;2;3;6;9;  sum: 21
loop: 19, 1;  sum: 1
약수의 합 (속도 개선)

소수확인하는 코드와 유사하게 제곱근을 취해서 루프 크기를 줄여줍니다. 단, 10 이하에서는 제곱근을 취하면, 약수를 계산하기가 곤란해서, 10이하일때는 제곱근을 취하지 않도록 분류해주었습니다.

def sumFactors(number):
    if number <= 10:
        total=0
        for i in range(1,number):
            if number%i==0:
                print(i,end=';')
                total+=i
    else:
        total=1
        loop = number**0.5
        i=2
        while i<=loop:
            if number%i==0:
                print(i,end=';')
                total+=i
                if i**2 != number:
                    total+=number//i
            i+=1
    return total

for i in range(1,20):
    print("loop:",i,end=', ')
    print("  sum:",sumFactors(i))
loop: 1,   sum: 0
loop: 2, 1;  sum: 1
loop: 3, 1;  sum: 1
loop: 4, 1;2;  sum: 3
loop: 5, 1;  sum: 1
loop: 6, 1;2;3;  sum: 6
loop: 7, 1;  sum: 1
loop: 8, 1;2;4;  sum: 7
loop: 9, 1;3;  sum: 4
loop: 10, 1;2;5;  sum: 8
loop: 11,   sum: 1
loop: 12, 2;3;  sum: 16
loop: 13,   sum: 1
loop: 14, 2;  sum: 10
loop: 15, 3;  sum: 9
loop: 16, 2;4;  sum: 15
loop: 17,   sum: 1
loop: 18, 2;3;  sum: 21
loop: 19,   sum: 1

 

is_abundant() 로 함수 변경. boolean 값 return

sumFactors()는 약수의 합만 리턴해줬는데, 좀더 편하게 abundant인지까지 판단해서 반환해주도록 하겠습니다.

def is_abundant(number):
    if number <= 10:
        total=0
        for i in range(1,number):
            if number%i==0:
                total+=i
    else:
        total=1
        loop = number**0.5
        i=2
        while i<=loop:
            if number%i==0:
                total+=i
                if i**2 != number:
                    total+=number//i
            i+=1
    if total > number:
        return True
    return False

for i in range(1,10000):
    if is_abundant(i):
        print(i,end=',')

 

 

Abundant 한 두수의 합으로 나타낼수 있는 수
def is_abundant():
    # 생략

for i in range(1,100):
    for j in range(1,i):
        if is_abundant(j) and is_abundant(i-j):
            print("loop:",i,j,i-j)
            break
loop: 24 12 12
loop: 30 12 18
loop: 32 12 20
loop: 36 12 24
loop: 38 18 20
loop: 40 20 20
loop: 42 12 30
...
...
Abundant 한 두수의 합으로 나타낼수 없는 수 (100까지)
def is_abundant():
    # 생략

grand_total =0
for i in range(1,100):
    abundant = False
    for j in range(1,i):
        if is_abundant(j) and is_abundant(i-j):
            abundant = True
            break
    if abundant == False:
        grand_total += i
        print("loop:",i)
        
print(grand_total)
loop: 1
loop: 2
loop: 3
loop: 4
loop: 5
loop: 6
loop: 7
...
...
loop: 91
loop: 93
loop: 95
loop: 97
loop: 99
Abundant 한 두수의 합으로 나타낼수 없는 수 (28123까지)

100까진 괜찮았는데, 28123까지 하니, 속도가 많이 느립니다. 매루프마다 모든 수를 abundant한지를 두번씩 호출 해야할뿐더러, 루프 자체도 중첩되어 있습니다,,

def is_abundant():
    # 생략

grand_total =0
for i in range(1,28124):
    abundant = False
    for j in range(1,i):
        if is_abundant(j) and is_abundant(i-j):
            abundant = True
            break
    if abundant == False:
        grand_total += i
        print("loop:",i,end=',')
        
print(grand_total)
loop: 1
loop: 2
loop: 3
loop: 4
loop: 5
loop: 6
loop: 7
loop: 8
loop: 9
loop: 10
loop: 11
....
...

 

Abundant 한 두수의 합으로 나타낼수 없는 수 (28123까지), 속도개선

이번에는 모든수를 조사하지 않고, abundant한 리스트를 만들어서, 그 리스트로 루프문을 돌려보겠습니다. 이경우엔, abundant 를 확인하는 함수는 모든수에 대해서 딱 한번씩만 호출됩니다. 그리고 루프문에서 두 abundant 수의 합이 28123 안쪽에 있는지만 확인하면 됩니다.

import time
start_time = time.time()

def is_abundant():
    # 생략

abundant_list=[]
for i in range(1,28123):
    if is_abundant(i):
        abundant_list.append(i)

total_list=list(range(1,28123))

for i in abundant_list:
    for j in abundant_list:
        if i+j<28123:
            total_list[i+j-1]=0

print(sum(total_list))
print("calculation time:",time.time()-start_time)
4179871
calculation time: 23.2755389213562

 

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기