严格证明: 假设n可以分解成质因子乘积的形式 n=p1^e1*p2^e2*……*pi^ei -------------------- (1) 上面的式子的意思是说,n的质因子是p1,p2,….,pi,而e1,e2,…,ei表示每个质因子在n中有多少个,举例子说 n=36 n=2^2*3^2 n=130 n=2*5*13=2^1*5^1*13^1 由(1)式可知,n的因子的个数是 n = (e1+1)*(e2+1)*…*(ei+1) 同样道理,我们可以把n^2写成 n^2= p1^2e1*p2^2e2*……*pi^2ei -------------------- (2) 也就是说每个质因子的指数由原来的e变成了2e(偶数出来了) 那么,n^2的因子的个数就是 n = (2e1+1)*(2e2+1)*…*(2ei+1) 上式每一项都是奇数,他们的乘积也就是奇数 刚算了一下,没有简单算法,跟这个差不多。质数就不说了,简单,合数都可以看成n个质因子相乘的积,无论这个质因子的幂是积还是偶,平方后都将是一个偶数,那么平方后的这个合数的因子个数就是n个奇数的乘积了,还是奇数
[此贴子已经被作者于2009-1-30 20:02:16编辑过] |