### Problem:

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.

We need to find the sum of all the multiples of 3 or 5 below 1000.

View this problem on Project Euler.

### Algorithm:

The problem sounds easy and any beginner can solve this in just few minutes.

What we need to do is:

Step 1: Begin a loop from 3 to 1000

Step 2: If the number is either divisible by 3 or 5 add it to sum.

That's it we need to do. But this algorithm works superbly fine on short data range, but when the data range goes beyond 10^{9} the program takes minutes and hours to finish processing. Hence we need an optimal solution to the problem. And the solution lies in the 10 class basic mathematics(Arithmetic Progression).

**Optimal Algorithm:**

Here the basic concepts of Arithmetic Progression is used. We need to calculate sum of n elements.

#### Formula:

Where n is the number of elements, a_{1} is the starting element, and a_{n} is the last element.

Step 1: Compute sum of all elements under 1000 which are divisible by 3

Step 2: Compute sum of all elements under 1000 which are divisible by 5

Step 3: Compute sum of all elements under 1000 which are divisible by 15

Step 4: Add sum1 + sum2 and subtract from sum3 i.e. sum1 + sum2 - sum3 (Where sum1=Sum of all elements divisible by 3, sum2=Sum of all elements divisible by 5, sum3=Sum of all elements divisible by 15) and we are done.

### Program:

/*

* Copyright (C) 2015 PankajPrakashh @ http://codeforwin.blogspot.com/

*

* This program is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program. If not, see http://www.gnu.org/licenses/

*/

import java.util.Scanner;

/**

*

* @author Pankaj

*/

public class ProjectEuler1 {

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

long n = in.nextLong();

n--; //Since we need to compute sum below n.

long sum = 0;

long totalElements = 0;

//Check if n is more than or equal to 3 then compute sum of all elements

//divisible by 3 and add to sum.

if(n>=3) {

totalElements = n/3;

sum += (totalElements * ( 3 + totalElements*3)) / 2;

}

//Check if n is more than or equal to 5 then compute sum of all elements

//divisible by 5 and add to sum.

if(n >= 5) {

totalElements = n/5;

sum += (totalElements * (5 + totalElements * 5)) / 2;

}

//Check if n is more than or equal to 15 then compute sum of all elements

//divisible by 15 and subtract from sum.

if(n >= 15) {

totalElements = n/15;

sum -= (totalElements * (15 + totalElements * 15)) / 2;

}

System.out.println(sum);

}

}

Happy coding 😉

<pre><code> ----Your Source Code---- </code></pre>