Check whether a number is a sum of two prime numbers

Question

The problem is to check a random number n can be the sum of 2 random prime numbers. For example,

if n=34 the possibilities can be (3+31), (5+29), (17+17)...

So far I have managed to save prime numbers to the array, but have no clue how I could check, if n is the sum of 2 prime numbers.

This is part of my code:

public static void primeNumbers(int n) {
    int i = 0, candidate = 2, countArray = 0, countPrime = 0;
    boolean flag = true;

    while (candidate <= n) {
        flag = true;
        for (i = 2; i < candidate; i++) {
            if ((candidate % i) == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            countPrime++;
        }
        candidate++;
    }
    int[] primeNumbers = new int[countPrime];


    while (candidate <= n) {
        flag = true;
        for (i = 2; i < candidate; i++) {
            if ((candidate % i) == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            primeNumbers[countArray] = candidate;
        }
        candidate++;
        countArray++;
    }

    for (i = 0; i <= primeNumbers.length; i++) {

    }
}

First I counted how many prime numbers are between 1-n so I can declare and initialize my array for prime numbers. Then I save prime numbers to the array. But now I have no idea how I could check if n is the sum of 2 prime numbers.

Answer 1

Given that you already have list of "prime numbers less than the given number", It is a very easy task to check if two prime numbers can sum to given number.

for(int i=0; i<array.length; i++){

    int firstNum = array[i];
    int secondNum = givenNum - firstNum;

    /* Now if it is possible to sum up two prime nums to result into given num, secondNum should also be prime and be inside array */

    if(ArrayUtils.contains(array, secondNum)){
        System.out.println("Yes, it is possible. Numbers are "+ firstNum + " and " + secondNum);
    }
}

EDIT: ArrayUtils is part of Apache Commons Lang library You can however use ArrayList instead to use contains method.