# LEVY - Editorial

Author: Kaushik Iska
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

SIMPLE

### PREREQUISITES:

Sieve of Eratosthenes

### PROBLEM:

For the given positive integer n ≤ N := 10000 you need to find the number of pairs (p, q) such that p + 2 * q = n and p, q are both primes. You should be able to answer up to 100000 test cases in a second.

### QUICK EXPLANATION:

The following solution works fine even when N = 400000. At first let’s find all prime numbers up to N using sieve of Eratosthenes. Then we fill array `cnt[]` of size N such that `cnt[n]` denotes the number of required pairs of primes for n. Initially it is filled by zeros. Then we iterate over pairs of primes (p, q) in a simple double loop over array of found primes and increase `cnt[p + 2 * q]` by 1 for each such pair. Moreover, if p + 2 * q > N we break from the inner cycle over q. Clearly after this double loop array `cnt[]` will be filled correctly. So after such precomputation we can answer each query in O(1) time. The complexity of such approach is O(N * log log N + (N / log N)2 + T). Here N * log log N is the complexity of sieve and N / log N is a approximate number of primes up to N.

Some contestants were curious about the case of even n. Let n = 2 * k. Then from p + 2 * q = n we have p = 2 * (k − q). So p is even prime and hence equal to 2. Then q = k − 1. So for even n answer is 1 if n/2 − 1 is prime and 0 otherwise.

### EXPLANATION:

Here we discuss implementation details of the above solution.

To find all primes the following pseudo-code could be used:

``````for p = 1 to N do
isPrime[p] = true
for p = 2 to N do
if isPrime[p] then
add p to the list of primes
for n = p * p to N with step p do
isPrime[n] = false
``````

Let `primes` denotes the list of found primes.

To fill the array `cnt[]` the following pseudo-code could be used

``````for n = 1 to N do
cnt[n] = 0
for p in primes do
for q in primes do
if (p + 2 * q > N) then break
increase cnt[p + 2 * q] by 1
``````

### ALTERNATIVE SOLUTION:

The low limit on N allows to use the following dirty trick. Let’s find array `cnt[]` using any algorithm that possibly could get TLE and print it to some file as a comma separated list of integers. Then copy this list to the program as an initialization of the actual array `cnt[]`. Now the program is ready to answer each query in O(1) time. Note also that source limit for this problem is 50000 bytes. So your program should not exceed 50000 characters. But since N is only 10000, hack with initialization of `cnt[]` would cost only about 26Kb of code which is far from the limit.

The most easiest and straightforward way to perform this hack is the following:

``````for n = 1 to N do
cnt = 0
for q = 1 to n/2 do
p = n - 2 * q
if (isPrime(p) and isPrime(q)) then
cnt = cnt + 1
print cnt, ","
``````

where `isPrime(n)` returns whether n is prime and could implemented as follows:

``````isPrime(n)
if n < 2 return false
for d = 2 to sqrt(n) do
if (n mod d = 0) return false
return true
``````

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be provided soon.
Tester’s solution can be found here.

### RELATED PROBLEMS:

UVA - 543 - Goldbach’s Conjecture

2 Likes

My approach is as follows: From `N = p + 2q`, we get `p = N-2q`; Once we have a list of primes (obtained by sieving), loop through the list of primes (using `q`). For each such `q`, check whether `p` (= `N-2q`) is also prime.