如何运用唯一分解定理的常见技巧？

本文共计1246个文字，预计阅读时间需要5分钟。

在算法中常遇到与整数因子相关的问题，常可通过质因数分解巧妙解决。例如：60=2^2 * 3^1 * 5^1，60的因子数有(2+1)*(1+1)*(1+1)=12个。100=2^2 * 5^2，100的因子数有(2+1)*(2+1)=9个。

引言

在算法中经常遇到与整数因子有关的问题，常常可以通过质因数分解来巧妙地解决问题：

例如:

60 = 2^2 * 3^1 * 5^1 则60的因子数有(2+1) * (1+1) * (1+1) = 12个

100 = 2^2 * 5^2 则60的因子数有(2+1) * (2+1) = 9个

下面的两个问题可以更深入地理解定理的用法.

问题一 阶乘约数

定义阶乘n! = 1 * 2 * 3 * 4… * n.

请问100！(100的阶乘)有多少个正约数.

100! = 1 * 2 * 3 * 4… * 100，依次分解每个乘数。

定义一个初始化均为0长度为101的数组，储存每个乘数分解后得到的质因数的指数，质因数相同的可以直接指数相加(同底数幂的乘法)。

利用唯一分解定理处理最后得到的数组中的元素，最终得到约数个数。