python

[Python] 21 – Amicable Numbers

[문제 링크]
http://projecteuler.net/problem=21

[문제 원본]
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 a ≠ b, 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.

[문제 풀이]

  • 반복문에서 수를 감소시키며 숫자의 약수의 합을 구한다.
  • 1에서 구해진 약수의 합의 수의 약수의 합을 구한다.
  • 2에서 구해진 값과 진행 중인 숫자가 일치하면 Amicable Number로 인식한다.단, 1에서 구해진 약수의 합과 진행 중인 숫자가 같은 경우는 제외한다.

[소스 코드]

"""
# 19_Amicable_Numbers.py
# Date: 2014. 07. 31
# Author: coozplz@gmail.com
"""
num = 10000
sumOfAmicable = 0

while(num > 0) :
    sumOfDivisor = 0
    for i in range(1, num):
        if(num % i == 0):
            # 약수의 합을 구한다.
            sumOfDivisor = sumOfDivisor + i

    sumOfDivisor2 = 0
    for i in range(1, sumOfDivisor):
        if(sumOfDivisor % i == 0):
            # 약수의 합을 구한다.
            sumOfDivisor2 = sumOfDivisor2 + i


    """
    # 약수의 합과 수가 일치하지만 두수가 동일한 경우는 제외한다.
    # 예) 28 // 28
    #      6 // 6
    """
    if(sumOfDivisor2 == num and num != sumOfDivisor) :
        print("AmicableNumber=", num, sumOfDivisor)
        sumOfAmicable = sumOfAmicable + num
    num = num - 1
print(sumOfAmicable)
기본

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중