PROBLEM LINK:Setter: Misha Chorniy DIFFICULTY:Easy PREREQUISITES:Prime Sieve, or even Square root factorization would suffix, Precomputation. Numbertheory (optional). PROBLEM:Answer the queries of form, Given a number $N$, can this number be represented as sum of two semiprimes. Semiprime is a product of any two distinct prime numbers. SUPER QUICK EXPLANATION
EXPLANATIONFor this problem, I am explaining two solutions, Common approach as used by Setter and Tester as well as most teams. The other one is quite an overkill, strange way to solve this problem, used by editorialist only. :D Setter/Tester Approach Calculate all the primes in range $[2,MXN]$. This can be done using Sieve of Eratosthenes or we can just naively check each number whether it is a prime or not. For those unaware of Sieve of Eratosthenes, Enter the secret box. Now that we have the list of primes in an array, say $pr$. Now, we need to find the list fo semiprimes. we can iterate over all pairs of Distinct primes take their product and the values in range $[1, MXN]$ are marked as semiprime. So, now we have the list of semiprimes in range$[1, MXN]$. Now, Computing final answer is just doing once again, Iterating over all pairs of semiprimes and if their sum is in range $[1, MXN]$, mark the sum as reachable. Answering queries become simple, as we just need to print whether the sum $N$ is marked reachable or not. Editorialist's Approach (Not recommended at all :P ) This solution differs from above solution at the computation of list of semiprimes. Give a try to compute list of semiprimes without computing primes. It relies on the formula of Number of factors of a number. The observation is, that all semiprimes have exactly four factors. (can also be proved eaisly) But, all numbers having four factors are of two types. Both semiprimes and perfect cubes will always have 4 factors. So, we iterate over all numbers, check if it has exactly four factors (including trivial factors) and is not perfect cube. If any number satisfy both criteria, it is marked as semiprime. After that, this solution is same as Author/Tester solution. Time ComplexityBoth Solutions have precomputation time $O(MXN^2)$ for iterating over all pairs of semiprimes, which dominates everything. For a fact, Sieve of Eratosthenes takes $O(N*log(logN))$ time while Square root factorization takes $O(N*\sqrt{N})$ time. Queries are answered in $O(1)$ time, taking overall $O(T)$ time. SO, overall complexity is $O(MXN^2)$. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Oct '18, 14:25

Why my solution is flagged as wrong answer?I have checked for 200 input and it works on codechef practice compiler.link of my solution. Logic used: Every semiprime number Has exactly two distinct prime factor and used 'count' variable to count it. Also used 'cnt' variable to take care of repeated prime factor. answered 18 Oct '18, 13:32

I solved this with a modified seive. We can calculate the semiprimes in the seive function itself and later simply iterate till N/2th number to check for semiprimes. Time complexity: 0(N loglogN + N). Have a look : https://www.codechef.com/viewsolution/20952615 answered 18 Oct '18, 14:17
