I saw a question somewhere, which asked to find the number of distinct numbers which can be represented as sum of two distinct primes. T=10000,N=10000000, the question felt impossible, so after attempting for a while, I saw the editorial, the solution was incorrect and poorly written.
If we did not have distinctness constraint, we could use goldbach conjecture and also mark p+2 as true(where p is prime) in a sieve and find the ans, but here we want only distinct sum of distinct primes, above approach would include 4(2+2) in the answers, which is not okay.
Even though the question is probably not solvable for the given values(i.e. n=1e7), what would be your best algorithm for this problem. And upto what n could it solve the problem for ? (1e3? 1e4? 1e5 ? 1e6 ? 1e7?)
Is it possible to answer more queries ? (lets say the limit comes from space complexity, so we can answer more queries)
sample cases n=4 ans=0
n=5 ans=1 (5=2+3)
n=9 ans=4 (5=2+3,7=5+2,8=5+3,9=7+2) (6=3+3 is not valid because the primes are not distinct)
Thank you codeforces !!
I've checked all numbers up to 107 and 2, 4, 6 are the only even numbers that can't be represented as a sum of two distinct primes.
holy shit, really :O ?
btw how do you check ? do you have a fast PC ?
can you provide code, I can run it if it will take less than an hour
You can find all primes in the interval and than use FFT for calculating which sums we can get. Polynom for FFT should be: P(x)= x^2+x^3+x^5+x^7+...
so if coeffecient of some number is 1, and that number/2 is a prime, we know its an invalid sequence ?
like we calculate coeffecients of every power by FFT on (x^2+x^3+...)*(x^2+x^3+...), and then we will see that for x^4 the coeffecient is 1, and 4/2=2 is a prime, therefore that is the only one way, so discard 4 from solution space ?
Yas, If coefficent is equal to 1 and half is prime you just need to discard that number. That can be checked easily.