Project Euler #1 in Java

I encountered a problem with this code I don't want to see others, so I want to know what my fault is

If we list all natural numbers below 10 as multiples of 3 or 5, we get 3, 5, 6 and 9 The sum of these multiples is 23

Find the sum of all multiples of 3 or 5 below 1000

public class Multiples {
    public static void main (String [] args) {
        int temp = 0;
        int temp2 = 0; 

        for (int i = 0; i <= 1000; i++) {
            if (i % 3 == 0) {
                temp = temp + i;
            }            
        }

        for (int j = 0; j <= 1000; j++) {
            if (j % 5 == 0) {
                temp2 = temp2 + j;
            }
        }

        System.out.println(temp + temp2);
    }
}

I got a value of 267333, which is wrong Did I add it wrong? I know algorithmically that this code may not meet the standard, but it should be useful, right?

Solution

Solution

1)O(n)：

A small improvement of other answers (I can start with 3):

public static void main(String[] args) {
    int sum = 0;
    for (int i = 3; i < 1000; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    System.out.println(sum);
}

For larger input numbers (integer.max_value instead of 1000), you need to:

>195 seconds

2)O(n)= O(n / 3)O(n / 5)O(n / 15)：

This is more effective and uses your initial method (delete the number of two shots):

public static void main(String[] args) {
    long sum = 0 ;
    for ( long i = 3 ; i < 1000 ; i+=3 ){
        sum+=i;
    }
    for ( long i = 5 ; i < 1000 ; i+=5 ){
        sum+=i;
    }       
    for ( long i = 15 ; i < 1000 ; i+=15 ){
        sum-=i;
    }
    System.out.println(sum);
}

In the first case, we have about n (1000) values for I, and in the second case, we have only about n / 3 N / 5 N / 15 (600) The second one is also better because it is less (not if involved)

For larger input numbers (integer.max_value instead of 1000), you need to:

>9 seconds

3)O(1)：

The solution is based on the following observations:

public static void main(String[] args) {
    int nr = 1000;
    nr--;
    int x3 = nr/3;
    int x5 = nr/5;
    int x15 = nr/15;

    long sum1 = 3*x3*(x3+1); 
    long sum2 = 5*x5*(x5+1);
    long sum3 = 15*x15*(x15+1);

    long sum = (sum1+sum2-sum3)/2;
    System.out.println(sum);
}

In this case, even if the input is integer MAX_ Value, the calculation is also very fast (less than 1 ms)