sary's blog

Why doesn't it TLE?
By sary, history, 21 month(s) ago, In English

Hello everyone, I was solving this Problem 584D, and I thought I would get TLE but it passed, I know my solution(simply in most cases I have an even number then get the 2 primes that sum up to that even number), it's correct according to Goldbach's conjecture "any even number greater than 2 can be written as the sum of two prime numbers", but I don't know how much operations will it take to get those 2 primes that will sum up to X (for an even number X <= 1e9). My Submission. Why doesn't it give TLE? Thanks

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

»
21 month(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

correct me if i'm wrong here, but prime numbers are separated in O(log(N)) on the number line, meaning that you would need to iterate order of log(N) numbers to go from one prime to another, so you could find the biggest prime smaller than N, lets call it "p", subtract it from N, and now you only need to find two prime numbers between 2 and N — p that add up to N — p, since N — p is O(log(N)) it should be fine.

→ Reply