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
My code is working fine on codeblocks but gives SIGSEGV error, here on spoj. HELP!!
Precompute using Prime Sieve and O(1) retrieval B| TLE->TLE->WA->AC
why is it showing run time error???
got accepted using sieve and noting down the first prime divisor for each number inside sieve function...nice question though :DLast edit: 2016-05-16 19:08:26
Ray Brish Bhanu:
learned diff b/w declaring an array locally and globally
good problem to learn application of sieve.Precomputation is necessary i think
worked even with long long int!!
easy one! my half century complete..................!!!!!!
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... :)