CODEWITHSUNDEEP
algorithmdynamic-programming
user3634974
user3634974

Reputation: 111

Represent a number as sum of primes

I am given a large number n and I need to find whether it can be represented as sum of K prime numbers.

Ex 9 can be represented as sum of 3 prime number as 2+2+5.

I am trying to use variation of subset sum but number is too large to generate all primes number till then.

The problem is from the current HackerRank contest. The restrictions are 1 <= n, K <= 10^12

Upvotes: 2

Views: 3116

Answers (3)

Niklas B.
Niklas B.

Reputation: 95318

For K = 1, the answer is obviously "Yes" iif N is prime

For K = 2, according to the Goldbach conjecture, which is verified for N up to around 10^18, the answer is "Yes" iif N is even and N >= 4 or if N - 2 is prime.

The interesting case is K = 3. Obviously if N < 6, the answer is "No" because the smallest number expressible as the sum of three primes is 2 + 2 + 2 = 6. If N >= 6, then either N - 2 or N - 3 is even and >= 4, so we can apply Goldbach's conjecture again.

So for K = 3, the answer is "Yes" simply iif N >= 6.

Via induction (hint: just use K - 3 times the prime 2), we can show that for K >= 3, the answer is "Yes" iif N >= 2*K, so only the cases K = 1 and K = 2 are non-trivial and require just a simple primality check, e.g. via Miller–Rabin in O(log^4 N).

EDIT: As a bonus, this proof also gives a constructive algorithm to output the partition. We use a number of 2's and maybe one 3 to get to K = 2. The tricky K = 2, N even case is not as hard as it looks: We know from computational verification of the Goldbach conjecture that for N >= 12, there is a Goldbach partition with a prime < 5200 or so. There are less than 700 such primes, so we can check them all in a reasonable amount of time.

Upvotes: 6

Brainless
Brainless

Reputation: 1758

Your input are n and K. There are many cases :

  1. K > n : impossible
  2. K = n : the K prime numbers are all 1
  3. K < n : 4 subcases :

a. n and K are odd

b. n is even, K is odd

c. n is odd, K is even

d. n and K are even

Case a: select any prime p < n and p > 2. The problem reduces to the same problem with input n-p and K-1 instead of n and K respectively, and we fall in case b

Case b: The problem reduces to the same problem with input n-2 and K-1 instead of n and K respectively, and we fall in case d

Case c: idem than b, but we fall in case a instead of d

Case d: if n = 2K, then 2, 2, ..., 2 taken K times is your solution (ie your primes are 2, 2, ..., 2). Otherwise n can be written

n = (\sum_{i=1}^{i=K-2} 2 ) + p + q

where we add the prime 2 (K-2) times in the sum. Then the problem reduces to the same problem with input n-2(K-2) instead of n and 2 instead of K. But this is Goldbach. You can solve it in O(n sqrt(n)) like this : take p and q both equal to n/2. Increment p and decrease q by 1 at each step until they are both prime.

Upvotes: 0

user448810
user448810

Reputation: 17866

The concept you are looking for is called the prime partitions of a number. The formula to compute the number of prime partitions of a number is \kappa(n) = \frac{1}{n}\left(\mathrm{sopf}(n) + \sum_{j=1}^{n-1} \mathrm{sopf}(j) \cdot \kappa(n-j)\right); I gave that in LaTeX notation because I don't know how to do it in html. The sopf(n) function is the sum of the distinct prime factors of n, so sopf(42) = 12, since 42 = 2 * 3 * 7, but sopf(12) = 5, since 12 = 2 * 2 * 3 but each prime factor is counted once.

I discuss this formula at my blog.

Upvotes: 0

Related Questions