SPOJ.com - Problem SUMPRIM1

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.

Input

The lonely line of input contains an integer N.

Output

You have to print the sum of all primes up to N.

Examples

Input_1:
19

Output_1:
77

Input_2:
1000000000

Output_2:
24739512092254535

Explanation

The first sum is

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77

Constraints

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.

Submit solution!

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

hide comments

2014-03-24 00:17:26 Francky
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++).
Now the problem is as a speed-challenge ; it was intended for, all submissions needed to be rejudged. Done.
Have fun with this configuration.

2014-03-24 00:05:20 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†)
Yes, I deleted my previous message, I think you haven't see it (deleted ~5 min after I post it).. I delete it because I know (very supicious) that there must be better complexity, so I change my mind, cancel my request, delete it.. but you very fast (Or I very slow) :-P and you've seen my comment before I deleted it :-O haha, nevermind ;-)
Btw, thanks for your answer..

Last edit: 2014-03-18 14:50:44

2014-03-24 00:05:20 Francky
I don't want to spoil, but the awaited correct complexity here is different, it is although possible to solve it with 'conventional' method. Done in 222B of Py3 or 690B of C for me, without golfing. For now, only Min_25 solved the problem in the way it was designed for. I've set the time 'relax' to allow Python submissions, but time limit would have been much lower. In fact I would like this problem as a speed challenge ; maybe possible in near future. I don't think a tutorial edition is needed ; you have the excellent PRINT, possibly helpful for conventional method optimization, and really very hard in Py2.7 ;-) . I can think too at a more serious edition where only fast languages could be able to get AC in time, with the good method, without constant optis.
edit: this post was an answer to a (deleted?) message.

Last edit: 2014-03-18 13:42:07

2014-03-24 00:05:20 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†)
Again, I'm not smart enough to enjoy your very good problem..

Btw, about master judge, could you make a new empty problem, and set me as co-author? maybe I can do some experiment about master judge on your problem.. (first, I'll try to implement BFK_AUTO masterjudge on your problem)
--ans(Francky)--> Thanks for your help. With Mitch we ever tried that. Chess. Even with exact copy of 1000/masterjudge/spoj/official/verywell/zeromodif. If Mitch upload no problem, if I upload the same file, it led to 'internal error'...
For the problem, I'm sure you'll find how to do the job in time ;-). I agree that it can surprise many people. It was intended for. Best regards speedy Tjandra.

Last edit: 2014-03-10 14:53:49

2014-03-24 00:05:20 [Lakshman]
@Min_25 amazing speed .
my 10^8 is taking .26s on ideone don't know how to compute 2*10^9 primes ,************ sniped ***********?.
--ans(francky)--> First congrats to Min_25. Please do not spoil in comment.

Last edit: 2014-03-10 08:17:23

2014-03-24 00:05:20 Francky
Congratulations to Robert Gerbicz as the first solver.
But, time is too relax, I would this problem in challenge section with time as score. Anybody knows how to do it simply?

(Mitch) Email sent regarding judge. :)

(Francky)--> Try done when tuning master-judge (just for the score), but I got again 'internal error' ; I ever tried a long time ago ; I can't never use my own master judge !! Very curious !! Thanks again for your infos.

Last edit: 2014-03-09 23:56:21