How to Find Two Primes Whose Sum is Equal to a Number N? I have been asked questions about primes in many, many interviews and this is definitely one of the questions that have stuck with me.

First thing first, as always, let us clear out any assumptions. As it turns out, usually problems that involve Maths, are more straight-forward in what they ask. The few questions that you might ask are:

- What should we do if we find multiple such tuples of two primes whose sum is equal to a number N? For now we can assume that just returning the one which has the smallest number, will be fine.
- Where do we start counting? Do we count 0 or 1as a possible “prime” number? As it turns out the specific definition of a Prime Number, specifies that a number must be greater than 1 to be considered a prime

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Let us try to devise an algorithm, that would somehow solve our problem. A general brute force approach would be to go through all possible numbers and check if they can form a prime tuple whose sum is equal to some number N we are given.

## How to Find Two Primes Whose Sum is Equal to a Number N – Algorithm Basics

- For each number i from 2 to N.
- If i and N-i are both primes, return the tuple.

Looks pretty simple does it not? The only missing piece is how do we check that the numbers are prime.

## How to Find Two Primes Whose Sum is Equal to a Number N – Primality Test for i

- For each number j from 2 to to i-1.
- If the remainder of i divided by any of the js is 0, then this is not a prime.

Everything should be pretty clear by now. All we have to do is try to put our solution to code.

## How to Find Two Primes Whose Sum is Equal to a Number N – Brute Force Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public class PrimeUtils { public ArrayList<Integer> primeSum(int N) { ArrayList<Integer> primeTuple = new ArrayList<Integer>(); for (int i = 2; i < N; i++) { if (isPrime(i) && isPrime(N-i)) { primeTuple.add(i); primeTuple.add(N-i); break; } } return primeTuple; } public static boolean isPrime(int possiblePrime) { int primeSqrt = (int) Math.sqrt(possiblePrime); for (int i = 2; i <= primeSqrt; i++) { if (possiblePrime % i == 0) { return false; } } return true; } } |

Looks good and simple. Now let’s do a Time and Space complexity analysis. We are only keeping some static sized array as our solution. Hence Space Complexity is **O(1)**. For time on the other hand, we are looking through all items from 1-N, and doing a primality test for all of them, by again going from 1-N. It seems obvious the time complexity is **O(N ^{2})**. NOTE: Even with our nice small optimization of putting a square root on the primality test, the time complexity remains the same. DO NOT mistake square root, with the most commonly utilized in complexity analysis, log(N).

With all that said and done, can we do better? As it turns out we should be able to, but I will leave that to up to you guys this time! Here are a few hints and approaches that we could take:

## How to Find Two Primes Whose Sum is Equal to a Number N – Further optimizations

- What if instead of checking for numbers being primes from scratch all the time, we reuse some of the work we do?
- What if instead of checking for numbers being primes, we compile a huge list of prime numbers up to N and then simply check over those?

#### Latest posts by Ajk (see all)

- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017