약수의 합

N이라는 숫자의 약수들의 합을 구할 때, 단순히 1부터 N까지 반복문을 돌려서 모든 숫자에 대해 확인하는 방법이 있다. 

이보다 더 효율이 좋은 방법으로는 N의 제곱근을 이용하는 방법이다. 

에라토스테네스의 체 문제에서와 같이 특정 N의 제곱근을 기준으로 양쪽의 약수들은 짝을 이루어 곱하면 N이 된다. 

그렇기 때문에 N의 제곱근 까지만 약수들을 구하면서 자동으로 짝을 이루는 약수들도 구할 수 있다. 

def sol(N):
	answer  = 0
    m = int(N ** 0.5) #1
    for i in range(1, m+1): #2
    	if N % i == 0: #3
        	ansewr += i #4
       		if i != N // i: #5
            	answer += N // i #6

1. N의 제곱근을 m이라고 한다. 

2. 1부터 m까지의 숫자들을 반복문에서 다룬다.

3. 만약 N이 i로 나누어 떨어진다면 I는 약수이기 때문에 

4. answer에 i를 더한다.

5. 만약 i가 n을 i로 나눈 몫과 같지 않다면( i 와 n // i 은 서로 짝을 이룬다는 뜻이다.)

6. n // i도 answer에 더한다. 

 

만약 N이 36이라면 i가 36의 제곱근인 6일 때, 6은 짝을 이루는 숫자가 자기 자신이므로 5번째 라인에서 걸러지면서, 중복으로 더하지 않게 된다.