[프로젝트 오일러] 문제1 - 3과 5의 배수

문제

영문

Multiples of 3 or 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

바로가기

 

한글

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

바로가기

 

해설

수학적 해결법

중고등학교 때 많이 보았던 문제 유형입니다! 우선 1000 미만의 3의 배수와 5의 배수에 대해 생각해봅시다.

• 3의 배수 : 3 6 9 12 15 18 21 27 30 ... 990 993 996 999
• 5의 배수 : 5 10 15 20 25 30 ... 985 990 995

다음과 같이 나열해보면, 두 목록에서 3과 5의 최소공배수인 15의 배수들이 겹쳐서 들어가있음을 확인하실 수 있습니다. 만약 3의 배수 전체와 5의 배수 전체를 그냥 더해준다면, 15의 배수는 두 번 중복이 되어 들어가겠지요. 따라서 중복된 15의 배수들은 한 번 빼줘야 합니다. (포함 배제의 원리) 따라서 우리가 구할 답은 다음과 같습니다.

 

(3의 배수의 합) + (5의 배수의 합) - (15의 배수의 합)

 

배수들의 합은 등차수열의 합 또는 가우스의 덧셈법을 이용해줍시다. 저는 그냥 각 배수로 묶어준 다음, 안 쪽의 자연수 합을 가우스 방식[n(n+1)/2]로 계산해줄게요. 어떤 방법으로 하셔도 상관 없습니다!

• 3의 배수 합 : 3*(1+2+...+333) = 3*333*334/2 = 166833
• 5의 배수 합 : 5*(1+2+...+199) = 5*199*200/2 = 99500
• 15의 배수 합 : 15*(1+2+...+66) = 15*66*67/2 = 33165

따라서 답은 166833+99500-33165 = 233168이 됩니다!

 

정답

233168