Programmers. 약수의 개수와 덧셈

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 약수의 개수와 덧셈

문제 풀이

매우 기초적인 문제였는데 괜히 어렵게 생각해버렸다. 소인수분해한 뒤 그 빈도에 +1씩 더해 곱하면 전체 약수의 개수가 되긴 하는데 그럴 필요 없이 제곱근을 기준으로 양쪽이 대칭이라는 점을 참고해야 한다. 1부터 제곱근까지 나누되 나눈 값과 몫이 같다면 제곱근으로 + 1, 그렇지 않다면 2를 더하고 그 값이 짝수면 더하고 홀수면 빼면 된다.

python 코드

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