1933: 蓝桥杯算法提高VIP-约数个数（算数基本定理）

解题思路:

O(n)的算法很容易想到，正好刚学了数论，就写一个求约数的模板吧，它的时间复杂度是O(sqrt(n))

根据算数基本定理，一个数可以分成多个质数相乘，例如60=2*2*3*5；

而约数个数就是根据算数基本定理来的，约数的个数等于分解出的质数次方+1相乘

如60的约数个数为：（2+1）*（1+1）*（1+1）=12

12的约数个数等于：（2+1）*（1+1）=6   【12=2*2*3】

附上算数基本定理的数学证明吧：

参考代码:

#include <stdio.h>
#include <math.h>

int main ()
{
	int i,k=0;
	int n,z=1;
	scanf("%d",&n);
	
	for(i=2;i<=n;i++){
		while(n%i==0){
			k++;
			n/=i;
		}
		z*=(k+1);
		k=0;
	}
	printf("%d",z);
	
	return 0;
}