题解 | Problem C

#include<iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N=1000000010; 
bool vis[100010];
int prim[100010];
int cnt=0;
 
void get_prim(){
	for(int i=2;i<=sqrt(N);i++){
		if(!vis[i])prim[cnt++]=i;
		for(int j=0;j<cnt;j++){
			if(prim[j]*i>sqrt(N))break; 
			vis[i*prim[j]]=1;
			if(i%prim[j]==0)break;
		}
	}
//	for(int i=0;i<50;i++)cout<<prim[i]<<endl;
}







int main() {
    int n;
    cin >> n;
    get_prim();
    while (n--) {
        string s;
        cin >> s;
        long long num = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s[i] - '0');

            }
        }
        //      cout << num << endl;
        int len = 0,maxx =0;
        while(1&&num)
        {
            while(num%prim[len]==0)
            {
                maxx = prim[len];
                num/=prim[len];
            }
            len++;
            if(len>=cnt)
            {
                break;
            }
        }
        if(num!=1)cout<<num<<endl;
        else if(num==1)cout<<maxx<<endl;
        else cout<<0<<endl;
    }
}
// 64 位输出请用 printf("%lld")