思路是质数筛，但是

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int n = 1E8, m = 577E4;
int T;
int Prt[n + 10], Prime[m], sum;
void Pre(){
	for(int i = 2; i <= n; ++ i){
		if(not Prt[i]){
			Prime[++ sum] = i;
		} for(int L = 1; L <= sum && Prime[L] * i <= n; ++ L){
			Prt[Prime[L] * i] = Prime[L];
			if(i % Prime[L] == 0){
				break;
			}
		}
	}
}
signed main(){
	scanf("%lld", &T);
	while(T --){
		int N;
		scanf("%lld", &N);
		int ans = 0;
		if(Prt[N] == 0){
			printf("%lld\n", N);
			continue;
		} while(1){
			int P = Prt[N];
			if(P == 0){
				ans xor_eq N;
				break;
			}
			ans xor_eq P;
			N = N / P;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

感谢