题意:求 n ( 1<n< 1e18) 的质因子中幂次最小的。
解:由于数的范围很大,题意只求幂次最小,预处理10000以内素数,差不多一千两百多个,每次对n先合数分解,
若此时幂次最小为1则返回答案。分解完答案不为 1 且分解后的值 tmp 大于 1 ,则存在超过 1e4的质因数,最多4次方(5次超范围)。那就分类讨论,设质因数 a ,b ,有以下四种情况。
1. tmp == a^4 ans>4 则ans = 4;
2. tmp == a^3 ans>3 则ans = 3;
3.tmp == a^2 ans>2 且 不为四次方 ans = 2
4. tmp == tmp ans = 1
#include <bits/stdc++.h>
using namespace std;
const int MAXN=10000+10;
int prime[MAXN+1];
int is_prime[MAXN+1];
void getPrime() {
memset(is_prime,0,sizeof(is_prime));
for(int i=2; i<=MAXN; i++) {
if(!is_prime[i])prime[++prime[0]]=i;//第prime[0]个素数是i
for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) {
is_prime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
long long sqrt3(long long n) {
long long l=1,r=(long long)pow(n*1.0, 1.0 / 3) + 1,mid;
while(l<=r) {
mid=(l+r)>>1;
if(mid*mid*mid==n) return mid;
else if(mid*mid*mid>n) r=mid-1;
else l=mid+1;
}
return -1;
}
long long factor[1000][2];
int fatCnt;
int getFactors(long long x) {
fatCnt=0;
int ans = 100;
long long tmp=x;
for(int i=1; i<=prime[0]; i++) {
if(1ll*prime[i]*prime[i]>tmp)
break;
factor[fatCnt][1]=0;
if(tmp%prime[i]==0) {
factor[fatCnt][0]=prime[i];
while(tmp%prime[i]==0) {
factor[fatCnt][1]++;
tmp/=prime[i];
}
if(factor[fatCnt][1]<ans) ans = factor[fatCnt][1];
fatCnt++;
}
if(ans==1)return 1;
}
long long k1,k2;
if(tmp>1) {
k1 = sqrt(tmp);
if(k1*k1==tmp) {
k2 = sqrt(k1);
if(k2*k2==k1&&ans>4)ans=4;
else if(k2*k2!=k1&&ans>2)ans=2;
}else{
k1 = sqrt3(tmp);
if(k1*k1*k1==tmp&&ans>3)ans=3;
else ans = 1;
}
}
return ans;
}
int main() {
getPrime();
int t;
scanf("%d",&t);
long long n;
while(t--) {
scanf("%lld",&n);
printf("%d\n",getFactors(n));
}
}