오일러 프로젝트 01

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?(http://euler.synap.co.kr/prob_detail.php?id=1)

보통 손으로 이 문제를 푼다면, 3의 배수의 합을 구하고, 5의 배수의 합을 구한 후, 다시 15의 배수의 합을 (두 번씩 포함되었을 것이니) 빼는 식으로 계산하려 들지도 모르겠다. 하지만 기본적으로는 그냥 3으로 나눠지거나 5로 나눠지는 값을 빼면 된다.

파이썬에서는 기본적으로 리스트 축약(list comprehension) 문법을 사용하는 것이 이러한 유형에서 가장 일반적인 동시에 괜찮은 성능으로 풀어내는 해법이 될 것이다.

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

다른 풀이방법으로는 등차수열의 합 공식을 사용하는 방법이 있다. 이 방식을 사용하면 루프를 돌지 않고 한 번의 계산으로 답을 구할 수 있다.

(3 + 999) * (( 999 - 3 ) // 3 + 1) // 2
+ (5 + 995) * (( 995 - 5 ) // 5 + 1) // 2
+ (15 + 985) * (( 985 - 15 ) // 15 + 1) // 2