完美力量的总和

import java.util.ArrayList;

public class SumsOfPerfectPowers {

    ArrayList<Long> numList = new ArrayList<Long>(5000001);
    // status of whether a number is power number
    boolean[] result = new boolean[5000001];

    public SumsOfPerfectPowers() {
        numList.add((long) 0);
        numList.add((long) 1);
        for (int i = 2; i <= 2237; i++) {
            int j = 2;
            double value;
            while ((value = Math.pow(i, j)) <= 5000000) {
                numList.add((long) value);
                j++;
            }
        }

        int len = numList.size();
//      System.out.println(len);
        int value;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                value = (int) (numList.get(i) + numList.get(j));
                if (value <= 5000001) {
                    result[value] = true;
                }
            }
        }


    }

    static {
    }

    public int howMany(int a, int b) {
        int sum = 0;
        for(int i=a;i<=b;i++) {
            if(result[i]) {
                sum ++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        SumsOfPerfectPowers test = new SumsOfPerfectPowers();

        System.out.println(test.howMany(0, 1));
        System.out.println(test.howMany(5, 6));
        System.out.println(test.howMany(25, 30));
        System.out.println(test.howMany(103, 103));
        System.out.println(test.howMany(1, 100000));

    }

}

#1 楼

(long) 0的结构应写为0L。

numList和result的访问修饰符应为private： > ArrayList<...>参考类型应该只是List<...>。请参阅：有效Java，第2版，第52条：通过其接口引用对象

private ArrayList<Long> numList = new ArrayList<Long>(5000001);
// status of whether a number is power number
private boolean[] result = new boolean[5000001];

是一个魔术数字。使用命名常量而不是数字将使代码更易读，更不易碎。如果您必须修改它的价值，那么很容易忘记在任何地方都要做。 5000000也是一个幻数和一个计算值。我要创建一个MAX常量：

private List<Long> numList = new ArrayList<Long>(5000001);

并在各处使用它，例如：

private static final int MAX = 5000000;

然后将2237更改为以下内容：

private boolean[] result = new boolean[MAX + 1];

2237仅在构造函数中使用，因此它可能是局部变量而不是字段。尝试最小化变量的范围。请参阅有效Java，第二版，项目45：最小化局部变量的范围。
实际上，我将numList重命名为numList，因为它存储了完美的能力。我将使代码更具可读性，更易于维护。

将列表的初始容量设置为perfectPowers，而该列表仅包含2500个元素。这是一个巨大的内存浪费。我会使用5000000的默认构造函数，该构造函数使用更少的内存。

final int maxSquare = (int) Math.ceil(Math.sqrt(MAX));
for (int i = 2; i <= maxSquare; i++) { ... }

ArrayList使用的浮点数并不总是精确的。对于较小的数字，这是正确的，但对于较大的数字，它不是：

final List<Long> perfectPowers = new ArrayList<Long>();

它打印：因此，我将Math.pow循环更改为以下内容：

final long a = 97761243;
final long aa = a * a;
System.out.println("long            " + aa);
System.out.println("Math.pow        " + ((long) Math.pow(a, 2)));
System.out.println("BigInteger.pow: " + BigInteger.valueOf(a).pow(2).longValue());

同一循环上的一些其他更改将导致以下结果：

long            9557260632905049
Math.pow        9557260632905048
BigInteger.pow: 9557260632905049

它的作用相同，但我认为它更易于阅读。

在第一个for循环中，我将while重命名为i，将base重命名为j，并将exponent方法的参数重命名为howMany和lowerBound。
/>

long value;
while ((value = BigInteger.valueOf(i).pow(j).longValue()) <= MAX) {
    perfectPowers.add(value);
    j++;
}

#2 楼

除了不需要重复的其他答案，

在几乎所有情况下，boolean[]都可以替换为BitSet。它占用了大量（确定性）空间，并且为您提供了合理的操作，如果您尝试在boolean[]上手动进行操作，则很可能会在最坏的情况下引入细微的错误，并最好地重新发明轮子。 :-)

#3 楼

有几点评论：通常，建议将变量声明为接口类型，以尽可能实现可扩展性和与实现无关。在编写大型程序时，您会意识到这一点。基于此，numList的类型将为List或Collection。
不是强制类型转换为（long），您只需在值后加上'L'即可使其变长。
建议声明成员变量为私有。默认范围是包私有。
不了解空静态块的用途！

#4 楼

我就是这样写的：

import java.util.ArrayList;
import java.util.List;

public class SumsOfPerfectPowers {

    private final static int SIZE = 5000001;
    private final boolean[] result = new boolean[SIZE];

    public SumsOfPerfectPowers() {
        List<Long> numList = fillNumList();
        fillResults(numList);
    }

    private List<Long> fillNumList() {
        List<Long> numList = new ArrayList<Long>(SIZE);
        numList.add(0L);
        numList.add(1L);
        int limit = 1 + (int) Math.sqrt(SIZE);
        for (int i = 2; i <= limit; i++) {
            for(long j = 2, value = i*i; value < SIZE; j++, value = (long) Math.pow(i, j)) {
                numList.add(value);
            }
        }
        return numList;
    }

    private void fillResults(List<Long> numList) {
        int len = numList.size();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int value = (int) (numList.get(i) + numList.get(j));
                if (value < SIZE) {
                    result[value] = true;
                }
            }
        }
    }

    public int howMany(int a, int b) {
        int sum = 0;
        for(int i=a; i<=b; i++) {
            sum += result[i] ? 1 : 0;
        }
        return sum;
    }

    //...
}

通常成员应该是私有的（有例外，例如对于最终成员，可以将它们公开）
不要使用幻数，给它们起个名字。或让客户端提供它们（可能有合理的默认值）
更喜欢for循环，请注意，您可以具有多个init和step部分。通常，请尝试限制变量的范围。
请尽量避免while中的“先分配再比较”模式


尝试使您的方法更小例如List）
不要在对象中保留不必要的数据。对于这么长的清单，即使鲍勃叔叔也会避免这样做

#5 楼

构造函数



幻数：各地都有无法解释的常量：5000001、2237、5000000。该限制应该只定义一次，最好作为构造函数的参数。

使用long：数组索引只能是int，而不能是long（JLS Sec 10.4）。因此，您可以支持的最大限制是Integer.MAX_VALUE。如果是这样，那么numList也应该存储Integer而不是Long。但是，我仍然建议使用long来存储您的中间和和乘积，以防止溢出。

浮点数的使用：浮点数计算永远不能用于整数算术证明。



我会像这样启动您的构造函数： = b + a，构建result时，您可以平均将内部循环减半。如果像我上面所做的那样排序完美功率列表，则可能会发生更多短路。

public SumsOfPerfectPowers(int limit) {
    this.limit = limit;

    SortedSet<Integer> perfectPowers = new TreeSet<Integer>();
    perfectPowers.add(0);
    perfectPowers.add(1);
    for (int base = 2; base * base < limit; base++) {
        for (long n = base * base; n < limit; n *= base) {
            // n is long to guard against overflow.
            // Casting n to int is safe because n < limit, which is an int.
            perfectPowers.add((int)n);
        }
    }
    // List traversal is faster than tree traversal
    this.perfectPowers = new ArrayList<Integer>(perfectPowers);

    // etc.
}

howMany()



命名：在我阅读代码之前，对我来说，howMany()的目的不是很明显。我建议将howMany()重命名为countInInterval()。

包含和不包含边界：包含和不包含边界是一种非常常见的模式，尤其是在数组从0索引的语言中。检查i < n而不是i <= n。有关更多示例，请考虑：C ++中的std::vector::end

Java中的String.substring(beginIndex, endIndex)

Python中的range(start, stop)

因此，我认为此函数将包含下限和排除上限的参数作为参数是合理的。 …

this.sumOf2 = new boolean[limit];
for (int i = 0; i < this.perfectPowers.size(); i++) {
    for (int j = 0; j <= i; j++) {
        int n = this.perfectPowers.get(i) + this.perfectPowers.get(j);
        if (0 < n && n < limit) {
            sumOf2[n] = true;
        } else {
            break;
        }
    }
}