프로젝트 오일러 #1 3 또는 5의 배수의 합

대학 과제에서 보면, 1부터 100까지 다 더하는 프로그램을 만드세요라는 문제가 많이 나옵니다.  대부분 결과는 for 루프를 이용해서 답을 구하고 있습니다.  (물론 문제 출제 의도는 for 루프를 잘 쓸 수 있는지를 보는 것이니 당연하다고 할 수도 있겠죠.)

 

그렇다고 해서, 1부터 n까지 합을 구하는 가장 기본적인 공식을 알고 있다면, 굳이 for 루프를 돌리지 않아도, 계산을 할 수 있습니다.

 

for 루프를 돌린다면, \(O(n)\)만큼의 시간이 기본적으로 듭니다.  그렇지만, 등차수열의 합 공식을 이용하면, 상수 시간으로 계산을 할 수 있습니다.  사실 더해야 하는 범위가 오일러 프로젝트의 문제처럼 1,000정도라면, 프로그램 실행시간은 사람이 눈치챌 수 없을 정도입니다.

 

해당 숫자 범위 안에서 m배수만의 합을 구하는 함수는 아래와 같습니다.

 

//----------------------------------------------------------------------------------------
//  Project Euler #1 - Multiples of 3 and 5
//    - by Aubrey Choi
//    - created at 2014-12-22
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <time.h>

///  @brief  sum of m-multiple numbers from s to e. 
///  @param  s                  [IN] start number
///  @param  e                  [IN] end number
///  @param  m                  [IN] multiply number
///  @return  Return sum.
int sum(int s, int e, int m)
{
  int s1 = (s-1)/m;
  int e1 = e/m;

  return m*(e1-s1)*(e1+s1+1)/2;
}

void solve1()
{
  printf("Ans = %d\n", sum(1, 999, 3)+sum(1, 999, 5)-sum(1, 999, 15));
}

int main()
{
  clock_t t;

  t = clock();
  solve1();
  printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

이 함수를 이용하면, 오일러 프로젝터 첫번째 문제는, 3의 배수의 합에서 5의 배수의 합을 더하고, 15의 배수의 합을 빼면, 3 또는 5의 배수의 합을 구할 수 있습니다.

 

sum(1, 999, 3) + sum(1, 999, 5) - sum(1, 999, 15)

 

수학적으로는 다음과 같습니다.

\[ \sum_{ k|3 ~or~ k|5}^{n} = \sum_{k|3}^{n} k + \sum_{k|5}^{n} k - \sum_{k|15}^n k \]