[프로그래머스] 약수의 갯수와 덧셈

문제 링크

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

문제 설명

• 에라토스테네스테네스의 체를 응용하는 문제
• left와 right는 1000까지 주어질 수 있기 때문에 1000까지의 숫자들의 약수의 갯수들을 각각 구한다.
• i * j 로 만들어 지는 숫자는 i와 j를 약수로 가진다고 할 수 있다. i 가 1일때의 상황을 보면 j는 1 ~ 1000 까지 돌면서 nums 배열에 1에서 1000번째 값에 1씩을 추가한다. 즉 1000이하 i를 약수로 가지는 모든 숫자들에 1을 더해줌으로써 약수의 숫자를 가지고 있는 배열을 만든다.
• left ~ right 까지 for문을 돌면서 nums 배열의 인덱스가 가지고 있는 약수의 갯수가 짝수면 더해주고 홀수면 빼주는 계산을 한다.

def solution(left, right):
    nums = [0] * 1001
    answer = 0
    
    for i in range(1, 1001):
        for j in range(1, 1000 // i + 1):
            nums[i * j] = nums[i * j] + 1
    
    for i in range(left, right + 1):
        if nums[i] % 2 == 0:
            answer = answer + i
        else:
            answer = answer - i
            
    return answer