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 by working with PRINT, another excellent tutorial problem.


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

hide comments
2018-02-26 19:48:17 [Lakshman]
@Francky what is the expected complexity is it $O(\ sqrt(P) \ log P)$

=(Francky)=> No ! This is a tricky problem, and you have to figure how to manage constraints. The problem was designed to be solved with slow languages as well (but with hard opti in that case). Good luck, and have fun !

=(Lakshman)=> @Francky Can you please tell me if I can get AC with my approach. Complexity is somewhat O(p^(3/4) * log p^2)


Last edit: 2018-03-20 08:46:12
2015-03-15 01:13:02 XeRoN!X
What's the limit on S. WIll it fit in long long ?

(Francky) => I guess not, as you can see here.

Last edit: 2015-03-15 20:52:13
2014-05-03 17:20:11 ivar.raknahs
@ francky-Is the value of s always prime?
--ans(Francky)--> No, like S=77=7×11 in sample #1, nor #2 where S%5==0.

Last edit: 2014-05-03 17:43:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.