Java 抛出除以零错误

Question

为了重新学习如何用Java编写代码，我遇到了欧拉项目的一些问题。我编写的以下代码用于解决问题 3：找到数字600851475143的最大素因数。

public class ProjectEuler {
/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    ProjectEuler t = new ProjectEuler();
    System.out.println(t.findLargestPrime(600851475143L));
}
public Boolean isPrime(int x) {
    Boolean answer = true;
    for (int i = 2; i < x/2; i++) {
        if (x%i == 0) {
            answer = false;
    }
}
    return answer;
}
public int findLargestPrime(Long max) {
    int largest = 1;
    for (int i = 2 ; i < max/2; i++) {
        if (max%i == 0 && isPrime(i) && i > largest) {
            largest = i;
        }
    }
    return largest;
}
}

但是，当我运行它时，代码会抛出算术错误，因为我试图除以零？实际的错误消息如下所示：

Exception in thread "main" java.lang.ArithmeticException: / by zero
at projecteuler.ProjectEuler.findLargestPrime(ProjectEuler.java:37)
at projecteuler.ProjectEuler.main(ProjectEuler.java:19)

我不知道我是否在某处犯了一个愚蠢的错误，或者这是否是我不理解的Java怪癖？谁能对此有所了解？

谢谢。

Answer 1

for (int i = 2 ; i < max/2; i++)最终会溢出(因为600851475143 / 2大于Integer.MAX_VALUE(，最终i将等于0何时发生max%i抛出该异常。

如果要防止i发生，请将更改为long(您还应该将所有其他int更改为long(。

Answer 2

这不是实际问题的答案，但是： 你不必检查所有数直到max，你甚至不必做任何检查除数是否是素数。你只需要(反复(将max除以你找到的任何除数i。

long l = 600851475143L;
for (int i = 2; i <= Math.sqrt(l); i++) {
    if (l % i == 0) {
        System.out.println(i);
        l /= i;
        i--;
    }
}
System.out.println("--> " + l);

这样，你就知道这个除数一定是素数——如果它是复合的，max早就被它的分量除以了。这也意味着您不必一直循环到max(对于给定的值，这将需要很长时间(，而只需要最大素数除数，它可能要小得多。一旦你达到sqrt(l) - 对于l的当前值，而不是原始值！-- 你可以停止，因为不能有任何比这更高的除数，并且 l 的剩余值将是最终(因此也是最大的(素因数。

因此，这将复杂度从大约O(n²(降低到大约O(n^1/2(。