# PROBLEM LINK:

Practice

Contest

**Author:** Kaushik Iska

**Tester:** Hiroto Sekido

**Editorialist:** Anton Lunyov

# DIFFICULTY:

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

asked
**15 Apr '13, 15:00**

6★anton_lunyov ♦

6.6k●62●119●138

accept rate:
12%