模组:Factorization/doc

Module:Factorization（编辑 | 讨论 | 历史 | 链接 | 监视 | 日志）

此模块用于处理整数分解。

原理说明

质因数分解

本模组内建前1000个质数的质数表（2、3、5、7 ... 7,919），其实作的演算法为短除法

考虑下列问题：

$f(n,k)=$数字n中，大于等于k、小于等于$\left\lceil {\sqrt {n}}\right\rceil$的质因数

将之改为递回问题

$f\left(n,k\right)={\begin{cases}\varnothing ,&{\mbox{if }}k>\left\lceil {\sqrt {n}}\right\rceil \\\left\{k\right\}\bigcup f({\frac {n}{k}},k),&{\mbox{if }}n\equiv 0{\pmod {k}}\\f\left(n,{\mbox{NextPrime}}\left(k\right)\right),&{\mbox{if }}n\not \equiv 0{\pmod {k}}\end{cases}}$

并且从$f(n,2)$开始计算

也就是说，每找到一个质因数，就会变成更小的问题，例如950

${\begin{array}{r}2{\underline {)950}}\,&30.82\approx {\sqrt {950}}\\5{\underline {)475}}\,&21.79\approx {\sqrt {475}}\\5{\underline {){\color {White}0}95}}\,&9.747\approx {\sqrt {95}}\\\ \ \ 19\,&4.36\approx {\sqrt {19}}\\\end{array}}$

（5以上、4.36以下没有质数，达结束条件）

• 另外一个例子，如496

$n=496,k=2,{\sqrt {n}}\doteqdot 22.27$ 2是496的质因数 $n=248,k=2,{\sqrt {n}}\doteqdot 15.74$ 2是248的质因数 $n=124,k=2,{\sqrt {n}}\doteqdot 11.13$ 2是124的质因数 $n=62,k=2,{\sqrt {n}}\doteqdot 7.87$ 2是62的质因数 $n=31,k=2,{\sqrt {n}}\doteqdot 5.56$ 2不是31的质因数 3不是31的质因数 5不是31的质因数 $7>5.56\approx {\sqrt {31}}$ $\therefore 31$是个质数

${\begin{array}{r}2{\underline {)496}}\\2{\underline {)248}}\\2{\underline {)124}}\\2{\underline {){\color {White}0}62}}\\\ \ \ 31\\\end{array}}$

许多情况可以在对数时间复杂度的情况下除完

最糟情况为除完${\sqrt {n}}$以下的所有质数，约为$\mathrm {O} ({\frac {\sqrt {n}}{\ln {\sqrt {n}}}})$ （参阅素数计数函数）

质数查表

本模组建有质数表和反质数表，因此在7,919以下的质数基本为常数时间（$O(1)$），

因此对应上方演算法，因数分解，在62,710,561（$7,919^{2}$）以下的数字，最优情况为$O(\ln n)$、最糟情况为$\mathrm {O} ({\frac {\sqrt {n}}{\ln {\sqrt {n}}}})$

但在大于7,919的数字则是以试除法实作，并用埃拉托斯特尼筛法和AKS质数测试的部分规则筛掉部分合数，最糟情况为$O({\sqrt {n}})$

因此对应上方演算法，因数分解，在62,710,561（$7,919^{2}$）以上的数字，虽然会将找过的质数建表（同一个模板调用周期中，大数后面计算较率会加快）

但在第一次找NextPrime时，会需要逐一除$O({\sqrt {n}})$，尤其当质数间隙特别大时，整体乘起来有机会变成$O(n)$

代入上方演算法，因数分解，会出现$O(n\ln n)$和最糟情况$\mathrm {O} ({\frac {n{\sqrt {n}}}{\ln {\sqrt {n}}}})$，尤其当输入特大的质数时就会出现计算较慢的情况。

列出因数

其使用Module:Combination找出质因数的全组合，并相乘而得到所有正因数。

函数说明

findDivisor

输入一个整数，并回传其所有因数

参数

• 1：要找出因数的整数

回传值

• 以逗号分隔的因数数列

范例

例如找出360的所有因数

{{#invoke:Factorization|findDivisor|1=360}}

结果为：1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360

若输入无效数字将返回空字串

{{#invoke:Factorization|findDivisor|1=娜娜奇}}

结果为：

factorization

输入一个整数，并印出质因数分解的结果

参数

• 1：要质因数分解的整数，其值不能超过35,184,372,088,831。
• use math：是否以<math></math>格式输出，预设为否

回传值

• 质因数分解的结果字串

范例

例如找出360的所有因数

{{#invoke:Factorization|factorization|1=360}}

结果为：2³ x 3² x 5

若输入无效数字将返回错误

{{#invoke:Factorization|factorization|1=娜娜奇}}

结果为：

使用<math></math>数学模式

{{#invoke:Factorization|factorization|1=360|use math=yes}}

结果为：$2^{3}\times 3^{2}\times 5$

factor

同于英文维基的en:Module:Factorization函数，差别在于用我们的接近对数时间短除法 (质数表内) 的演算法，设计能支援英文维基的参数之Adaptor。

所以最大上限从英文维基的1,000,000,000改为我们的35,184,372,088,831查表上限。

下面为英文区的原始说明文件：

This template displays the factorization of a given number. Numbers smaller than 2 or greater than 1,000,000,000 return "number out of range". Fractional numbers are rounded down.

Parameters

• The first unnamed parameter is the number
• Product - the symbol to be used to indicate times. Defaults to ·
• Bold - set to any value to make it bold
• Serif - set to any value to make it serif
• Big - set to any value to make it big
• Prime - set to any value to have prime numbers return an unformatted link to prime instead of the number

nextPrime

输入一个整数，找到大于该数的最小质数

参数

• 1：要找下一个质数的整数

回传值

• 大于该数的最小质数

范例

例如找出367的下一个质数

{{#invoke:Factorization|nextPrime|1=367}}

结果为：373

lastPrime

输入一个整数，找到小于该数的最大质数

参数

• 1：要找上一个质数的整数

回传值

• 小于该数的最大质数

范例

例如找出367的上一个质数

{{#invoke:Factorization|lastPrime|1=367}}

结果为：359

primeIndex

输入一个整数n，回传第n个质数

参数

• 1：质数序数n

回传值

• 第n个质数

范例

例如找出第367个质数

{{#invoke:Factorization|primeIndex|1=367}}

结果为：2477

primeIndexOf

输入一个整数n，回传小于等于n的质数个数

参数

• 1：质数序数n

回传值

• 小于等于n的质数个数

范例

例如印出367是第73个质数

{{#invoke:Factorization|primeIndexOf|1=367}}

结果为：73

create_factorization_string

将质因数分解表格转成格式化字串，不支援#invoke

语法

create_factorization_string(factors, times, pow_h, pow_f)

参数

• factors：质因数表格，如$2^{3}\times 7^{2}$表示为{[2]=3,[7]=2}。
• times：乘法字元的格式，预设为x。
• pow_h：指数符号开头，预设为<sup>。
• pow_f：指数符号结尾，预设为</sup>。

_findDivisorByPrimeFactor

利用质因数分解表格列出所有因数，不支援#invoke

语法

_findDivisorByPrimeFactor(prime_factors)

参数

• prime_factors：质因数表格，如$2^{3}\times 7^{2}$表示为{[2]=3,[7]=2}。

回传值

• 包含所有因数的一维阵列

_findDivisor

输入一整数，找出所有因数，其使用短除法因数分解，再产生质因数的全排列。不支援#invoke

语法

_findDivisor(num)

参数

num：要找出因数的整数

回传值

• 包含所有因数的一维阵列

_findDivisor_old

输入一整数，找出所有因数，其使用试除法，从2除到平方根。不支援#invoke

语法

_findDivisor_old(input)

参数

num：要找出因数的整数

回传值

• 包含所有因数的一维阵列

_factorization

输入一个整数，并印出质因数分解的结果

语法

_factorization(input)

参数

• input：要质因数分解的整数，其值不能超过35,184,372,088,831。

回传值

• 质因数分解的结果之质因数表格，如$2^{3}\times 7^{2}$表示为{[2]=3,[7]=2}。

_nextPrime

输入一个整数，找到大于该数的最小质数。不支援#invoke

语法

_nextPrime(input)

参数

• input：要找下一个质数的整数

回传值

• 大于该数的最小质数

_lastPrime

输入一个整数，找到小于该数的最大质数。不支援#invoke

语法

_lastPrime(input)

参数

• input：要找上一个质数的整数

回传值

• 小于该数的最大质数

arr

质数表，为一个一维阵列。不支援#invoke

内容

• 预设为前1000个质数

lists

质数反查表，key为质数、value为质数之序数。不支援#invoke

内容

• 预设为前1000个质数

table_max

质数表的预设最大值。不支援#invoke

常数值

• 预设为7919，即第1000个质数。

max_index

质数表的预设最大足标。不支援#invoke

常数值

• 预设为1000，表示预设存了1000个质数。

limit

本模组可处理数字的最大上限。不支援#invoke

常数值

• 预设为35,184,372,088,831，表示预设可存的质数之最大上限。

说明

考量到记忆体限制，根据素数计数函数，10⁷的以下质数有664,579个，其质数表容量已经要以 MB 为单位计算

因此限制质数表最大只能建立到5,931,641（第408,493个质数），对应上方演算法${\sqrt {n}}$

因此限制订为35,184,372,088,831（5,931,641²）

约为 2⁴⁵，位于维基lua整数的运算限制内

设计考量

前提

• 根据mw:Lua_reference_manual#number，支援最大的整数计算为9,007,199,254,740,992，为$2^{53}$
• WP:关注度 (数字)，WP:1729之取值为$10^{7}$，超过的话数字建立条目机率极低，无须刻意支援
• 根据素数计数函数，10⁷的以下质数有664,579个，若这些质数全部建档，质数表容量已经要以 MB 为单位计算