约数的个数

约数的个数

输入n个整数,依次输出每个数的约数的个数

输入描述

输入的第一行为N,即数组的个数(N<=1000) 接下来的1行包括N个整数,其中每个数的范围为(1<=Num<=1000000000) 当N=0时输入结束。

输出描述

可能有多组输入数据,对于每组输入数据, 输出N行,其中每一行对应上面的一个数的约数的个数。

刚看到这道题的第一反应也是暴力、循环计数。但是转眼一想,数字范围较大,而且使用Python更是没有速度优势。那么这道题只有去寻找相关的算法了。

约数个数定理

对于一个大于1正整数n可以分解质因数:

则n的正约数的个数就是

其中a1、a2、a3…ak是p1、p2、p3,…pk的指数。

定理简证

首先同上,n可以分解质因数:n=p1^a1×p2^a2×p3^a3pk^ak

由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1,共(a1+1)个;

同理p2^a2的约数有(a2+1)个......pk^ak的约数有(ak+1)个。

故根据乘法原理:n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。

本题题解

大致思路如下: 1. 分解质因数 2. 对各个质因数计数 3. 各个计数结果+1之后求乘积

需要注意的是如果是1的话则不符合这个定理,因此需要提前判断

from operator import mul
from functools import reduce

def f(x,s):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            s.append(i)
            f(x//i,s)
            break
    else:s.append(x)
    return s

input()
n = map(int, input().split())
for a in n:
    if a == 1:
        print(a)
        continue
    a = f(a, [])
    s = [a.count(i)+1 for i in set(a)]
    print(reduce(mul, s))