[프로그래머스 : PYTHON] 약수의 합

문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항

• n은 0 이상 3000이하인 정수입니다.

입출력 예

n	return
12	28
5	6

입출력 예 설명

입출력 예 #1
12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.

입출력 예 #2
5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

 

문제풀이

에라토스테네스의 체를 이용하여 약수를 구할 때 n의 제곱근만큼의 범위까지 약수를 구한다.

예를 들어 설명하자면 16의 약수가 1, 2, 4, ,8 16인 것을 보면 가운데 4는 16의 제곱근이다. 그러므로 제곱급 범위 내에서 약수를 다 찾을 수 있다.

n의 제곱근 범위만큼 돌면서 n으로 나눈 나머지가 0일 때 해당 숫자(i)와 i로 나눈 몫을 answer에 더해준다. 두 약수를 한번에 구해준 것이다. 단, 제곱근이 정수일 경우엔 해당 숫자만을 더해준다.

 

전체코드

import math
def solution(n): 
    if n == 0:
        return 0
    
    answer = 0
    
    for i in range(1, int(math.sqrt(n))+1):
    	# 약수일 때
        if n % i == 0:
        	# i가 정수 제곱근일 때
            if i == int(math.sqrt(n)) and math.sqrt(n) == int(math.sqrt(n)):
                answer += int(math.sqrt(n))
                continue
            # i가 정수 제곱근을 아니나 약수 1개를 가질 때
            answer += i + (n // i)
        
    return answer