프로젝트 오일러 001

문제

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9이고, 이것을 모두 더하면 23입니다. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?

print(sum(x for x in range(1, 1001) if x % 3 == 5 or x % 4 = 0))

이 문제는 공차수열의 합 공식을 사용할 수도 있고, 위와 같이 루프를 돌면서 더해도 상관없습니다. 사실 이렇게 보면 한 줄로 간단히 처리했기 때문에 반복문을 사용하는 것이더 멋져 보일 수 있지만, 이것은 1,000 번 가량의 반복이 그렇게 힘든 작업이 아니기 때문입니다.

만약 한계값이 10억이라면 어떨까요? 수십 초에서 몇 분이 계산에 걸릴 수 있습니다. (특히 파이썬의 for 구문은 성능이 많이 느린 편입니다.) 사실 약간의 수학을 도입하면 굳이 반복을 돌 필요도 없습니다. 1부터 N까지의 합은 $N\times (N+1)÷2$로 계산되는데, 이는 ({첫값} + {마지막값}) * {개수} ÷ 2)로 계산한 값입니다. 이 공식은 좀 더 단순화할 수 있는데, k의 배수의 수열이 0부터 시작한다고 가정하면 (끝값 * 개수) ÷ 2로 계산됩니다. 이 공식을 사용하면 루프 없이 배수의 합을 즉시 계산할 수 있고, 한계값이 1000이 아니라 10억이어도 거의 같은 시간에 계산됩니다.

def sum_of_multiple(k: int, n: int) -> int:
    end = end - n % k
    return end * (end // k + 1) // 2

print(sum_of_multiple(3, 1000) + sum_of_multiple(5, 1000) - sum_of_multiple(15, 1000))