【模板】求一个数的因子个数-质因数分解

结论

对于任何一个自然数NN，都可以分解质因子得到如下形式：

N=pe11∗pe22∗pe33∗⋯∗pekkN=p1^e1 ∗ p2^e2 ∗ p3^e3∗ ⋯ ∗ pk^ek(e1、e2…ek是指数)

那么有结论：N的因子的个数为：f(n)=(1+e1)∗(1+e2)∗⋯∗(1+ek)

如N=100，分解质因子变形为：100=22∗52，NN的因子的个数为：f(N)=f(100)=(1+2)∗(1+2)=9

即：1,2,4,5,10,20,25,50,100

推导

1.因为任何一个数都能分解成如上形式(N=1时,2^0)

2.又在对N进行分解时,对质因数p1，有选0~e1个共e1+1种情况；

3.且质因数相乘结果不重复(由于质数间互质)，所以结果就是:

f(n)=(1+e1)∗(1+e2)∗⋯∗(1+ek)

代码展示

int Get_factornum(int x){int ans=1;for(int i=2;i*i<=x;i++){int num=1;while(x%i==0){num++;x/=i;}ans*=num;}if(x>1){//说明还存在一个质因数,例如14 ans*=2;}return ans;}