数学、筛法、线性筛/欧拉筛

线性筛求出值域内每个数的最小质因数，分解 $i$ 时不断将 $i$ 除以其最小质因数。

预处理时间复杂度 $O(V)$，单次分解质因数时间复杂度 $O(\log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int lim=100000000;
int T,n,cnt,p[6000001],s[100000001];
bool on[100000001];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    on[0]=on[1]=1;
    for(int i=2;i<=lim;i++){
        if(!on[i]) p[++cnt]=s[i]=i;
        for(int j=1;j<=cnt&&i*p[j]<=lim;j++){
            on[i*p[j]]=1,s[i*p[j]]=p[j];
            if(i%p[j]==0) break;
        }
    }
    for(cin>>T;T!=0;T--){
        int ans=0;
        cin>>n;
        while(n!=1) ans^=s[n],n/=s[n];
        cout<<ans<<'\n';
    }
    return 0;
}