Euler Project＃3 Java:为什么在找到最大的质量因素时要算成平方根，而不是从平方根倒数

Question

我正在尝试解决Euler项目的问题3，我编写了以下代码，这给了我正确的答案公共类巨大策略{

public static boolean isPrime(int p) {
    boolean isPrime = true;
    for (int i = 2; i < p / 2; i++) {
        if (p % i == 0) {
            return false;
        }
    }
    return isPrime;
}
public static double largestPrimeFactor(long n) {
    double factor = 0;
    for (int j=1; j<Math.sqrt(n); j++) {
        System.out.println("j is : "+ j);
        if (n % j == 0 && isPrime(j)) {
        factor = j;
        }
    }
    return factor;
}

public static void main(String args[]) {
    long limit = 600851475143L;
    System.out.println(largestPrimeFactor(limit));
}}

我想知道，当我们寻找最大因素时，以1起并增加方形根是一个好主意。因此，我尝试更改最大磁源方法中的for循环，以从n的平方根开始并倒数。但是，现在我得到了一个错误的答案。这样做的原因是什么？

public class LargestPrimeFactor {
public static boolean isPrime(int p) {
    boolean isPrime = true;
    for (int i = 2; i < p / 2; i++) {
        if (p % i == 0) {
            return false;
        }
    }
    return isPrime;
}
public static double largestPrimeFactor(long n) {
    double factor = 0;
    for (int j=(int)Math.sqrt(n); 1<j; j--) {
        System.out.println("j is : "+ j);

        if (n % j == 0 && isPrime(j)) {
            factor = j;
        }
    }
    return factor;
}
public static void main(String args[]) {
    long limit = 600851475143L;
    System.out.println(largestPrimeFactor(limit));
}}

Answer 1

找到第一个质量因素后您没有休息 - 第一个找到最大的因素，您不应该进一步搜索。为此，您应该返回您找到的第一个正确值

public static double largestPrimeFactor(long n) {
    double factor = 0;
    for (int j=(int)Math.sqrt(n); 1<j; j--) {
        if (n % j == 0 && isPrime(j)) {
            return j; // Changed this line
        }
    }
    return factor;
}