SPOJ.com - Problem SUMPRIM1

SUMPRIM1 - Sum of primes

no tags

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!

hide comments

< Previous 1 2 Next >

	veteran_01: 2021-02-11 08:52:47 we cannot use python here =(Francky)=> It's harder, but possible ! It was designed so. Last edit: 2021-02-26 14:50:04
	mahmud2690: 2018-05-04 10:15:40 Learned how to make code pretty ugly due to source limit) =(Francky)=> There's ways to write less verbose code. Last edit: 2018-05-04 11:43:01
	aliosm: 2018-04-29 10:43:15 Any hint in how to start to solve this problem? =(Francky)=> No hint here (see notes below) ; happy solving. Last edit: 2018-05-02 12:00:49
	dp_v1: 2016-04-15 15:10:22 @Francky, why i am getting internal error. someone please help... =(Francky)=> Judge don't give any info about "Internal error" reason. I don't know why psinfo for your submission is empty... Your code is extremely slow, even for very small input... Last edit: 2016-04-15 16:05:05
	weathervane: 2015-08-15 19:04:04 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? =(Francky)=> There's about 30 input files, and for each one one single input number. Just focus on one input number. Your program need to read only one number, and write only one answer. 2s is for each input file. The AC solvers are given the total time, that can reach near 30×2s = 60s at max. Good luck. Last edit: 2015-08-16 12:45:31
	sivanatarajan: 2014-10-17 17:57:29 I got time limit exceeded in 30th test case :-( --ans(Francky)--> You have TLE on all cases, only this one is shown as TLE, but all are. Sorry. Last edit: 2014-10-18 00:01:49
	mehmetin: 2014-07-21 10:18:11 Simple segmented sieve takes ~9 seconds to run for 2x10^9, on my machine... Last edit: 2014-07-21 10:24:50
	Francky: 2014-06-10 11:22:51 Congratulations to Min_25 as the first solver with a slow language, and as solver in the way the problem was designed for.
	Viplov Jain: 2014-06-02 12:53:55 @francky why put a size limit? --ans(Francky)--> The goal is to do it <b>without</b> any precomputed values. With many of them, the problem is killed. --(viplov) cant it be increased it a little ,say to ~1500b --ans(Francky)--> No, and in fact I think the actual limit is a bit too high ; 750 would have been the best imho. But it's too late, we don't like changes after publication, when possible. --(viplov) ok ,i understand the precomputation thing ... it does spoil the problem Last edit: 2014-06-10 15:35:15
	[Lakshman]: 2014-05-03 20:11:09 @francky am I getting WA for 210^9? --ans(Francky)--> Here again, it is very easy to make the reverse task, at least until 10⁸ (but it should be enough), and build own test cases in order to debug the code. Good luck ;-) Last edit: 2014-05-03 21:16:33*

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