rt,写了欧拉筛预处理，但和没写用时一毛一样。
写之前：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int factor[1000005],tot=1,maxx=0;
int gcd(__int128 a,__int128 b){return (b?gcd(b,a%b):a);}
int qpow(int a,int b,int m)
	{
	int x=1,y=a;
	while(b){if(b&1)x=x*y%m;y=y*y%m;b>>=1;}
	return x;
	}
int ac(int a,int n)
	{
	int u=n-1,t=0;
	while(!(u&1)){u>>=1;t++;}
	int x1=qpow(a,u,n),x2;
	for(int i=1;i<=t;i++)
		{
		x2=qpow(x1,2,n);
		if(x2==1&&x1!=1&&x1!=n-1)return 1;
		x1=x2;
		}
	return (x1!=1);
	}
int ml(int n,int s)
	{
	if(n<2)return 0;
	if(n==2)return 1;
	if(!(n&1))return 0;
	for(int i=0;i<min(n,s);i++)
		{
		int a=rand()%(n-1)+1;
		if(ac(a,n))return 0;
		}
	return 1;
	}
int pr(__int128 n)
	{
	__int128 i=1,k=2,c=rand()%(n-1)+1;
	__int128 x=rand()%n,y;y=x;
	while(1)
		{
		i++;
		x=(x*x+c)%n;
		int d=gcd(y>x?y-x:x-y,n);
		if(d!=1&&d!=n)return d;
		if(x==y)return n;
		if(i==k){y=x;k<<=1;}
		}
	}
void f(int n)
	{
	if(ml(n,3)){tot++;maxx=max(maxx,n);return;}
	int p=n;
	while(p==n)p=pr(p);
	f(p);f(n/p);
	}
signed main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	srand(time(0));
	int t;cin>>t;
	while(t--)
		{
		int n;cin>>n;tot=1;maxx=0;
		f(n);
		if(tot==2)cout<<"Prime\n";
		else cout<<maxx<<'\n';
		}
	return 0;
	}

寄录

写了欧拉筛之后：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3000000;
int is_prim[N+5]={0},tot=1,maxx=0,cnt=0,prim[N+5];
__int128 gcd(__int128 a,__int128 b){return (b?gcd(b,a%b):a);}
int qpow(int a,int b,int m)
	{
	int x=1,y=a;
	while(b){if(b&1)x=x*y%m;y=y*y%m;b>>=1;}
	return x;
	}
int ac(int a,int n)
	{
	int u=n-1,t=0;
	while(!(u&1)){u>>=1;t++;}
	int x1=qpow(a,u,n),x2;
	for(int i=1;i<=t;i++)
		{
		x2=qpow(x1,2,n);
		if(x2==1&&x1!=1&&x1!=n-1)return 1;
		x1=x2;
		}
	return (x1!=1);
	}
int ml(int n,int s)
	{
	if(n<=N)
	    {
	    return !is_prim[n];
	    }
	if(n<2)return 0;
	if(n==2)return 1;
	if(!(n&1))return 0;
	for(int i=0;i<min(n,s);i++)
		{
		int a=rand()%(n-1)+1;
		if(ac(a,n))return 0;
		}
	return 1;
	}
int pr(__int128 n)
	{
	__int128 i=1,k=2,c=rand()%(n-1)+1;
	__int128 x=rand()%n,y;y=x;
	while(1)
		{
		i++;
		x=(x*x+c)%n;
		int d=gcd(y>x?y-x:x-y,n);
		if(d!=1&&d!=n)return d;
		if(x==y)return n;
		if(i==k){y=x;k<<=1;}
		}
	}
void f(int n)
	{
	if(ml(n,3)){tot++;maxx=max(maxx,n);return;}
	int p=n;
	while(p==n)p=pr(p);
	f(p);f(n/p);
	}
void init()
    {
    for(int i=2;i<=N;i++)
        {
        if(!is_prim[i]){prim[++cnt]=i;}
        for(int j=1;j<=cnt&&i*prim[j]<=N;j++)
            {
            is_prim[i*prim[j]]=1;
            if(i%prim[j]==0)break;
            }
        }
    }
signed main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	srand(time(0));
	int t;cin>>t;
	init();
	while(t--)
		{
		int n;cin>>n;tot=1;maxx=0;
		f(n);
		if(tot==2)cout<<"Prime\n";
		else cout<<maxx<<'\n';
		}
	return 0;
	}

寄录2

有dalao知道为什么吗？玄关qwq