Project Euler #1 - C

Question: 

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.

Solution:

The simple way to complete this is to run two loops that accumulate a shared sum: one that sums the multiples of 3 and another than sums the multiples of 5. But that is too easy... lets add some complexity by completing both sums inside one loop. Again... there is any easy way, and there is a hard way. We could go through a loop 333 times and do each multiple of 3 individually, or we could do it all in 199 iterations for each multiple of 5 and simultaneously sum all multiples of 3. But, 3 * 199 = 597... so that means that we are missing all multiples of 3 over 597. We know that we want to count the numbers 999, 996, 993, 990, ... , 603, 600. Well, 600 / 3 = 200 which is out of the scope of our loop, and 999 / 3 = 333 which is also out of the scope. So lets try dividing by 6. 600 / 6 = 100... good. 999 / 6 = 166 r 3. CRAP! We cant get to 999! So what to do? Add two consecutive multiples in each iteration. That is, we want 

2i * 3 + (2i + 1) * 3

=(2i + 2i + 1) * 3 (by simple factorization)

=(4i + 1) * 3

Finally, Here is my solution written in C. 

int main (void)
{
int i;
int sum = 0;


for (i = 199; i > 0; i--)
{
if ( i < 167 && i > 99)
sum += ( (i<<2) +1 ) * 3; 
if ( i <= 66 )
sum -= 15*i; 

sum += (i<<3);

}
        printf("Sum is %d\n", sum);
return 1;
} 


So now for an explanation of the lines inside the loop. 

if ( i <= 166 && i >= 100)

sum += ( (i<<2) + 1) * 3;

This line is what calculates our multiples between 600 and 999. For the newbies out there, 

(i<<2) == 4*i

One thing that slipped my mind was that many numbers between 0 and 1000 are multiples of both 3 AND 5... namely, all multiples of 15. Thus, these numbers are counted twice and we need to subtract them. There are exactly 66 multiples of 15 less than 1000, so 

if ( i <= 66 )

sum -= 15*i;

takes care of that problem. 

Finally, we need our multiples of 3 and multiples of 5. Or, 3*i + 5*i... well, thats 8*i ! 8 = 2^3... so, 

                sum += (i<<3);

And thats it! Compile, and see the solution before your eyes!