[Programmers] 약수의 개수와 덧셈

https://programmers.co.kr/learn/courses/30/lessons/77884

코딩테스트 연습 - 약수의 개수와 덧셈

다른 방법이 생각나지 않아서 left에서 right까지 약수의 개수를 직접 구했는데

수학적으로 접근한 풀이가 있어서 기억해두려고 가져왔다.

 

"약수가 홀수개인 모든 수는 제곱수"

 

* 제곱수: 어떤 자연수의 제곱이 되는 수

제곱수가 아닌 수들은 각자 곱해지는 쌍이 있어서 짝수개가 나온다는 댓글이 이해하는 데 참고가 됐다.

내가 이해하기로는 우선 기본적으로 1과 자신이 약수에 포함되는데,

제곱수가 아닌 수들은 여기에 곱해지는 쌍(짝수)이 추가되니 짝수가 된다.

예를 들어 제곱수가 아닌 15 -> 기본적으로 1, 15가 약수에 포함되면서 3 * 5 = 15이므로 (3, 5) 쌍이 약수에 추가되어

약수가 1, 3, 5, 15 이렇게 총 4개(짝수)가 된다.

 

- 다른 분의 풀이

Python

def solution(left, right):
    answer = 0
    for i in range(left,right+1):
        if int(i ** 0.5) == i ** 0.5: # i ** 0.5는 제곱근을 구하는 식
            answer -= i
        else:
            answer += i
    return answer

 

i ** 0.5는 제곱근을 구하는 식인데, 제곱근을 정수로 표현 가능한 수(제곱수)는 약수가 홀수개라고 한다.

그래서 int(i ** 0.5)와 i ** 0.5가 같은지 확인해서 홀수개인지 판단한다.