[C/C++] Project Euler #1 Add 3 or 5 multipliers.

From the University of challenges, one comes from a lot of problems that create a multi-add programs to 100. Most results are still seeking answers using the for loop. (The problem, of course, questions shall intention is to see if you can well use a for loop to assume Maybe.)

But that, from 1 to n, if you know the most basic formula for the sum up, do not turn the bother for loop, can be calculated.

If you run this using for loop, \(O(n)\) time is elapsed. However, by using the sum formula of the arithmetic progression, can be calculated as a constant time. In fact, if the range of 1000 to be more a matter of degree, like Project Euler, program execution time is not enough challenge anyone noticed.

 

sum of multiplications

Function to obtain the sum of m drainage million in the corresponding number range is as follows:

/// @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;
}

 

With this function, the projector Euler first problem adding to the sum of a multiple of 5 from the sum of a multiple of 3, except the sum of the multiple of 15, the sum of a multiple of 3 or 5 can be obtained.

 

\[ S_{3,5}(n) = \sum_{k=1}^{n/3} 3k + \sum_{k=1}^{n/5} 5k - \sum_{k=1}^{n/15} 15k \]