批量分解素因数(一)

这个程序的功能是采用高效的算法,将n以内的的所有自然数分解质因数,并存储起来,最后输出其分解式。

1.自然数的分解

根据算术基本定理,一个大于1的自然数能够唯一分解成几个素数乘积的形式。
如\(120=2 \times 2 \times 2 \times 3 \times 5\)。我们这里,将自然数的分解式写成\(n=(p_1^{e_1}) \times (p_2^{e_2}) \times \cdots \times (p_m^{e_m})\)的形式,这里\(p_1,p_2,p_m\)表示素数,\(p_1^{e_1}\), \(p_2^{e_2}\)表示素数的方幂。
如\(120=(2^3)\times(3^1)\times(5^1)\)

2. 非重复素因子的个数

若一个自然数表示为几个素数乘积的形式,则去掉重复因子后,其因子的个数叫做这个自然数的非重复素因子的个数。如120含有3个非重复素因子,他们分别是2,3,5。容易看出,不同的自然数,其非重复素因子个数可能不同的,如27仅有1个非重复素因子3,而210含有2,3,5,7四个非重复素因子。\(2^{32}\)以内的所有整数中,其非重复素因子个数最多不超过9个,这个因为前10个素数的乘积\(2\times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29=6,469,693,230>2^{32}\)

3.自然数分解式的表示

若 \(n=(p_1^{e_1}) \times (p_2^{e_2}) \times \cdots \times (p_m^{e_m})\),我们说这个自然数的分解式包含m项,每项包含2个成员,素因子p和其指数e。自然数的分解式可顺序存储,也可采用链式存储,前者其分解式的所有项的地址是相邻的,各项顺序存放。后者其分解式的每项的地址是不相邻的,使用单链表来存储。链式存需要额外的空间来存储指针,不但内存占用率高,且运行效率也低,故此文中的程序采用顺序存储方式。

4.算法

4.1 首先,函数sift采用与筛法求素数类似的方法,求出n以内所有的素数,并统计出每个合数的非重复素因子的个数。
4.2 接着,程序算出所有n以内的所有自然数分解式的项数的之和,分配内存来存储其分解式,并确定每个自然数的分解式的的地址。方法是:若c_arr[i]表示自然数i的素因子的个数,a_arr[i]表示自然数i的的分解式的存储地址,则自然数i+1的的分解式的地址a_arr[i+1]=a_arr[i]+c_arr[i]
4.3 然后,函数buildfactorTable将n以内的所有自然数分解,并存储其分解式。
4.4 最后,函数print_factor输出每个自然数的分解式。

5.复杂度分析

5.1 空间复杂度
函数batchDecompose 在运行过程中动态分配了3个数组,buff,addrtable和factorTable,前两个数组大小分别为n+1和n+2。最后一个数组的大小取决于n以内每个数的分解式的项数的和。n以内平均每个数的非重复素因子的个数约为log(log(n)),故factorTable的大小约为n*log(log(n)),故总的空间复杂度为o(n*log(log(n)))
5.2 时间复杂度
函数sift的时间复杂度度亦为o(n*log(log(n))),计算addrTable的时间复杂度为o(n),函数buildfactorTable的时间复杂度稍大于o(n*log(log(n))),故总的时间复杂度稍大于o(n*log(log(n)))

下面是C语言源代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注