java - Project Euler #3 Java 解决方案问题

Question

class eulerThree {

    public static void main(String[] args) {

        double x = 600851475143d; 

        for (double z = 2; z*z <= x; z++) {

            if (x%z == 0) {

                System.out.println(z + "PRIME FACTOR");

            }

        }

    }

}

输出是:

71.0
839.0
1471.0
6857.0
59569.0
104441.0
486847.0

因此，我假设 486847 是 x 的最大质因数，但欧拉计划却另有说法。我在我的代码或我的数学中没有发现问题，所以我很困惑。你能看到我看不到的东西吗？

Answer 1

首先，你必须使用准确的算术手段。其他人建议使用 BigInteger .你可以这样做。对我来说，这感觉有点像作弊(这对于以后处理更大整数的问题更重要)所以更有趣的方法(恕我直言)是自己编写必要的任意精度操作。

其次，600851475143 足够小，可以用 long 精确计算，这会快得多。

第三，您的循环没有正确检查质因数。你只是检查奇数。这是一个准系统(不完整)的解决方案:

long num = 600851475143L;
List<Long> factors = new ArrayList<Long>(); // or use a Set
if (num & 1 == 0) {
  factors.add(2L);
}
for (long i=3; i*i<=num; i+=2) {
  // first check i is prime
  // if i is prime check if it is a factor of num
}

检查是否为质数有不同的实现水平。最天真的:

public boolean isPrime(long num) {
  for (long i=2; i<=num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

当然会进行各种不必要的检查。正如您已经确定的那样，您只需要检查最多为 sqrt(n) 的数字。你可以消除偶数(2 除外):

public boolean isPrime(long num) {
  if (num & 1 == 0) {
    return false; // checks divisibility by 2
  }
  for (long i=3; i*i<=num; i+=2) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

但您也可以做得比这更好。另一个优化是您只需要检查该范围内的质数的数字。 63 的质因数是 3 和 7。如果一个数不能被 3 或 7 整除，那么根据定义它不能被 63 整除。

所以你想做的可能是建立一个 Set<Long>或质数，直到平方等于或大于您的目标数。然后只需检查这一系列数字是否可以整除目标。