最小质因数之和

欧拉筛，spf数组记录每个数字的最小质因子，sum前缀和数组，最后实现$O(1)$ 查询，代码实现如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
#define endl '\n'
#define int long long
#define inf 0x3f3f3f3f
const int N=1e6+9;
int n,primes[N],spf[N],sum[N];//前缀和数组
bitset<N>pri;
void EUler(){
	int pp=0;
	pri[0]=pri[1]=1;
	for(int i=2;i<=N;i++){
		if(!pri[i]) primes[++pp]=i,spf[i]=i;
		for(int j=1;j<=pp&&primes[j]*i<=N;j++){
			pri[primes[j]*i]=1;
			spf[primes[j]*i]=primes[j];
			if(i%primes[j]==0){
				break;
			}
		}
	}
	for(int i=2;i<=N;i++){
		sum[i]=sum[i-1]+spf[i];
	}
}
void solve(){
	cin>>n;
	cout<<sum[n]<<endl;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ ;
	cin>>_;
	EUler();
	while(_--){
		solve();
	} 
    return 0;
}