3
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ The first takes 6 milliseconds at 1,000,000, and the second takes 2. \$\endgroup\$
    – user34073
    Jan 28, 2015 at 0:23
  • 3
    \$\begingroup\$ Another version - First and foremost another version is possible (no loops necessary).. where you can identify the fact that 3 + 6 + 9 + .... 999 = 3 * (1 + 2 + 3 + .... 333) and similarly, answer to your problem is 3 * Math.Floor(n / 3) * (Math.Floor(n / 3) + 1) / 2 + 5 * Math.Floor(n / 5) * (Math.Floor(n / 5) + 1) / 2 - 15 * Math.Floor(n / 15) * (Math.Floor(n / 15) + 1) / 2 Note - This assumes that if you want sum below 1000, then you use 999 as n above \$\endgroup\$ Jan 28, 2015 at 0:29
  • \$\begingroup\$ Put another way, if F(a, n) = a * Math.Floor(n / a) * (Math.Floor(n / a) + 1) / 2, then the answer is F(3, 999) + F(5, 999) - F(15, 999) \$\endgroup\$ Jan 28, 2015 at 0:51

2 Answers 2

3
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.