SUMPRIM2  Sum of primes (reverse mode)
XerK had prepared his new problem with some sums of primes up to some bounds.
His results are well here, but he forgot the bounds.
Your task is to find which was the last prime in the sum.
This problem is extremely simple, but you have to be extremely fast.
Input
The lonely line of input contains an integer S.
Output
You have to print the last prime P such that sum(prime from 2 to P) = S.
Examples
Input_1: 77
Output_1: 19
Input_2: 24739512092254535
Output_2: 999999937
Explanation
The first sum was
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77
Constraints
0 < P <= 10^12
The challenge problem SUMPRIM1 is the reverse task.
Time limit is set to allow some slow languages to finish in time, it could be hard.
For your information, there's a total of 20 input files.
;) Have fun.
You may try before an excellent tutorial problem (Twin Primes) and make some speed experiments.
You could take benefit too in working with PRINT, another excellent tutorial problem.
hide comments
[Lakshman]:
20180226 19:48:17
@Francky what is the expected complexity is it $O(\ sqrt(P) \ log P)$


XeRoN!X:
20150315 01:13:02
What's the limit on S. WIll it fit in long long ?


ivar.raknahs:
20140503 17:20:11
@ franckyIs the value of s always prime?

Added by:  Francky 
Date:  20140309 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 