## APS Statement

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.

## APS Solution

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <bits/stdc++.h> using namespace std; const int me = 10000025; int t, n; long long f[me]; int main() { ios_base::sync_with_stdio(false); cin.tie(false); for(int i = 2; i < me; i ++) if(!f[i]) for(int j = i; j < me; j += i){ if(!f[j]) f[j] = i; } for(int i = 1; i < me; i ++) f[i] += f[i - 1]; cin >> t; while(t --){ cin >> n; cout << f[n] << endl; } return 0; } |

**You also like to see:**