# Find multiples of 5 or 3 - Project Euler

3

I'm trying to make a problem of this page , and it came out of the following way:

``````public static int metodo() {
int total = 0;
for (int i=1; i<1000; ++i) {
if (i%3 == 0 || i%5 == 0) { total += i; }
};
}
``````

but I'm trying not to use the operator of the rest, and get the multiples multiplying by 5 or 3 in some way but every time I do not try it did not give me the expected result, is there any way to do it by multiplication?

asked by MatiEzelQ 06.08.2016 в 03:33
source

3

In a way this is a math problem rather than a programming one.

First let's calculate the sum of the numbers smaller than X that are multiples of a divisor D. We calculate the maximum multiple of D that is less than X, we call it M (X, D): M (X, D) = ((X-1) integer_ division D) * D

In the case of divider 3: M (1000,3) = 999

We calculate the sum: 3 + 6 + ... + 996 + 999; which we call S (X, D)

This is a arithmetic progression , the sum of which is given by:

Where:

• a1 = D
• an = M (X, D)
• n = M (X, D) / D

That in java we calculate like this:

``````// Calcular S(X,D)
public static int sumaMultiplosMenores( int maximo, int divisor )
{
int maxMultiplo = ((maximo-1)/divisor)*divisor; // M(X,D)
int numTerminos = maxMultiplo/divisor;          // n
return numTerminos*(maxMultiplo+divisor)/2;     // S(X,D)
}
``````

The final result is the sums of the multiples of 3 and 5 that are less than X, that is: S (1000.3) + S (1000.5)

But there is a problem, in doing the above we have added the multiples of 15 twice, to compensate for the subtractions once: Final result = S (1000.3) + S (1000.5) -S (1000.15) )

In java this is:

``````public static int metodo()
{
return sumaMultiplosMenores(1000, 3) +
sumaMultiplosMenores(1000, 5) -
sumaMultiplosMenores(1000, 15);
}
``````

This form requires a constant execution time, while with a loop the time increases as X increases.

source
3

One possibility:

``````public static int metodo2(int n) {
int total = 0;
for( int i = 3; i < n; i += 3 )
total += i;
for( int i = 5; i < n; i += 5 )
total += i;
for( int i = 15; i < n; i += 15 )
total -= i;
}
``````

Explanation: first add all the multiples of 3 and then those of 5. Then we subtract the ones that are multiples of both (therefore, multiples of 15) to correct the fact that we have added them in duplicate before.

0
``````public static int metodo(int n) {
int x=5, y=3;
int c=0, c1 = 0, c2 =0;

for(int i=0;i<n;i++){
if(i%y == 0){
c+=i;
}
else if(i%x == 0){
c+=i;
}

}
return c;
}
``````

If you make the comparisons separately it's easier, I also made those problems and this code gave me the correct result.