user285372
user285372

Reputation:

sum of all the numbers below 1000 that are multiples of 3 or 5

Project Euler problem 1 is: Find the sum of all the multiples of 3 or 5 below 1000

Here is my program, using two simple functions to work out the sum of all the multiples of 3 and all the multiples of 5 and then add them up:

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;


int threeSum( void );

int fiveSum( void );


int main( int argc, char** argv )
{
    cout << "\n The sum of all the natural numbers below 1000 that are multiples of 3 or 5 = \n" << endl;

    cout << threeSum() + fiveSum() << endl << endl;

    system( "PAUSE" );
}


int threeSum( void )
{
    int sumSoFar = 0;

    for ( int i = 1 ; i < 1000 ; i++ )
    {
        if ( i % 3 == 0 )
                            sumSoFar = sumSoFar + i;
    }

    return sumSoFar;
}


int fiveSum( void )
{
    int sumSoFar = 0;

    for ( int i = 1 ; i < 1000 ; i++ )
    {
        if ( i % 5 == 0 )
                            sumSoFar = sumSoFar + i;
    }

    return sumSoFar;
}

which produces 266333 as the answer. Is this correct, or am I doing something wrong, as the website checker says this is the wrong answer!

Upvotes: 0

Views: 8951

Answers (6)

viper
viper

Reputation: 1

This is the best answer and the easiest I could do:

{
int sum ;

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

Upvotes: -1

MartinStettner
MartinStettner

Reputation: 29174

As most others pointed out, you're summing the multiples of 15 twice.

Just a hint for another solution:

The sum of multiples of 3 below 1000 is

SUMBELOW(3,1000) = 3 + 6 + 9 + ... + 999 = 3*(1+2+3+...+333) = 3*333*(1+333)/2 = 3*((1000-1)/3)*(1+(1000-1)/3)/2

(All divisions are integer divisions...)

There are similar formulas for calculating the sums of multiples of 5 and 15. To get the overall result, you have to add the sums for 3 and 5 and subtract the sum for 15...

Upvotes: 1

Karoly Horvath
Karoly Horvath

Reputation: 96346

Another way of seeing this is:

answer = (sum of multiplies of 3) + (sum of multiplies of 5) - (sum of multiples of 15)

these are simple arithmetic series so you don't even need loops.

Upvotes: 7

rubenvb
rubenvb

Reputation: 76795

My guess is you're double counting the common multiples of 3 and 5.

Upvotes: 1

MAK
MAK

Reputation: 26586

Your solution does not take into account the fact that some numbers (like 15) are divisible by both 5 and 3. You are adding them twice in your sum.

Upvotes: 1

zw324
zw324

Reputation: 27210

You are summing up with all the multiples of 15. This is an easy mathematical problem:

In the case of 15, since it is dividable by both 3 and 5, you are counting it twice in both of the functions.

I suggest that you can use one single loop and ||. Of course, a single formula would be better, but that's just mathy, I doubt you will like it:)

BTW, Project Euler is more math/computer science than pure programming, so when in doubt, try to think in a mathy way:)

Upvotes: 2

Related Questions