java 中的哥德巴赫弱猜想

Question

我正在尝试为 Goldbach's weak conjecture 编写代码，其中规定每个大于 5 的奇数都可以表示为三个质数之和。我必须打印前三个等于给定数字的质数。该程序有效，但我超出了时间限制。 5 < N < 10^18

public static void FindPrimes(int n){
    boolean found = false;
    if(n%2 == 1 && n > 5){
        for(int i=n; i>=2; i--){
            for(int j=i; j>=2; j--){
                for(int k=j; k>=2; k--){
                    if(NumberIsPrime(i) && NumberIsPrime(j) && NumberIsPrime(k)){
                        if(i + j + k == n){
                            System.out.println(k+" "+j+" "+i);
                            found = true;
                            return;
                        }
                    }
                }
            }
        }
        if(!found){
            System.out.println(-1);
        }
    }
}
public static boolean NumberIsPrime(int x){
    if (x == 0 || x == 1){
        return false;
    }
    for (int i = 2; i * i <= x; ++i){
        if (x % i == 0){
            return false;
        }
    }
    return true;
}

Answer 1

可以进行一些改进。我敢肯定还有更多我没有考虑到的。

首先，尝试记忆（保存素数），因为它们是在 Set 中计算的，以更好地控制和加速验证数字是否为素数。
使用质数集作为约数来找到其他质数。他们需要按升序迭代才能执行此操作，因此需要 SortedSet 实现。
我先查一下考生的总和。如果它们加起来不等于 n 则无需检查它们是否为质数。
您可以通过查找素数 a 和 b 然后查看 n-(a+b) 是否为素数来将嵌套循环减少到两个。
查看此站点以获得更好的查找素数的算法。有许多已作为答案呈现。

java 中的哥德巴赫弱猜想

Goldbach's weak conjecture in java

java

math

discrete-mathematics