SUMPRIM1 - Sum of primes
Léo had been defeated by XerK at the battle of the ThermoPell. 300 braves fell ; XerK as a living God decided to allow a new honor table, for those who can use less than 900 characters in his new problem. This problem is extremely simple, but you have to be extremely fast.
The lonely line of input contains an integer N.
You have to print the sum of all primes up to N.
The first sum is
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77
0 < N <= 2×10^9
The classical problem SUMPRIM2 is the reverse task. Time limit allows some slow languages to finish in time, it could be hard. For your information, my 690-Byte C code need a total time of 0.76s for the 30 input files, 22.82s for my Python one. (Edit 12/II/2017, after compiler update). Warning : You have 900B as code size limit. ;-) Have fun.
Learned how to make code pretty ugly due to source limit)
Any hint in how to start to solve this problem?
I am confused by the question's requirements. It states there will be one input case, but the author talks about 30 input cases. It also gives a time limit of 2.0 seconds, yet answers have been accepted with much larger time than that. Correct answers are awarded a score. Where is that mentioned in the question?
I got time limit exceeded in 30th test case :-(
Simple segmented sieve takes ~9 seconds to run for 2x10^9, on my machine...Last edit: 2014-07-21 10:24:50
Congratulations to Min_25 as the first solver with a slow language, and as solver in the way the problem was designed for.
@francky why put a size limit?
@francky am I getting WA for 2*10^9?
Problem fixed : I feel really stupid. For MasterJudge, you have to select an extension (.C++ for most masterjudge), if not you have silently 'internal error' for each submission. I saw this 'thing' but simply ignore it, as I thought all masterJudges were (.C++).