Project Euler Retreat

Question

Now I am doing Project Euler number 1:

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.

This is my code, which runs in 0 milliseconds:

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int sumNums = 0;

    for(int i = 0; i < 1000; i++)
    {
        if (i % 3 == 0 || i % 5 == 0) { sumNums += i; }
    }

    s.Stop();

    Console.WriteLine(sumNums);
    Console.WriteLine(s.ElapsedMilliseconds);
}

I also have this version, which also runs in 0 milliseconds. In fact, running both methods in the same timer together results in 0 milliseconds:

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int sumNums = 0;

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

    for (int i = 0; i < 1000; i += 5)
    {
        sumNums += i % 3 == 0 ? 0 : i;
    }

    s.Stop();

    Console.WriteLine(sumNums);
    Console.WriteLine(s.ElapsedMilliseconds);
}

What could be improved, and which version is better?

Answer 1

I don't have a C# compiler, but I think the 2nd version will be faster if you drop the i % 3 in the 2nd loop, let it sum all the multiple of 5, and then make another pass to remove the multiples of 15. And since the summing of 3, 5, 15 are repetitive, I'd introduce a helper function, like this:

static int sumOfMultiples(int x, int limit)
{
    int sum = 0;
    for (int i = x; i < limit; i += x)
    {
        sum += i;
    }
    return sum;
}

Then in Main, you could write:

int max = 1000;
int sumNums = sumOfMultiples(3, max) + sumOfMultiples(5, max) - sumOfMultiples(15, max);

But of course, the suggestion of @VikasGupta in comments is the best, to use pure math instead of looping, rewriting the helper as:

static int sumOfMultiples(int x, int limit)
{
    int n = (limit - 1) / x;
    return x * n * (n + 1) / 2;
}

Answer 2

Since I don't have a C# compiler (sorry), so I converted both programs into Java in order to test.

First Code:

Average speed: 80000- 90000 nanoseconds

Review:

for(int i = 0; i < 1000; i++)
{
    if (i % 3 == 0 || i % 5 == 0) { sumNums += i; }
}

You can start on 3 safely without affecting the outcome:

for(int i = 3; i < 1000; i++)
{
    if (i % 3 == 0 || i % 5 == 0) { sumNums += i; }
}

Also, you should space out your if statement into three lines, for better readability:

for(int i = 3; i < 1000; i++)
{
    if (i % 3 == 0 || i % 5 == 0) {
        sumNums += i;
    }
}

That's probably it for this one.

Second Code:

Average speed: 60000 - 65000 nanoseconds

Review:

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

for (int i = 0; i < 1000; i += 5)
{
    sumNums += i % 3 == 0 ? 0 : i;
}

Same as previous, you can start from a slightly larger number:

for (int i = 3; i < 1000; i += 3)
{
    sumNums += i;
}

for (int i = 5; i < 1000; i += 5)
{
    sumNums += i % 3 == 0 ? 0 : i;
}

Thoughts

I think they are both equal at 1000, but as the numbers get larger, the first one will slow down significantly.