C(clang11) 解法, 执行用时: 135ms, 内存消耗: 348K, 提交时间: 2021-02-04 14:15:17

#include<stdio.h>
int main()
{
    long long int t,k,p,res,f,i,j;
    scanf("%lld",&t);
    for(k=1;k<=t;k++)
    {
    	scanf("%lld",&p);
    	res=1;
    	for(i=1;;i++)
    	{
    		res=(res*i)%p;
    		if(res==0)
    		{
    			printf("%d\n",i);
    			break;
			}
			f=1;
			for(j=2;j*j<=p/i;j++)
			{
				if((p/i)%j==0)
				{
					f=0;
					break;
				}
			}
			if(p%i==0&&p/i>i&&f==1)
			{
				printf("%d\n",p/i);
    			break;
			}
		}
	}
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 129ms, 内存消耗: 632K, 提交时间: 2020-05-01 23:32:53

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n, t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		int ans = 0;
		for (int i = 2; i*i <= n; i++)
		{
			int sum = 0, temp = 0;
			while (n%i == 0)
			{
				sum++;
				n /= i;
			}
			for (int j = 1; j <= sum; j++)
			{
				if (j%i == 0)
				{
					temp++;
					sum -= temp;
				}
				ans = max(j*i, ans);
			}
		}
		ans = max(n, ans);
		cout << ans << endl;
	}
}

C++(clang++11) 解法, 执行用时: 242ms, 内存消耗: 408K, 提交时间: 2021-02-04 12:27:16

#include <bits/stdc++.h>
using namespace std;
int judge(int p)
{
	for(int i=2;i*i<=p;i++){
		if(p%i==0){
			return 0;
		}
	}
	return 1;
}
int main()
{
	int T;
	cin>>T;
	int p;
	while(T--){
		cin>>p;
		for(int i=1;;i++){
			p/=__gcd(i,p);
			if(p==1){
				cout<<i<<endl;
				break;
			}
			if(judge(p)&&i<p){
				cout<<p<<endl;
				break;
			}
		}
	}
	return 0;
}