Tag Archives: MillerRabin

Hackerrank Weekly / Prime Sum

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.

Problem


You're given N and K, both positive and less or equal 10^{12}. 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.

Solution


The first observation is that if K = 1, then the answer is YES if and only if N is prime. In addition, if N = 1 the answer is NO.

The second observation is that for every N, the maximum valid K is \lfloor N / 2 \rfloor. If N is even, then you can write N as a sum of N / 2 twos. If N is odd, then you can write N as a sum of 3 and (N - 3) / 2 twos. You cannot take a greater K, because the smallest prime is 2.

From now, we can assume that N \geq 2 and 2 \leq K \leq \lfloor N / 2 \rfloor .

The next crucial step is to use the Goldbach's conjecture. It says that every even N > 2 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 N \leq 4 \cdot 10^{17} 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 N / 2 twos. We can take any 2 \leq m \leq N / 2 of these twos and replace them by two primes because m \cdot 2 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 (N - 3) / 2 twos. We can take any 2 \leq m \leq (N - 3) / 2 twos and replace them by two primes using the same rule as above. It follows that the answer is YES for 3 \leq K \leq N / 2. But what if K = 2 ? 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 N - 2 is prime.

The last remaining thing is how to decide fast if N is prime. Since N \leq 10^{12} a standard sieve or trying to divide N by numbers less or equal \sqrt N is too slow. We can use Miller–Rabin primality test.

It is a randomized algorithm in general, but since N \leq 10^{12} we can make it deterministic.

I really like that problem.