素数分解的唯一性：p1^x1*p2^x2...pn^xn(一个整数可唯一地分解为一些不同质因子的若干次方的乘积)

再根据乘法原理 因子个数为(x1+1)*(x2+1) + ... + (xn + 1)

例题：LightOJ - 1028 （计算因子个数）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;
#define LL long long
#define ULL unsigned long long
#define MAX int(1e6+18)//求MAX范围内的素数 
const int N  = 1e6+11;
const int M  = 1e6+11;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;

//bool su[N+1]={1,1,0}; int prm[N+1],sz=0;
 
long long su[MAX],cnt;  
bool isprime[MAX];  
void prime()  
{  
    cnt=1;  
    memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数  
    isprime[0]=isprime[1]=0;//0和1不是素数  
    for(long long i=2;i<=MAX;i++)  
    {  
        if(isprime[i]) {
            su[cnt++]=i;//保存素数i  
        } 
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)  
        {  
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数  
        }  
    }  
}  
//void init(){
//    for(int i=2;i<N;i++){
//        if(!su[i]) prm[sz++]=i;
//        for(int j=0;j<sz;j++){
//            int t=prm[j]*i;
//            if(t>N) break;
//            su[t]=1;
//            if(i%prm[j]==0) break;
//        }
//    }
//}
LL solve(LL n){
    LL ans=1;
    for(int i=1;i<=cnt && su[i]*1ll*su[i]<=n;i++){
        if(n%su[i]==0){
            LL cntt=0;
            while(n%su[i]==0) {
                cntt++; n/=su[i];
            }
            
            ans=ans*(cntt+1);
        }
    }
    if(n!=1) ans<<=1;
//	printf("Ans = %d\n",ans); 
    return ans-1;
}
LL num(LL n){ //返回的是因子总数
    LL count=2;
    for(LL i=2;i<=sqrt(n);i++){
        if(n%i==0){
            if(i==sqrt(n) && n/i==i){ //如果两因子相同，则只加1
                 count++;   
            }
            else count+=2;
        }
    }
    return count;
}
int main(){
 //   init();
//    cout<<prm[0]<<prm[1]<<prm[2]<<endl;
    prime();
	int T ;scanf("%d",&T);
    int cas=1;
    while(T--){
        LL n;scanf("%lld",&n);
        printf("Case %d: %lld\n",cas++,solve(n));
    }
return 0;
}

换成输出num(n)-1，则超时。