Reputation:
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
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
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
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
Reputation: 76795
My guess is you're double counting the common multiples of 3 and 5.
Upvotes: 1
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
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