Bsrhrki

I'm learning C++ and currently doing Project Euler challenges. The first challenge is the following.

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.

I did a quite simple and stupid brute-force implementation by just looping from 1 to 999, checking if its divisible by either 3 or 5 and if it is, sum it with the result variable.

Is there any faster/better/cleaner implementation, maybe without a loop or with less division?

#include <iostream>

int main(int argc, char *argv[])

 int result(0);
 for (int i = 1; i < 1000; ++i) 
 if (!(i % 3 && i % 5)) 
 result += i;
 
 
 std::cout << "Result: " << result << "n";
 return 0;

The code is basically fine.

The if condition is perhaps a little complicated though. To interpret it you have to read "if not ((i is not a multiple of 3) and (i is not a multiple of 5))", which is a double negative.

Given the problem statement, we'd expect something more like "if (i is a multiple of 3) or (i is a multiple of 5)", so:

if ((i % 3 == 0) || (i % 5 == 0))

Nitpicking:

• If we don't need argc and argv, we can declare main as int main() with no arguments.


• The return 0; at the end of main happens automatically in C++, so we don't have to write it ourselves.

Note that there exists an arithmetic solution to the problem, which is much faster (it could even be done at compile-time in C++).

We want to sum all the multiples of 3 or 5 less than 1000. We can think about the sequence of multiples of 3 as (3, 6, 9, 12, 15, ..., 999), which is the same as 3 * (1, 2, 3, 4, 5, ..., 333). [...]

Such a sequence, where the difference between each number is constant, is called a finite arithmetic progression [and the sum is] a finite arithmetic series. The formula for the sum is 1/2 * n * (a_1 + a_n). where n is the number of terms being added, a_1 is the first element in the sequence, and a_n is the last element in the sequence.

Yes, there are ways to do this that avoid most of the divisions, and are probably faster as well.

Let's start with a simplified version of the problem: add up all the multiples of 3.

Now, you could do a simplified version of what you've written:

int sum = 0;

for (int i=1; i<1000; i++)
 if (i % 3 == 0)
 sum += i;

...but we know up front that 1 and 2 aren't multiples of three. We can generate all multiples of three by counting by 3's:

int sum = 0;

for (int i=0; i<1000; i += 3)
 sum += i;

Obviously enough, we can do the same thing for multiples of 5:

int sum = 0;

for (int i=0; i<1000; i += 5)
 sum += i;

But if we do both in succession:

int sum = 0;

for (int i=0; i<1000; i += 3)
 sum += i;

for (int i=0; i<1000; i += 5)
 sum += i;

...we'll get the wrong answer. The problem now is that if a number is a multiple of both 3 and 5 (e.g., 15) we've counted it twice. There are a few ways we can avoid that. One is to have the second loop add i to the sum if and only if i is not a multiple of 3.

for (int i=0; i< 1000; i += 5)
 if (i % 3 != 0)
 sum += i;

Another is to initially add those, but then add a third loop that generates only the numbers that are multiples of both 3 and 5, and subtracts those from the overall result:

int product = 3 * 5;

for (int i = 0; i < 1000; i += product)
 sum -= i;

Since you're (apparently) more interested in learning programming than in learning math, I'll only sketch out the next step. There are ways to avoid doing those loops at all though. What we're really doing is (for two different values of N) summing a series of 1N + 2N + 3N + 4N + ...

Using the distributive property, we can turn that into N * (1 + 2 + 3 + 4 + ...). Gauss invented an easy way to sum a series like 1 + 2 + 3 + 4 + ..., so what we need to do is compute the number of terms of that series we need for each of 3 and 5, compute them, multiply by 3 and 5 respectively, and add together the results. Then do the same for multiples of 15, and subtract that from the result. The number of terms in each series we need will be the upper limit divided by the N for that series--so for multiples of 3, we have 1000/3 terms, and for multiples of 5 we have 1000/5 terms.

So, we can compute the final value as:

3 * gauss_sum(1000/3) + 5 * gauss_sum(1000/5) - 15 * gauss_sum(1000/15)

...and we're left with no loops at all, so we can compute the correct value for any upper limit (up to what fits in an unsigned long long, anyway) in constant time.

The one bit that is absolutely not fine is this line:

if (!(i % 3 && i % 5))

It is clever, and clever is bad. The question was about "all integers that are multiples of 3 or 5." So write that:

if (i % 3 == 0 || i % 5 == 0)

As you were asking for "less division"... Here's a different approach with absolutely no division, multiplication or modulo operations. We have two counters t (for increment three) and f (for increment five), and update them in a single while loop. Due to the increments it's guaranteed t and f will always be numbers divisible by 3 resp. 5. Now we just have to pick which counter to update (the lower one), and to handle the case when both counters occasionally meet :)

(You can avoid the std::min-line and put the addition to result into the if/else if/else-part, but with this it's easier to understand what happens.)

#include <iostream>

int main() 
 unsigned t=0, f=0;
 unsigned result=0;
 while (t<1000) 
 result+=std::min(t, f);

 if (t<f) t+=3;
 else if (f<t) f+=5;
 else // f==t
 t+=3;
 f+=5;
 
 
 std::cout << "Result: " << result << std::endl;
 return(0);