Prime Sum

Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number.

NOTE A solution will always exist. read Goldbach’s conjecture

Example:

Input : 4
Output: 2 + 2 = 4
If there are more than one solutions possible, return the lexicographically smaller solution.

If [a, b] is one solution with a <= b,
and [c,d] is another solution with c <= d, then

[a, b] < [c, d] 

If a < c OR a==c AND b < d.
思路：

一个一个check是不是prime

Solution:

Time: O(nsqrt(n))
Space: O(1)

 public ArrayList<Integer> primesum(int A) {
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 2; i <= A / 2; i ++) {
           if (isPrime(i) && isPrime(A - i)) {
               result.add(i);
               result.add(A - i);
               break;
           }
        }
        return result;
    }
    
    private boolean isPrime(int i) {
        boolean prime = true;
        for (int j = 2; j <= (int) Math.sqrt(i); j ++) {
            if (i % j == 0) {
                prime = false;
                break;
            } 
        }
        return prime;
    }