Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Sukarna_Paul's blog

By Sukarna_Paul, history, 5 months ago, In English,

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.