파이썬_실전 프로젝트

프로젝트 오일러 21번문제 - Amicable Number

Amicable Number 라는 수가 있습니다. 한글로는 친화수 또는 우애수라고 하네요.

서로가 약수의 합이 되는 두수를 말합니다. 1000 이하의 모든 Amicable Number의 합을 구하는 문제입니다.

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 ab, 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.

 

해당규칙의 함수를 만들고, 루프를 돌면서 합산을 하면 되겠네요.

 

약수의 합을 반환해 주는 함수
def getSumOfDivisors(number):
    total=0
    for i in range(1,number):
        if number%i==0:       #약수인지 판단
            total=total+i    #약수이면 합산
    return(total)
    
print(getSumOfDivisors(220))

 

약수의 합의 다시 약수의 합계산.
def getSumOfDivisors(number):
    total=0
    for i in range(1,number):
        if number%i==0:       
            total=total+i    
    return(total)

print(getSumOfDivisors(getSumOfDivisors(220)))  # 함수로 나온값을 다시 함수로 전달.

 

Amicable 인지 판단해서 합산
def getSumOfDivisors(number):
    total=0
    for i in range(1,number):
        if number%i==0:       
            total=total+i    
    return(total)

grandTotal=0
for i in range(1,10001):
    if i == getSumOfDivisors(getSumOfDivisors(i)):
        grandTotal = grandTotal + i
print(grandTotal)
40284

 

이렇게만 하면 답이 될줄 알았는데, 잘못 계산했네요.

1. 먼저, Amicable 일경우, 두 수가 짝으로 존재하기때문에, 모두 더해줘야합니다.

2. 루프를 순차적으로 돌다보면, 다른루프에서 같은 amicable number 가 생겨서 중복이 될수도 있습니다.

 

그럼 조금 수정하도록 하죠.

수정
def getSumOfDivisors(number):
    total=0
    for i in range(1,number):
        if number%i==0:       
            total=total+i   
    return(total)

grandTotal=0
grandTotalList=[]
for i in range(1,10001):
    result_a = getSumOfDivisors(i)
    result_b = getSumOfDivisors(result_a)
    if i == result_b and i != result_a:
        print(i,result_a,"are Amicable number")
        if i not in grandTotalList:
            grandTotal = grandTotal + i
            grandTotalList.append(i)
        if result_a not in grandTotalList:
            grandTotal = grandTotal + result_a
            grandTotalList.append(result_a)

print(grandTotal)
print(grandTotalList)
220 284 are Amicable number
284 220 are Amicable number
1184 1210 are Amicable number
1210 1184 are Amicable number
2620 2924 are Amicable number
2924 2620 are Amicable number
5020 5564 are Amicable number
5564 5020 are Amicable number
6232 6368 are Amicable number
6368 6232 are Amicable number
31626
[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

댓글

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