[Programmers] [077884] [Python] 약수의 개수와 덧셈

문제

• 플랫폼 : 프로그래머스
• 번호 : 077884
• 제목 : 약수의 개수와 덧셈
• 난이도 : Level 1
• left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return
• 문제 : 링크

---

필요 지식

• 수학

---

풀이

파이썬으로 풀었다.

풀이1 : 순수하게 약수 전부 카운팅

def solution(left, right):
    counts = [0, 1, *([2]*(right-1))]

    for i in range(2, right + 1):
        for j in range(2 * i, right + 1, i):
            counts[j] += 1

    return sum(i if counts[i] % 2 == 0 else -i
               for i in range(left, right + 1))

• 1,2, ... right까지 모든 수의 약수들을 카운팅한다.
• left부터 right까지 반복하여 각각의 값마다 약수의 갯수가 짝수이면 해당 값을 더하고, 홀수이면 해당 값을 뺀다.

풀이2 : 제곱수의 약수는 홀수개이다!!!

from math import sqrt


def solution(left, right):
    return sum(i if sqrt(i) % 1 else -i
               for i in range(left, right + 1))

• 어떤 수가 제곱수(스스로의 거듭제곱근이 정수인 수)이면 해당 수의 약수의 갯수는 무조건 홀수다.
  • 제곱수 여부를 sqrt(i)%1로 판단했다. 이 값이 0이면 제곱수라는 뜻이고, 0이 아니면 제곱수가 아니다.
  • 0이 아니라 함은 Truthy하므로, 참으로 평가됨을 의미된다.
  • 즉 제곱수가 아니면 참으로 평가해서, 해당 수를 그냥 더하고, 제곱수이면 거짓으로 평가해서 해당 수를 빼게 된다.
• 이 성질을 이용하면 left부터 right까지만 순회하면 된다.

---