为什么我的程序没有给出预期的输出？

Question

我正在研究 Project Euler 的问题 29，其中指出：

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^2=4, 2^3=8, 2^4=16, 2^5=32

3^2=9, 3^3=27, 3^4=81, 3^5=243

4^2=16, 4^3=64, 4^4=256, 4^5=1024

5^2=25, 5^3=125, 5^4=625, 5^5=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

我已经在Java中编写了解决这个问题的程序。它运行没有任何错误，但是没有给出预期的输出。我在下面提供了我的代码和输出。

import java.util.ArrayList;
import java.math.BigInteger;
public class problemTwentyNine {
  public static void main(String [] args) {
    long start = System.nanoTime();
    ArrayList<BigInteger> distinctTerms = new ArrayList<BigInteger>();
    BigInteger temp;
    for(int i = 2; i <= 100; i++) {
      for(int j = 2; j <= 100; j++) {
        temp = new BigInteger("" + (int) (Math.pow(i, j)));
        if(!distinctTerms.contains(temp)) {
          distinctTerms.add(temp);
        }
      }
    }
    System.out.println(distinctTerms.size());
    long stop = System.nanoTime();
    System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms");
  }
}

输出：

422

Execution time: 24.827827ms

在project euler上输入这个答案后，发现不正确；但是我看不出我的代码哪里出了问题。

Answer 1

行 (int) (Math.pow(i, j)) 没有多大意义，因为 100^100 比 Integer.MAX_VALUE 大得多。您应该使用 BigInteger.

来执行这些操作

应该是

temp = BigInteger.valueOf(i).pow(j);

Answer 2

您只获得 422 个不同元素的原因是您的值太大并且您将它们转换为 int。

当 Math.pow(i, j) (a double) 的结果大于 Integer.MAX_VALUE 并且您转换为 int，则结果为 Integer.MAX_VALUE .

Section 5.1.3 of the JLS 涵盖了这个 缩小基元转换 :

Otherwise, one of the following two cases must be true:

The value must be too small (a negative value of large magnitude or negative infinity), and the result of the first step is the smallest representable value of type int or long.

The value must be too large (a positive value of large magnitude or positive infinity), and the result of the first step is the largest representable value of type int or long.

（强调我的）

你经常得到那个结果，所以只有 422 个不同的结果。

将您的计算更改为 BigInteger 数学。

temp = new BigInteger("" + i).pow(j);

通过这一更改，我现在获得了 9,183 个不同的元素。这更有意义，因为将重复完全平方的某些次方。

为什么我的程序没有给出预期的输出？

Why is my program not giving the expected output?

java

arraylist

biginteger