For a given odd number n I want to efficiently compute 3 primes whose sum is equal to n. If there are multiple solutions then I want the one with the smallest primes (I want 2+2+17=21 instead of 3+5+13=21)
This is always possible forn>5.
My current approach is to reduce the problem to computing 2 primes whose sum is equal to n-3 and then I simply output the 2 computed primes and 3 since they obviously sum up to n. I choose 3 since it is the smallest odd prime and when I subtract it from n I get an even number, therefore it should be part of every solution I'm looking for. I'm using this to compute the sum of 2 primes, it works if n is even which it is in my case (since I subtracted 3 from an odd n).
My approach doesn't work since there are solutions without a 3 as a summand (41=2+2+37).
Is there a straightforward approach which I'm missing?
First test whether n-4 is prime. If so, your answer is {2, 2, n-4}. Otherwise, your original approach will work. You'll never use just one 2 because your sum would be even.