Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

prac64's blog

By prac64, history, 5 months ago, ,

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 !!

•
• +8
•

 » 5 months ago, # |   +8 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.
•  » » 5 months ago, # ^ |   0 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
•  » » » 5 months ago, # ^ |   0 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+...
•  » » » » 5 months ago, # ^ |   0 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 ?
•  » » » » » 5 months ago, # ^ |   0 Yas, If coefficent is equal to 1 and half is prime you just need to discard that number. That can be checked easily.