Sum of multiples of 3 or 5

5

I'm trying to build a program that finds and adds the multiples of 3 or 5 below 1000.

The problem is that it is returning a result of the sum that does not match what I ordered.

    package basicojava;

public class Multiplos {
    public static void main(String[] args) {
        int x = 3;
        int z = 5;
        int somax = 0;
        int somaz = 0;
        int res;

        for(int i = 1; i < 1000; i++) {
            if(x % i == 0) {
                somax = i + i;
            }
        }
        for(int i = 1; i < 1000; i++) {
            if(z % i == 0) {
                somaz = i + i;
            }
        }
        res = somax + somaz;

        System.out.println("A soma dos multiplos de 3 e 5 abaixo de 1000, é: " +res);

    }
}

The sum is returning 16.

    
asked by anonymous 15.08.2017 / 02:24

5 answers

12

According to this answer in SOEn , there is an error in your logic. The correct would be to divide the i by the x or z to see if they are multiples, and add to the cumulative variables:

public static void main (String[] args) {
    int x = 3;
    int z = 5;
    int somax = 0;
    int somaz = 0;
    int res;

    for(int i = 1; i < 1000; i++) {
        if(i % x == 0) {
            somax += i;
        }
    }
    for(int i = 1; i < 1000; i++) {
        if(i % z == 0) {
            somaz += i;
        }
    }
    res = somax + somaz;

    System.out.println("A soma dos multiplos de 3 e 5 abaixo de 1000, é: " +res);
}

However, the above code will add a common multiples of 3 and 5 twice, since you are doing the summation in separate loops, which will affect the result.

Another way to do this by unifying everything in a loop and avoiding the problem mentioned is as below:

int x = 3;
int z = 5;
int res = 0;



for(int i = 0; i < 1000; i++){
    if(i % x == 0 || i % z == 0){
        res += i;
    }
}

System.out.println("A soma dos multiplos de 3 e 5 abaixo de 1000, é: " +res);

See an example with multiples up to 10 in the ideone , whose result will be 23 (3 + 6 + 9 + 5 = 23 ) .

    
15.08.2017 / 02:37
11

Solution using IntStream

From Java 8 you can use the IntStream class to do the loop job:

IntStream stream = IntStream.range(1, 1000);

The above code will generate a Stream that represents all integers between 1 and 1000. To get the sum of the values that are multiples of 3 or 5, simply filter through the multiples of 3 or 5 and add them: / p>

long result = stream.filter(value -> (value % 3 == 0 || value % 5 == 0)).sum();

In this way, the value of result will be the sum of all multiples of 3 or 5 between 1 and 1000, 233,168.

  

See working at Ideone .

Mathematical solution ❤️

Another possible solution is to analyze the problem mathematically. If we consider the sum of all values that are multiples of 3, we have:

3 + 6 + 9 + 12 + ... + 993 + 996 + 999

If we put the term 3 in evidence, we have:

3 * (1 + 2 + 3 + 4 + ... + 331 + 332 + 333)

That is, the sum of all multiples of 3 between 1 and 1000 is the triple equivalent of the sum of all integer values between 1 and 333, where 333 refers to the largest multiple of 3, less than 1000, divided by 3. And it is known that the sum of the integers between 1 and X is:

1 + 2 + 3 + 4 + ... + X = X*(X+1)/2

Generalizing, we have that the sum of all the multiples of n, between 1 and N, will be:

S(n) = n*(N/n)*(N/n + 1)/2

Therefore, the sum of all multiples of 3, between 1 and 999, will be:

S(n=3) = 3*(999/3)*(999/3 + 1)/2 = 166.833

Likewise, the sum of all multiples of 5, between 1 and 999, will be:

S(n=5) = 5*(999/5)*(999/5 + 1)/2 = 99.500

However, multiples of 15, which are multiples of 3 and 5, will be counted twice and, to obtain the desired value, one must subtract the sum of the multiples of 15, between 1 and 999: / p>

S(n=15) = 15*(999/15)*(999/15 + 1)/2 = 33.165

Thus, the sum of all multiples of 3 or 5, between 1 and 999, will be:

S = 166.833 + 99.500 - 33.165
S = 233.168

What is the desired result. In Java we can do this:

class Main {
  public static void main(String[] args) {

    int N = 1000;
    int result = sum(3, N-1) + sum(5, N-1) - sum(15, N-1);

    System.out.println(result);
  }

  public static int sum(int n, int N) {
      return n * (N/n) * (N/n + 1)/2;
  }
}
  

See working at Ideone .

    
15.08.2017 / 14:51
4

Just adding, everything depends on interpretation, where it can go wrong.

In the question speak

  

... multiples of 3 and 5 below 1000.

That is

i % 3 && i % 5

I would this ideone :

 for(int i = 1; i < 1000; i++){
    result = (i % n1 == 0 && i % n2 == 0)? result += i : result;
 }

If you are multiples of 3 or 5 below 1000, this would result in a totally different result.

That is

i % 3 || i % 5

I would this ideone :

 for(int i = 1; i < 1000; i++){
    result = (i % n1 == 0 || i % n2 == 0)? result += i : result;
 }

Note: The int is starting with 1 because adding 0 is same as adding with nothing.

    
15.08.2017 / 03:08
1

The sum of multiple numbers of n is a sum of arithmetic progression with ratio equal to n .

One way to reduce the complexity of O (n) to O (1) is to use formula for this sum,

soma_de_pa = (primeiro_elemento + enesimo_elemento) * n / 2;

In this way, the desired program would have the following face ,

class Programa {
    public static void main(String []args){
        int primeiro_elemento = 0;

        int enesimo_elemento_multiplo_3 = 1000 - (1000 % 3);
        int enesimo_elemento_multiplo_5 = 1000 - (1000 % 5);
        int enesimo_elemento_multiplo_15 = 1000 - (1000 % 15);

        double n_multiplo_3 = Math.ceil(1000 / 3.0);
        double n_multiplo_5 = Math.ceil(1000 / 5.0);
        double n_multiplo_15 = Math.ceil(1000 / 15.0);

        double soma_multiplo_3 = (primeiro_elemento + enesimo_elemento_multiplo_3) * n_multiplo_3 / 2.0;
        double soma_multiplo_5 = (primeiro_elemento + enesimo_elemento_multiplo_5) * n_multiplo_5 / 2.0;
        double soma_multiplo_15 = (primeiro_elemento + enesimo_elemento_multiplo_15) * n_multiplo_15 / 2.0;

        // O total é a soma dos múltiplos de 3 mais a soma dos
        // múltiplos de 5, menos a soma dos múltiplos de 15, que
        // foi contabilizada duas vezes, nas duas primeiras parcelas.
        // (obrigado, Anderson Carlos Woss, pela dica!)
        double soma = soma_multiplo_3 + soma_multiplo_5 - soma_multiplo_15;

        System.out.println(soma_multiplo_3);
        System.out.println(soma_multiplo_5);
        System.out.println(soma_multiplo_15);
        System.out.println(soma);
    }
}
    
06.06.2018 / 20:02
0
public class somaMultiplos {

    public static void main(String[] args) {
        int numeroTres = 3;
        int numeroCinco = 5;
        int somaMultiploTres = 0;
        int somaMultiploCinco = 0;
        int resultado = 0;

        for(int i = 0; i < 1000; i++) {
            if((i%numeroTres == 0)||(i%numeroCinco == 0))
                resultado += i;     

            if((i%numeroTres == 0)&&(i%numeroCinco == 0))
                resultado += i;
        }
        // vai haver momentos de existir número múltiplos de 3 e de 5 ao mesmo tempo 
        // e portanto o primeiro "if" não leva isso consideração 
        //o segundo "if" é justamente para somar os números que são múltiplos de 3 e 5 ao mesmo tempo


        System.out.println("A soma dos multiplos de 3 e 5 abaixo de 1000, é: " +resultado);
    }
}
    
15.08.2017 / 14:28