3

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.

Improve this question
3
  • "So if a number is even we can directly return 2 as output" - ähm, no it is a conjecture ... Commented Mar 2, 2016 at 19:10
  • @Meiko well it hasn't been proved wrong yet. So we can safely assume it to be correct. :) Commented Mar 2, 2016 at 19:15
  • 1
    @Meiko Goldbach's conjecture has been verified to hold up to 4 x 10^16, so depending on what Leo is doing (only using 32 bit numbers for example), returning 2 may make sense. Commented May 11, 2017 at 0:20

2 Answers 2

Reset to default
10

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Yes i get that point, but I want to find it by traversing the array not by using Golbach's Conjecture. As I have already said in my question for odd numbers traversing array in descending order to find the sum works perfectly but not for even numbers. As in case of 122, so I am curious for any other approach towrads traversal. I hope i have made myself clear now.
I guess I don't understand your definition of minimum. For instance, 122 = 2 + 7 + 113 = 13 + 109. If "minimum" means the set with smallest cardinality, then 13 + 109 has only two members. If "minimum" means the set that has the smallest minimum element, then 2 + 7 + 113 has an element of 2. I guess you prefer the 13 + 109 solution, which is the one my algorithm finds. The difference seems to be that I start from the smallest prime, you start from the largest prime.
@user448810 — Would it have been clear if they had said "minimal set of prime numbers" instead of "minimum prime numbers"?
0

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)
Improve this answer

2 Comments

For my problem the number of primes were given, for example here the number is 4, if you want you can populate the primes list with the prime number less than the given Sum(D)
I have solved this problem using Globach's Conjecture. Still curious about your solution how did come up with D as 29? Also Is your solution generic enough? How will it work when we have an array of size 1000? Can you please explain?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.