Add all the natural numbers below one thousand that are multiples of 3 or 5.
On the walk home, I found myself thinking about the problem and I wondered if it would be possible to use C++ template meta-programming to obtain the solution at compile time. Here's what I came up with:
template< int n >
struct sum_integers_up_to
{
static const int result =
(n * (n + 1)) / 2;
};
template< int upper_limit, int x >
struct sum_multiples
{
static const int result =
x * sum_integers_up_to< (upper_limit - 1)/ x >::result;
};
template< int upper_limit, int x, int y >
struct sum_two_multiples
{
static const int sum_of_multiples_of_x =
sum_multiples< upper_limit, x >::result;
static const int sum_of_multiples_of_y =
sum_multiples< upper_limit, y >::result;
static const int sum_of_multiples_of_xy =
sum_multiples< upper_limit, x*y >::result;
static const int result =
sum_of_multiples_of_x + sum_of_multiples_of_y - sum_of_multiples_of_xy;
};
int main()
{
return sum_two_multiples< 1000, 3, 5 >::result;
}
Having a look at the assembly code generated by MSVC, we see that it's about as minimal as it gets (spoiler alert!):
_main PROC
mov eax, 233168
ret 0
_main ENDP
One down, 328 to go...