CODEWITHSUNDEEP
sumprimes
knbdtu
knbdtu

Reputation: 65

Write a number N as sum of K prime numbers

Is there any condition for writing a number N as sum of K prime numbers(prime numbers not necessarily distinct)?

Example: If N=6 and K=2 then we can write N as 6=3+3 whereas if N=11 and K=2 then we cannot represent 11 as sum of two primes.

My Approach- I deduced the condition that If K>=N then we cannot represent N as sum of K primes.Also if K=1 then by primality testing we can check whether whether N is a prime number. Also by goldbach's conjecture for even numbers(except 2) N can be represented as sum of two prime numbers.

But the main problem is that I'm not able to predict it for K>=3.

Upvotes: 1

Views: 1609

Answers (1)

Rahul Yadav
Rahul Yadav

Reputation: 41

1.Well, first list out all the prime numbers less than and equal to N.

2.Brute Force Approach with backtracking method.

ex :

N = 8

k = 2.

  1. 2 2
  2. 2 3
  3. 2 5
  4. 2 7
  5. 3 3(Don't again consider 3 and 2)
  6. 3 5. Done!

ex : 2

N = 12, k = 4

  1. 2 2 2 2
  2. 2 2 2 3
  3. 2 2 2 5
  4. 2 2 2 7
  5. 2 2 3 3(don't again check for 2232)
  6. 2 2 3 5. Done!

ex 3:

N = 11, k = 3

  1. 2 2 2
  2. 2 2 3
  3. 2 2 5
  4. 2 2 7
  5. 2 2 11
  6. 2 3 3(don't check again for 232)
  7. 2 3 5
  8. 2 3 7>11(don't check for 2311)
  9. 3 3 3(don't again check the 32.. series.) 10.3 3 5 Done!

Upvotes: 0

Related Questions