HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Project Euler Retreat

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
projectretreateuler

Problem

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

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

What could be improved, and which version is better?

Solution

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;
}

Code Snippets

static int sumOfMultiples(int x, int limit)
{
    int sum = 0;
    for (int i = x; i < limit; i += x)
    {
        sum += i;
    }
    return sum;
}
int max = 1000;
int sumNums = sumOfMultiples(3, max) + sumOfMultiples(5, max) - sumOfMultiples(15, max);
static int sumOfMultiples(int x, int limit)
{
    int n = (limit - 1) / x;
    return x * n * (n + 1) / 2;
}

Context

StackExchange Code Review Q#78825, answer score: 3

Revisions (0)

No revisions yet.