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 = a = 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....
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).
Single line containing a[n] i.e. nth number of the sequence for each test case.
Input: 3 2 3 4 Output: 2 5 7
AC In One Go. 18th.. :D dp
Awesome sieve+dp:) Ac in 3 go , dont forget to use long long answers are explosive:)
sieve+pre-computation gives :)
weak test cases
use long long int...very easy
Use long long. cost me 1 WA :)
Nice problem ..
Awesome optimisation problem.
And if you use 64 bit signed integers, remember to use "%lld" instead of "%d"......
My 50th On spoj