prac64's blog

By prac64, history, 6 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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+...

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yas, If coefficent is equal to 1 and half is prime you just need to discard that number. That can be checked easily.