Java中的项目Euler＃1 [英] Project Euler #1 in Java

问题描述

我遇到了这段代码的问题。我不想看别人，所以我想知道我的错是什么。

I'm having problems with this code. I don't want to look at others, so I'm wondering what's wrong with mine.

如果我们列出10以下的所有自然数是3或5的倍数，我们得到3,5,6和9.这些倍数的总和是23。

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.

查找低于1000的3或5的所有倍数之和。

Find the sum of all the 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);
    }
}

我得到的值是267333，这是错误的。我的添加错了吗？我在算法上知道，这段代码可能达不到标准，但它应该有用，对吧？

The value I get is 267333, which is wrong. Is my adding wrong? I know algorithmically, this code might not be up to par, but it should work, right?

推荐答案

解决方案

1）O（n）：

其他答案的小改进（ i 可以从 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);
}

输入更大的数字（ Integer.MAX_VALUE 而不是 1000 ）需要：

For a bigger input number ( Integer.MAX_VALUE instead of 1000 ) it takes:

• 195秒

效率更高并使用初始方法（删除两次拍摄的数字）：

This is more efficient and uses your initial approach (remove numbers that were taken twice):

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

在第一种情况下，我们有大约 n （1000） i 的值，在第二种情况下我们只有 n / 3 + n / 5 + n / 15 （$ 600） i 的值。第二个也更好，因为比较少（没有，如果涉及）。

In the first case we have about n (1000) values for i, in the second case we have only about n/3 + n/5 + n/15 (600) values for i. The second one is also better because there are fewer comparisons ( no if involved ).

对于更大的输入数字（ Integer.MAX_VALUE 而不是 1000 ）需要：

For a bigger input number ( Integer.MAX_VALUE instead of 1000 ) it takes:

• 9秒

此解决方案基于以下观察：

This solution is based on the following observation:

1 + 2 + ... + n = n *（ n + 1）/ 2

1 + 2 + ... + n = n*(n+1)/2

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

在这种情况下，即使输入为整数.MAX_VALUE ，计算速度非常快（小于1毫秒）。

In this case, even if the input is Integer.MAX_VALUE, the computation is very fast ( less than 1 ms ).

这篇关于Java中的项目Euler＃1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！