×

# 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

This question is marked "community wiki".

6.6k62119138
accept rate: 12%

 4 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. Link to Solution: http://www.codechef.com/viewplaintext/1977659 answered 15 Apr '13, 16:38 4.1k●5●23●64 accept rate: 14% 1 I used the same approach but the other way. (15 Apr '13, 16:43) I also thought the other way first. But to code, finding p given q, seemed to be easier than finding q given p (and I don't know why!!) :P (15 Apr '13, 16:49)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×11,590
×780
×206
×15
×2

question asked: 15 Apr '13, 15:00

question was seen: 5,814 times

last updated: 15 Apr '13, 16:49