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
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/23/2024 03:03:09 (h1).
Desktop version, switch to mobile version.
Supported by
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.