약수의 개수와 덧셈 (lv1)

 주어진 두 수 사이의 값들이 약수를 홀수개로 갖는지 짝수개로 갖는지 판단하는 문제이다. 따라서 먼저 약수의 개수를 구하고, 그 값이 짝수 인지 홀수 인지 판별하는 식으로 접근했다.

 그러나 수학적으로 다음과 같은 명제가 존재한다.

약수(수학) - 나무위키 (namu.wiki)

약수(수학) - 나무위키

제곱수의 약수의 개수는 홀수이고, 제곱수가 아닌 경우는 짝수이다.

 또한, 다음과 같은 명제도 존재한다.

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다. (tistory.com)

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

 약수를 구하는 알고리즘을 작성할 때, n의 약수 d는 i 번째와 마지막에서 i번째 끼리 값이 같기 때문에, 제곱근까지만 연산하면 된다. 즉, 제곱근에 대해서 약수들은 대칭관계를 갖는다는 점을 유의하자는 것이다.

 

 본 문제를 해결하기 위해 두 명제가 모두 필요한 것은 아니지만, 첫번째 명제를 이용해 간단히 어떤 수가 홀수개의 약수를 갖는지, 짝수개의 약수를 갖는지 알아볼 수 있다.

---

코드

before

def solution(left, right):
    answer = 0
    for d in range(left,right+1):
        if d == 1:
            answer -= 1
            continue

        cnt = 2
        for divisor in range(2,d//2+1):
            if d % divisor == 0:
                cnt += 1
        if cnt % 2 == 0:
            answer += d
        else :
            answer -= d
    return answer

after

def solution(left, right):
    answer = 0
    for i in range(left,right+1):
        if int(i**0.5)==i**0.5:
            answer -= i
        else:
            answer += i
    return answer