• Source 
    1. #include <iostream>
    2. #include <cmath>
    3. #include <vector>
    4. using namespace std;
    5. bool checkPrime(long long x)
    6. {
    7. 	for(long long i=2;i<=ceil(sqrt((double)x));++i)
    8. 		if(x%i==0)
    9. 			return false;
    10. 	return true;
    11. }
    12. const int N=1000008;
    13. bool mark[N+100];
    14. int main()
    15. {
    16. 	for(int i=2;i<=N/2;++i)
    17. 	{
    18. 		if(mark[i]==false)
    19. 		{
    20. 			int b=i+i;
    21. 			while(b<=N)
    22. 			{
    23. 				mark[b]=true;
    24. 				b+=i;
    25. 			}
    26. 		}
    27. 	}
    28. 	vector<int> primes;
    29. 	for(int i=2;i<=N;++i)
    30. 		if(!mark[i])
    31. 			primes.push_back(i);
    32. 	int t;
    33. 	cin>>t;
    34. 	for(int k=1;k<=t;++k)
    35. 	{
    36. 		long long n;
    37. 		cin>>n;
    38. 		long long ans=0;
    39. 		for(int i=0;i<primes.size();++i)
    40. 		{
    41. 			if(n%primes[i]==0)
    42. 			{
    43. 				ans=primes[i];
    44. 				while(n%primes[i]==0)
    45. 					n/=primes[i];
    46. 			}
    47. 		}
    48. 		if(checkPrime(n) && n>ans)
    49. 			ans=n;
    50.  
    51. 		cout<<ans<<endl;
    52. 	}
    53. }