Sum the Multiples of 3 and 5

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 N.

  #include <stdio.h>
  int main(){
    int i=0,j,k,l,sum=0;
    scanf("%d",&i);
    if(i<=100000&&i>0){
    for(j=0;j<i;j++){
        scanf("%d",&k);
        if(k<=1000000000&&k>0){
        for(l=3;l<k;l++){
            if(l%3==0||l%5==0)
                {sum+=l;}
        }}
    printf("%d\n",sum);
    sum=0;
    }}

The above code does satisfy all the test cases but it has been rejected citing that it is very slow. Please suggest improvements to the code.

Answer 1

Generally, try to think about the problem before brute-forcing it.

Is there an easy way to sum all the multiples of 3 below \$N\$? Of course there is. First we note that the largest multiple of 3 is \$3 * \lfloor\frac{N}{3}\rfloor\$ and the sum of all the multiples is then \$3 * 1 + 3 * 2 + ... 3 * \lfloor\frac{N}{3}\rfloor\$. Factor out the 3 and you get \$3 * (1 + 2 + 3 + ... \lfloor\frac{N}{3}\rfloor)\$. Now we use Gauss's trick for summing the natural numbers to get a nice easy formula for the sum: \$3*x*\frac{x+1}{2}\$, where \$x\$ is \$\lfloor\frac{N}{3}\rfloor\$.

Similarly, we can get the sum for the multiples of 5, and add the results together. However, we then have a bunch of duplicates (namely multiples of 15) which we can also calculate in a similar manner and then subtract to get the final result.

This approach completely eliminates any and all looping, and so will be super quick.

Now, let's discuss your code. Here's a list of suggestions:

1. If you are prompting the user, provide some helpful hints as to what you are expecting as input.

2. Having hardcoded bounds such as yours is unintuitive. Have your sum be a long or even long long (depending on the desired platform) and you will not run into issues with integer inputs, which are guaranteed by scanf(%d). This will also cut down on the indentation, increasing readability.

3. Variable names are important. While it is pretty easy to see that i, k are the bounds, and j, l are counter variables after reading the code, it would be even easier to understand with lower_bound, upper_bound and i, j for the counters (per standard practices).

4. Consider generalizing the problem to create a function that will be reusable elsewhere.

Answer 2

You can solve it with one for loop. The % operator is predefined for numeric types to compute the remainder after division. So if the remainder after division is 0 then you can add "i" to "sum".

int sum = 0;
for(int i = 1; i < 1000; i++)
{
   int value1 = i%5 == 0?5:0;
   int value2 = i%3 == 0?3:0;
   sum += (value1 + value2) >0 ?i:0;
}

Answer 3

It's a very simple problem to get the answer. Just use the A.P and the answer will be:

(sum of multiple of 3) + (sum of multiple of 5) - (sum of multiple of 15)

Use this formula to calculate the sum = n(a + l) / 2, where n = number of terms.

• a = first term
• l = last term