c - Find the sum of all the multiples of 3 or 5 below 1000

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. I have the following code but the answer does not match.

#include<stdio.h>
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=0;i<=1000;i++)
    {
        if((i%5==0)||(i%3==0))
        {
            sum=sum+1;
        }
    }
    printf("%d
",sum);
    getchar();
    return 0;
}

Answer 1

Rather than using range/loop based solutions you may wish to leverage more math than brute force.

There is a simple way to get the sum of multiples of a number, less than a number.

For instance, the sum of multiples of 3 up to 1000 are: 3 + 6 + 9 + ... + 999 Which can be rewritten as: 3* ( 1 + 2 + 3 + ... + 333)

There is a simple way to sum up all numbers 1-N:

Sum(1,N) = N*(N+1)/2

So a sample function would be

unsigned int unitSum(unsigned int n)
{
    return (n*(n+1))/2;
}

So now getting all multiples of 3 less than 1000 (aka up to and including 999) has been reduced to:

3*unitSum((int)(999/3))

You can do the same for multiples of 5:

5*unitSum((int)(999/5))

But there is a caveat! Both of these count multiples of both such as 15, 30, etc It counts them twice, one for each. So in order to balance that out, you subtract once.

15*unitSum((int)(999/15))

So in total, the equation is:

sum = 3*unitSum((int)(999/3)) + 5*unitSum((int)(999/5)) - 15*unitSum((int)(999/15))

So now rather than looping over a large set of numbers, and doing comparisons, you are just doing some simple multiplication!