问题解决方案euler#3

ou6hu8tu 于 2021-07-09 发布在 Java

关注(0)|答案(3)|浏览(341)

我正试图解决第三个欧拉项目，但我把停止计算的逻辑搞砸了。
这是第三个项目：
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);

}

我知道逻辑不正确，但我真的坚持了一个多小时。
我知道这里的主要目标是循环，找到一个素数，检查这个素数是否是数字的一个因子，并找到最大的一个，但是停止条件是如果循环数是素数，而不是数字的一个因子。
抱歉弄得一团糟，我被卡住了：）谢谢！

Java logic

来源：https://stackoverflow.com/questions/41456532/issue-trying-project-euler-3

3条答案

按热度按时间

sbtkgmzw1#

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

赞(0）回复(0）举报 2021-07-09

cxfofazt2#

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

赞(0）回复(0）举报 2021-07-09

7fhtutme3#

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

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

赞(0）回复(0）举报 2021-07-09

我来回答

问题解决方案euler#3

3条答案

相关问题

热门标签

最新问答