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.

Source: http://projecteuler.net/problem=1

Solution:

There are multiples of and multiples of . Some of those numbers are multiple of both and (i.e. they are multiples of ). When summing, we need to avoid summing twice we need to subtract those numbers.

There are multiples of . The result is:

This is a simple C++ program that verifies the math:

int main()
{
int n = 1000;
int sum = 0;
for ( int i = 1; i < n; i++ )
{
if ( ( i % 3 == 0 ) || (i % 5 == 0 ) )
{
sum += i;
}
}
int div3 = ( n – 1 ) / 3;
int div5 = ( n – 1 ) / 5;
int div15 = ( n – 1 ) / 15;
int sumDirect = 3 * div3 * ( div3 + 1 ) / 2 +
5 * div5 * ( div5 + 1 ) / 2 – 15 * div15 * ( div15 + 1 ) / 2;
if ( sum != sumDirect )
{
cout<<“Bad idea!”;
}
else
{
cout<<“Excellent!”;
}
}

### Like this:

Like Loading...

*Related*