正在尝试发布项目euler#3

Question

我试图解决欧拉三号工程，但我对停止计算的逻辑相当混乱。

以下是第三个Euler项目：

13195的质因数是5、7、13、29。

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

主代码中的循环在找到所述数字的第一个素数因子后停止。相反，我们必须消除所有这样的素因子，直到我们达到其中最大的一个。我不愿意在这里分享任何代码，因为问题确实很具体。不要在出现素数除数时中断循环，而是尝试列出所有素数除数。

希望这有帮助。

Answer 2

public class LargestPrimeFactor {
private long num;
public LargestPrimeFactor(long num){
    this.num=num;
}
public long calculate(){
    for(long i=1;i<=num/2;i++)
        if(num%i==0)
            if(isPrime(num/i)) 
                return num/i;

    return 1;
}
private static boolean isPrime(long num){
    for(long i=2;i<=(long)Math.sqrt(num);i++){
        if(num%i==0) return false;
    }
    return true;
}
}

Answer 3

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

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;
}