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\$
  • \$\begingroup\$ The first takes 6 milliseconds at 1,000,000, and the second takes 2. \$\endgroup\$ – 23fc9a62-56de-47fb-97b4-737890 Jan 28 '15 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\$ – Vikas Gupta Jan 28 '15 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\$ – Vikas Gupta Jan 28 '15 at 0:51
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.