如何快速求一个数的因数个数

3406 浏览 0 回复 2020-08-06

Eihuvita.

+关注

首先贴模板

long long dcp(long long x){
    long long i,ans = 1;
    for(i = 2; i * i <= x; i++){
        if(x % i == 0){
            long long temp = 0;
            while(x % i == 0){
                x /= i;
                temp++;
            }
            ans *= (temp+1);
        }
    }
    if(x > 1) ans *= 2;
    return ans;
}

举个例子， $24=2^{3}*3^{1}$
那么答案就是 $(3+1)*(1+1)=8$
怎么理解呢，
对于2 有0 1 2 3四种指数选择，对于3 有0 1两种指数选择

所以就是4 * 2 = 8 个因子个数
还是理解吧不了，那我们列出来
2 3

$2^{0}*3^{0}=1$ $2^{0}*3^{1}=3$
$2^{1}*3^{0}=2$ $2^{1}*3^{1}=6$
$2^{2}*3^{0}=4$ $2^{2}*3^{1}=12$
$2^{3}*3^{0}=8$ $2^{3}*3^{1}=24$
这就很明显了吧