# Add multiples of 3 or 5 below 1000, Can this code be optimised. Project Euler #1

I have seen some solution here for the same problem, this and this I have found better ways to solve this problem. I just want to know how good or bad my code and way of approaching this problem is.

using System;

public class Program
{
public static void Main()
{
int sum = 0;
for (int i = 0; 3 * i < 1000; i++)
{
sum += 3 * i;

if (5 * i < 1000 && (5 * i) % 3 != 0)
{
sum += 5 * i;
}
}
Console.WriteLine(sum );
}

• Console.WriteLine(sum + ""); looks weird, why don't you just Console.WriteLine(sum);? – nalka Oct 15 at 7:44
• Please do not edit the code in the question, unless it was a copy-error from the actual code you have. Removing mistakes as they are pointed out, makes the answers no longer relevant for future readers - there's nothing shameful about posting "bad" code in code-review; it's what it's here for :) – Bilkokuya Oct 15 at 10:13
• There is nothing wrong with this solution but it is not really what project euler is searching for. @AlanT provided a good reference solution to this problem. – BevynQ Oct 15 at 20:57
• When you ask about optimizations problems, please get in the habit of saying what you want to be optimized. The optimal program in terms of speed is class P { static void Main() { System.Console.WriteLine("233168"); } } but I think that would not be satisfying to you! What exactly do you wish to be "optimal"? – Eric Lippert Oct 15 at 22:40
• I'm not sure exactly what the goal is here, because even if we allow the upper bound to vary this can be computed in constant time, unless I'm missing something. – Matt Samuel Oct 16 at 0:13

I'm afraid that the solution given is not better than the referenced C one (although the C solution could be generalized and made a bit easier to understand)

Why?

The code under review has a outer loop that is executed 333 times (with a multiplication in each condition check). We can remove the multiplication to do the job a bit more cheaply

for (int i = 1; i <= 333; i++)


But, even with the restructured loop we still do

this, sum += 3 * i;, 333 times and then
this, 5 * i < 1000 && (5 * i) % 3 != 0, 333 times

As opposed to

S1= a*(b+c)/2;, once
s2= k*(i+j)/2;, once
s3= n*(m+o)/2;, once
S= S1 + s2 - s3;, once

It is a bit of a cheat in the C solution that the various magic numbers are hardcoded; but even allowing for a function to calculate the values

var sum3 = SumDivisibleBy(999,3);
var sum5 = SumDivisibleBy(999,5);
var sum15 = SumDivisibleBy(999,15);
var sum35 = sum3 + sum5 - sum15;

private static int SumDivisibleBy(int range, int divisor)
{
var top = range/divisor;
var ret = divisor*top*(top+1)/2;
return ret;
}


is a lot cheaper than brute-forcing the solution.

In the original solution, for numbers under 1000, we need to loop 333 times, for numbers under 10000, we need to loop 3333 times,... It doesn't scale well. For the other solution, there are the same number of operations each time.

• Multiplication by a constant 3 is cheaper than multiplication by a runtime variable. With only 2 set bits, and being 1 + a small power of 2, compilers can do this on x86 with a single instruction with 1 cycle latency, e.g. lea eax, [rcx + rcx*2]. Or a smart compiler might just optimize the 3 *i < 1000 into i <= 333, because it can prove that's exactly equivalent for the possible range of i values (making the multiply not overflow). It doesn't hurt to do this optimization by hand in the source, though. And +1 for applying Gauss's closed-form sum formula in a nicely readable way. – Peter Cordes Oct 15 at 18:11
• @PeterCordes: As far as I'm aware, neither project Euler nor OP are specifying that they are squeezing for performance to that degree. Using a variable renders the code reusable for any divisors, not just 3 and 5. I'm not saying your performance argument is wrong, but it doesn't necessarily outweigh the benefits of a reusable approach. – Flater Oct 16 at 9:29

## The main problem

The main issue here is that you define i in function of it being a "factor of 3", and then also try to use this number as a "factor of 5". This doesn't make any sense - as there is no inherent relationship between being a threefold and a fivefold number.

It would've made sense if you were doing it for 3 and 6, for example, because 3 and 6 are related:

//i*3 is obviously always a multiple of 3
sum += 3 * i;

if ((3*i) % 2 == 0)
{
//Now we know that i*3 is also a multiple of 6
}


But that is not the case here.

## The for loop's readability

I understand your idea, you wanted to only iterate over factors of three which keep the multiple under 1000. While I will suggest to change this approach (later in the answer), your approach could've been written in a much more readable manner:

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


This will iterate over i values of 0,3,6,9,12,15,... and will skip all values inbetween.

The benefit here is that you don't need to work with i*3 all the time, you can just use i itself.

You will need to iterate over the multiple of 5 separately. However, should you keep using this approach, I would always suggest splitting these loops anyway.

## The algorithm

Your approach works, but it's not the easiest approach. If I put your approach into words:

Add every multiple of 3 to the sum.

Also add the multiple of 5, but only if it's still below 1000, and it's not already divisble by 3.

The issue here is in how you handle the multiples of five. You're working with an i that is defined as the allowed values for threefolds. For any i > 200, you're effectively having to manually exclude this value. You're using a different approach for the 5 than you are using for the 3, even though the logic is exactly the same. That's not a reusable approach.

Secondly, there is a readability problem. Your code should be trivially readable, and I simply wasn't able to understand your intention. I had to google what the question was before I could understand what your code was trying to achieve.

So let me offer a better approach, first putting it into words:

• Check every number from 0 to 1000 (not including 1000)
• If it is divisible by 3 or it is divisible by 5, then add it to the sum.

This can be put into code, step by step:

// Check every number from 0 to 1000 (not including 1000)
for(int i = 0; i < 1000; i++)
{
var isDivisibleBy3 = i % 3 == 0;
var isDivisibleBy5 = i % 5 == 0;

//If it is divisible by 3 or it is divisible by 5
if(isDivisibleBy3 || isDivisibleBy5)
{
//then add it to the sum
sum += i;
}
}


Note how the code exactly mirrors my algorithm description.

You don't need to use the booleans. I simply added them to simplify the example. if(i % 3 == 0 || i % 5 == 0) would be equally okay to use because it's still reasonably readable.

If the calculations become more complex, I suggest always using the booleans so you neatly break your algorithm down to small and manageable steps. It will do wonders for your code readability, and it does not impact performance (the compiler will optimize this in a release build).

## A LINQ variation

This can be further shortened using LINQ:

var sum = Enumerable.Range(0,1000)
.Where(i => i % 3 == 0 || i % 5 == 0)
.Sum();


LINQ is just a nicer syntaxt, but it uses a for/foreach iteration in the background, so I suspect it won't be much more performant than the previous example. But I do consider this highly readable.

## Maximizing performance

The previous suggestion maximizes readability, but it does so at the cost of performance, as it now has to loop over 1000 values and evaluate them all. You already linked several other answer that clearly dive deeper into the code in order to maximize the performance, I hope you can see that this dramatically impacts the readability.

public void Solve(){
result = SumDivisbleBy(3,999)+SumDivisbleBy(5,999)-SumDivisbleBy(15,999);
}

private int SumDivisbleBy(int n, int p){
return n*(p/n)*((p/n)+1)/2;
}


By itself, I would have no idea what this code does. I can sort of understand the intention of Solve(), but it's not quite apparent how SumDivisbleBy() works.

SumDivisbleBy() has effectively become impossible to maintain. If you needed to introduce a change, you would effectively have to reverse engineer it before you can alter it. This means that starting from scratch is the better option, which is clearly not a good thing.

However, when performance is the main focus, this is acceptable. I would, however, strongly urge you to document the algorithm in comments specifically to help future readers in understanding how/why this works.

Note that AlanT's answer contains a more readable variant of the SumDivisbleBy() method, which already helps a lot with understanding the algorithm. The clear naming used clarifies what the algorithm does, which is the main goal of writing readable code (explaining why something works is only a secondary goal and not always required).

• How about using two counters, one with i+=3 and the other one with j+=5? Wouldn't it be even more efficient without the %? – t3chb0t Oct 15 at 8:41
• @t3chb0t: Sure but then you have to iterate twice. I haven't crunched the numbers on it but it seems to be a "pick your poison" type deal. Either iterate twice, or iterate once and validate the numbers. Besides, if you're going for performance, you're waaaay better off with the SumDivisbleBy example I linked, as this only requires one computation per divisor (3 computations) in total) and no iteration at all. – Flater Oct 15 at 8:46
• @t3chb0t: A propos, if you use the i+=3 approach, you will always have to have a second i+=5 loop. OP's code relies on the "factors of three" (from 0 to 333) inherently including all "factors of five" (from 0 to 200). Using the i +=3 approach, i is no longer a list of "factors of three" but rather "multiples of three", which no longer inherently include all "multiples of five"; thus requiring you to iterate those separately. – Flater Oct 15 at 8:50
• Not exactly... I was thinking about a single for loop with two variables... – t3chb0t Oct 15 at 8:53
• @t3chb0t: I don't see how that would work unless you then use a combined condition, i.e. for(int i = 0, j=0; i < 1000 || j < 1000 ; i+=3,j+=5). While technically possible, I don't see the benefit of doing so. It dramatically lowers readability, and the # of operations is pretty much exactly the same regardless of merging the for loops or keeping them separate. If anything, you're going to end up incrementing j 333 times (because i will be incremented 333 times) while you only need to increment it 200 times, but since the for is still working with i, it also keeps incrementing j. – Flater Oct 15 at 9:00

Thanks @Henrik Hansen it helped. This is optimised code below according to the WIKI. But here is the tradeoff, this has to loop 1000 times. where above solution need to run at most 333 times.

 using System;

public class Program
{
public static void Main()
{
int sum = 0;
for (int i = 0; i < 1000; i++)
{
if ( i % 3 == 0 || i % 5 == 0)
{
sum += i;
}
}
Console.WriteLine(sum );
}
}

• Yes, but you should read a bit further -:) – Henrik Hansen Oct 15 at 8:08