How can I approach for this problem ? https://codeforces.com/gym/102055/problem/L

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 189 |

2 | Errichto | 188 |

3 | tourist | 180 |

4 | Radewoosh | 173 |

5 | vovuh | 166 |

6 | pikmike | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 160 |

9 | rng_58 | 155 |

10 | farmersrice | 152 |

How can I approach for this problem ? https://codeforces.com/gym/102055/problem/L

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/26/2020 00:45:33 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If $$$n \leq 11$$$ then answer is obviously -1. Otherwise, if $$$n$$$ is odd, then write first four primes as $$$2,2,2,3$$$ and show $$$n-9$$$ as sum of two primes. If $$$n$$$ is even, choose first four as $$$2,2,2,2$$$ and write $$$n-8$$$ as sum of two primes. It is always possible* because of Goldbach conjecture.

*Well, at least for such small numbers.

But how will you find two prime numbers such that their sum is n (even) as the range for n is too high.

my solution: calculate all primes $$$< 100$$$ then calculate all $$$5$$$ tuples of those primes and add them to a map (sum of those primes to used primes). Now for each input number just try if $$$n-x$$$ is prime and $$$x$$$ is in the map. If you found a valid $$$x$$$ then $$$n-x$$$ and the $$$5$$$ other primes are the result, if no valid $$$x$$$ is there (propably) is no solution.

As TooNewbie pointed out before, first you can conclude that the answer always exists. In fact, a very similar argument can lead you to conclude that any number greater than 9 can be written as the sum of 5 prime numbers. Now, you aren't required to find some particular combination and that's the key. So, something which is good to know is that the prime gap is usually not that big (it's less than 2000 for very large numbers) and then, you can easily iterate over all the numbers between $$$[n - 2010, n - 10]$$$ and find a suitable prime in this range. Say that $$$p$$$ is this prime, then given that $$$10 \leq n - p \leq 2010$$$, you can also easily find the other 5 primes.

How can you test if such large numbers (10^12) are prime? Looping over all primes < 10^6 seems like it would take too long.

Miller Rabin Primality Test

You can certainly use Miller Rabin or some probabilistic algortihm. Also, you can notice that the number of primes less than n is around $$$\frac{n}{logn}$$$. So, up to $$$10^6$$$, there are ~$$$10^5$$$ primes and therefore, the complexity for this iteration will be $$$10^5*2000 = 2*10^8$$$ (if you only test with the precomputed primes), which is usually fast enough.

Ok, but my implementation is getting TLE :(

link : https://pastebin.com/jnDMVA0Z

I implemented what I explained you before here and it's getting accepted.