APS - Amazing Prime Sequence
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
hide comments
ashiq_iqbal:
2016-01-22 18:20:01
When will you mark the multiple of the primes...on that time you can store the prime of the multiples in the multiples... Hope it helps to avoid TLE... :) |
|
chandan kumar:
2016-01-21 06:27:53
Easy problem if you use the concept of sieve of Eratosthenes |
|
minhthai:
2016-01-15 17:51:14
nice for beginner like me :) |
|
bhavya16:
2015-11-11 10:30:51
Please help....my code is running fine in code blocks but in Spoj it is giving Compilation error and sometimes runtime error
|
|
saini428:
2015-08-26 21:48:34
easy problem,done using sieve,,,, |
|
[Mayank Pratap]:
2015-08-16 18:46:16
@dushyant ...no need of unsigned if using sieve |
|
anuveshkothari:
2015-08-11 14:06:22
not reading @dushyant comment costed me 1 WA Last edit: 2015-08-11 14:09:50 |
|
Satyam Mishra:
2015-07-30 22:53:33
ACed..
|
|
Dushyant Singh:
2015-07-30 09:49:31
Those who are getting WA change everything to unsigned long long, same for those who are getting TLE. :-) |
|
ANIKET:
2015-07-25 05:28:56
rojers's algorithms rocks......ac in 1/2 go...... only one line code :P :) |
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 |