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

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

약수의 합이 자기자신이 되는 수를 퍼펙트 넘버라고 하고, 약수의 합이 자기 자신보다 클때는 abundant, 약수의 합이 원래수 보다 작으면 deficient 라고 합니다. 28123 이하의 수중에서, abundant 한 두수의 합으로 나타낼수 없는 수를 찾아서 합계를 구하는 문제입니다.

 

예를 들어, 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 한 두수의 합으로 표현이 가능하다고 합니다.

 

일단 약수의 합부터 하나씩 구해보도록 하겠습니다.

약수의 합
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 자세히 보기