PROBLEM LINK:Author: Kaushik Iska DIFFICULTY:SIMPLE PREREQUISITES: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 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 pseudocode could be used:
Let To fill the array
ALTERNATIVE SOLUTION:The low limit on N allows to use the following dirty trick. Let's find array The most easiest and straightforward way to perform this hack is the following:
where
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be provided soon. RELATED PROBLEMS:
This question is marked "community wiki".
asked 15 Apr '13, 15:00

My approach is as follows: From Link to Solution: http://www.codechef.com/viewplaintext/1977659 answered 15 Apr '13, 16:38
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)

As per the original question, an even number can never be represented as the sum of an even subprime(2q) and an odd prime(p). Then why don't we print "0" straight away for the query of each even number?
link
This answer is marked "community wiki".
answered 24 Oct '17, 11:57
