[programmers] 약수의 개수와 덧셈

약수의 개수와 덧셈

월간 코드 챌린지 시즌 2

level 1

 

python 3

우선 특정 수의 약수 개수를 판단하는 기본적인 방법은 다음과 같다.

def dividorNumIsEven(n):
    dividorList = []
    
    for i in range(1, n + 1):
        if (n % i) == 0:
            dividorList.append(i)
    
    return True if len(dividorList) % 2 == 0 else False

그런데 이런 방식을 left 부터 right 까지 모두 <한다면 시간초과 나겟죠..?

import math


def getSquareNumSum(n):
    return (n * (n + 1) * (2 * n + 1)) / 6


def getRangedSquareNumSum(minNum, maxNum):
    minSquareNumSum = getSquareNumSum(minNum)
    maxSquareNumSum = getSquareNumSum(maxNum)
    return maxSquareNumSum - minSquareNumSum


def solution(left, right):
    totalSum = 0
    squareNumList = []

    for n in range(left, right + 1):
        totalSum += n

        if math.sqrt(n).is_integer():
            squareNumList.append(n)

    minNum = math.sqrt(squareNumList[0]) - 1
    maxNum = math.sqrt(squareNumList[-1])
    squareNumSum = getRangedSquareNumSum(minNum, maxNum)

    return totalSum - (2 * squareNumSum)

저도 몰랐는데, 약수의 개수가 홀수인 수는 제곱수라고 하네요.

따라서 left ~ right 사이의 제곱수들의 합은 약수의 개수가 홀수인 수의 합과 동일하다는 뜻이죠.

문제에서는 약수의 개수가 짝수인 수는 더하고, 홀수인 수는 빼야 하니, 총 합(totalSum)에서 2번(2 * squareNumSum) 빼주면 됩니다.

제곱수의 합의 공식은 다음과 같습니다.

```1^{2} + 2^{2} + ... + x^{2} = \frac(x(x + 1)(2x + 1))(6)```

그런데 위에서 구한 squareNumList에는 제곱수들이 들어 있으니, 다시 루트를 해서 공식에 넣어야 되는 것 조심하세요.

 

참고

[월간 코드 챌린지 시즌 2] 5월 문제 해설