Goldbach's weak conjecture in java

Question

I'm trying to write a code for the Goldbach's weak conjecture, which states that every odd number greater than 5 can be expressed as the sum of three prime numbers. I have to print the first three prime numbers that are equal to the given number. this program works but i get Time Limit Exceeded. 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

There are a few improvements that could be made. I am certain there are more that I haven't considered.

• First, try to memoize(save the primes) as they are calculated in a Set to better control and speed up verifying a number is a prime.

• Use the set of primes as divisors to find other primes. They will need to iterated in a ascending order to do this so a SortedSet implementation would be required.

• I would check the sums of the candidates first. If they don't add up to n then no need to check if they are prime.

• You can reduce your nested loops to two by finding primes a and b and then seeing if n-(a+b) is a prime.

• Check this site for better algorithims for finding primes. There are many that have been presented as answers.