# Sum the Multiples of 3 and 5

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.

• The formatting makes it nearly unreadable. Code that doesn't look good also typically doesn't run well. – Edward Jul 8 '14 at 11:52
• Hint: you don't need loops at all. How would you find out how many multiples of 3 (or 5, but let's stick with one term for the moment) there were? What stunt did Gauss do as a young student that's applicable? – Clockwork-Muse Jul 8 '14 at 12:30
• possible duplicate of Finding the sum of all the multiples of 3 or 5 below 1000 – sds Jul 8 '14 at 15:27
• @sds: That question is from a different user and about a different language. Such questions are not considered duplicates on Code Review. – Jamal Jul 8 '14 at 23:01

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.

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;
}


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
• Welcome to Code Review! This site is a bit different from the other Stack Exchange Q&A sites - here answers are expected to review the OP's code; please see what makes a good CR-ish answer on our Meta for more details. – Mathieu Guindon Jul 15 '15 at 14:41