SPOJ.com - Problem APS

APS - Amazing Prime Sequence

#number-theory

Bablu is very fond of Series and Sequences...

After studying Fibonacci Series in Class IX, he was impressed and he designed his own sequence as follows...

a[0] = a[1] = 0

For n > 1, a[n] = a[n - 1] + f(n), where f(n) is smallest prime factor of n.

He is also very fond of programming and thus made a small program to find a[n], but since he is in Class IX, he is not very good at programming. So, he asks you for help. Your task is to find a[n] for the above sequence....

Input

Your code will be checked for multiple Test Cases.

First Line of Input contains T (<= 100), the number of Test Cases.

Next T lines contain a single number N. (1 < N < 10^7).

Output

Single line containing a[n] i.e. nth number of the sequence for each test case.

Example

Input:
3
2
3
4

Output:
2
5
7

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 Next >

	The_ROCK: 2013-12-29 08:22:04 @Karan Dev : Its because for high values your recursive function eats up all the stack memory. For more details on how recursion works, visit http://en.wikipedia.org/wiki/Stack_overflow
	karan_dev: 2013-08-15 10:36:57 my code works for n=10000, but not for , n=100000 or above. I checked 'smallest prime' function, it is working good for n=100000 or above. help.
	Bhagwat: 2013-06-04 02:48:31 nice problem..:)
	Abhishek Mishra: 2013-04-25 11:08:27 should be moved to the tutorial section...
	Eduardo Nunes: 2013-04-18 21:56:31 nice one :-D
	johri: 2013-02-19 09:25:25 Amazing ..:))
	Aditya Pande: 2013-02-17 04:58:46 i guess the test cases are randomly generated. The supposedly faster code working slowly...?
	chicku: 2013-02-16 21:34:27 @abdelkarim ya man did it before the question was there on spoj
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-02-15 20:15:28 @Ehor Nechiporenko: Your memory usage give me more idea to optimize my solution ;-) Thanks, haha...
	Alex Anderson: 2013-02-15 16:15:36 The number 11,000,000 was in the input, but it seems to have been fixed now. EDIT: Or not. I'm not sure what's going on anymore then. My Java program gets a runtime error if I make my array size 1100000. But it gets AC if I make my array size 11000001. However, my C++ program gets AC if I make my array size 10000000, or even smaller. EDIT2: Ok, I think I see. I was getting runtime error because for some reason, sometimes my Java program will run on Pyramid, and it can't allocate that much memory, hence RE. Other times it will run on Cube (correctly) and that isn't an issue. Last edit: 2013-02-15 16:19:44

Submit solution!

Added by:	c[R]@zY f[R]0G
Date:	2013-02-14
Time limit:	1s
Source limit:	5000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64