java - 尝试项目 euler #3 时出现问题

Question

我正在尝试解决欧拉项目三，但我对停止计算的逻辑感到非常困惑。

这是第三个欧拉项目:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

好吧，我创建了一个函数来检查数字是否为素数:

public static boolean isPrime(int number) {
    if (number % 2 == 0)
        return false;
    
    for (int i = 3; i*i <= number; i+=2) {
        System.out.println("Dividing the number " + number + " by: " + i);
        if (number % i == 0)
            return false;
    }
    return true;
}

还有一个检查素数是否是该数字的因子的函数:

 public static boolean isFactor(int number, int prime) {
    if (number % prime == 0)
        return true;
    else
        return false;
}

唯一的问题是主要功能，我正在尝试类似的东西:

 public static void main(String[] args) {
    
    int number = 13195;
    int i = 3;
    
    do {
        i++;
    } while (isPrime(i) && isFactor(number, i) == false);
    
    System.out.println(i);
    
}

我知道逻辑不正确，但我确实卡在上面一个多小时了。

我知道这里的主要目标是循环，找到一个素数并检查这个素数是否是该数字的一个因子并找到最大的一个，但是停止条件是循环数字是否是一个素数并且不是一个数字的因数。

抱歉搞得一团糟，我很困惑:)谢谢!

Answer 1

你的逻辑的主要问题是你从最小的质数开始，一旦它遇到一个质数和给定数字的因子，你的程序就会停止。你应该做的是从另一端开始。我们知道一个数字的任何素数都不会大于该数字的平方根，所以你可以做的是:

int number = 13195;
int i = (int)Math.sqrt(number);

do {
    i--;
} while (isPrime(i) && isFactor(number, i) == false);

System.out.println(i);

600851475143 还有其他变化，这不适合 int，所以无论你在计算它，都尝试使用 long。

这是我对这个问题的解决方案，它不是100%正确，但它适用于这个问题。

public static void main(String[] args) {
    long number= 600851475143L;
    int rootOfNumber = (int)Math.sqrt(number)+10;
    for(int i = rootOfNumber; i > 2; i--) {
        if(number % i == 0) {
            if(psudoprime(i)) {
                System.out.println(i);
                break;
            }
        }
    }

}

public static boolean psudoprime(int num) {
    for(int i = 2; i < 100; i++) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}