http://www.51nod.com/Challenge/Problem.html#problemId=2176

对于 n ，一直除去因子直到无法再除为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k;
int main(){
	freopen("in","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&n);
		k=2; 
		while(n>1){
			while(n%k==0) n/=k;
			k++;
			if(k*k>n&&n>1) k=n;
		}
		printf("%lld\n",k-1);
	}
	return 0;
}