Hackerrank has recently launched a very nice type of contests. The weekly contest takes place every week and lasts 7 days. Every day a new problem is posted and the difficulty of problems increases each day. The 3rd edition has begun on Monday.
While first two problems were pretty straightforward, Wednesday's problem requires some theoretic background and a little bit of analysis.
You're given N and K, both positive and less or equal . You have to decide if N can be written as a sum of exactly K prime numbers. In addition, one test file contains at most 5000 testcases, so you have to solve one quite fast.
The full problem statement is here: https://www.hackerrank.com/contests/w3/challenges/prime-sum. I encourage you to solve it.
The first observation is that if , then the answer is YES if and only if N is prime. In addition, if the answer is NO.
The second observation is that for every N, the maximum valid K is . If N is even, then you can write N as a sum of twos. If N is odd, then you can write N as a sum of 3 and twos. You cannot take a greater K, because the smallest prime is 2.
From now, we can assume that and .
The next crucial step is to use the Goldbach's conjecture. It says that every even can be written as a sum of exactly 2 prime numbers. While this hasn't been proven yet and remains as one of the oldest and best-known unsolved problems in number theory, it is confirmed for by a distributed computer program.
We can use that fact to solve the problem.
If N is even, let's write it as a sum of twos. We can take any of these twos and replace them by two primes because is even and because of the conjecture, so the answer is YES.
If N is odd, let's write it as a sum of 3 and twos. We can take any twos and replace them by two primes using the same rule as above. It follows that the answer is YES for . But what if ? We know then, that one of the primes has to be 2 because we cannot have two odd primes, so the answer is YES if and only if is prime.
The last remaining thing is how to decide fast if N is prime. Since a standard sieve or trying to divide N by numbers less or equal is too slow. We can use Miller–Rabin primality test.
It is a randomized algorithm in general, but since we can make it deterministic.
I really like that problem.