APS.cpp

#include<iostream>
using namespace std;

typedef unsigned long long ll;
const ll MAX = 10000003;

ll a[MAX];  // Đánh dấu số i là số nguyên tố hay không
ll r[MAX];  // Lưu kết quả    

void create()
{
    // Khởi tạo số nguyên tố đánh dấu là 0
	for(ll i = 2; i < MAX; i++) 
	{
		a[i] = 0;
		r[i] = 0;
	}

    // Sinh ra dãy số theo quy luật:
    // nếu a[i] là số nguyên tố thì a[k.i] không phải số nguyên tố 
    // và thừa số nguyên tố lớn nhất của k.i là i
	for (ll i = 2; i*i < MAX; i++)
        if (!a[i])
            for (ll j = i; j < MAX; j += i)
                if (!a[j])
                    a[j] = i;

    // Nếu a[i] khác 0 thì i là không là số nguyên tố và thừa số nguyên tố
    // lớn nhất của i là a[i]
    // ngược lại thì i là số nguyên tố và thừa số lớn nhất của i là i
    for (ll i = 2; i < MAX; i++)
	{
		if(a[i]) r[i] = r[i - 1] + a[i];
		else r[i] = r[i - 1] + i;
	}
}

int main()
{
	create();

	ll T = 0;
	cin >> T;
	for(ll tc = 0; tc < T; tc++)
	{
		ll n = 0;
		cin >> n;
		cout << r[n] << endl;
	}
	return 0;
}