Find minimum prime numbers which sum to a given value

Question

I want to find the minimum set of prime numbers which would sum to a given value e.g. 9 = 7 + 2 (not 3+3+3).

I have already generated a array of prime numbers using sieve of eratosthens

I am traversing the array in descending order to get the array largest prime number smaller than or equal to given number. This works great if the number is odd. But fails for even numbers e.g 122 = 113 + 7 + 2 but 122 = 109 +13.

From Golbach's Conjecture we know that any even number can be represented as two sum of two prime numbers. So if a number is even we can directly return 2 as output.

But I am trying to figure out a way other than brute force to find minimum prime numbers.

Answer 1

Try this out! Not an ideal code but if you want to have a working solution :P

primes = [2,3,5,7]
D = 29
i = -1
sum_ = 0
count = 0
while sum_ != D :
    sum_ = sum_ + primes[i]
    count += 1
    if (sum_ == D) :
        break
    elif D - sum_ == primes[i-1] :
        count += 1
        break
    elif D - sum_ < ex[i-1] and (D-sum_ not in primes) :
        sum_ = sum_ - primes[i]
        count = count - 1
        i = i - 1
print(count)

Answer 2

Although your question didn't say so, I assume you are looking for the set of primes that has the smallest cardinality.

If n is even, then consider the primes p in order, 2, 3, 5, …; eventually n - p will be prime, so n is the sum of two primes. This process typically converges very quickly, with the smaller of the two primes seldom larger than 1000 (and usually much smaller than that).

If n is odd, and n - 2 is prime, then n is the sum of the primes 2 and n - 2.

If n is odd, and n - 2 is not prime, then n - 3 is even and can be written as the sum of two primes, as described above.

Thus you can always find two or three primes that sum to any target n greater than 3.