模块:Factorization/doc
这是Module:Factorization的文档页面
Module:Factorization(编辑 | 讨论 | 历史 | 链接 | 监视 | 日志)
![]() | 此Lua模块与英文维基的版本完全不同,甚至不是Fork。本模块是独立于英文维基百科独立开发的,只是因为wikidata有对应项目后增加了一个与英文维基对应页面相同功能的函式。 请不要把本模组与英文维基同步,否则将导致其他相依模块(如:Module:Number)无法运作。请在模块的/sandbox或者/testcases子页面测试。考虑至讨论页讨论变更。 |
![]() | 此模块使用Lua语言: |
此模块用于处理整数分解。
原理说明
质因数分解
本模组内建前1000个质数的质数表(2、3、5、7 ... 7,919),其实作的算法为短除法
考虑下列问题:
- 数字n中,大于等于k、小于等于 的质因数
将之改为递回问题
-
- 并且从 开始计算
- 也就是说,每找到一个质因数,就会变成更小的问题,例如950
- (5以上、4.36以下没有质数,达结束条件)
- 另外一个例子,如496
|
|
- 许多情况可以在对数时间复杂度的情况下除完
- 最糟情况为除完 以下的所有质数,约为 (参阅素数计数函数)
质数查表
本模组建有质数表和反质数表,因此在7,919以下的质数基本为常数时间( ),
- 因此对应上方算法,因数分解,在62,710,561( )以下的数字,最优情况为 、最糟情况为
但在大于7,919的数字则是以试除法实作,并用埃拉托斯特尼筛法和AKS质数测试的部分规则筛掉部分合数,最糟情况为
- 因此对应上方算法,因数分解,在62,710,561( )以上的数字,虽然会将找过的质数建表(同一个模板调用周期中,大数后面计算较率会加快)
- 但在第一次找NextPrime时,会需要逐一除 ,尤其当质数间隙特别大时,整体乘起来有机会变成
- 代入上方算法,因数分解,会出现 和最糟情况 ,尤其当输入特大的质数时就会出现计算较慢的情况。
列出因数
- 其使用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}}
- 结果为:23 x 32 x 5
- 若输入无效数字将返回错误
{{#invoke:Factorization|factorization|1=娜娜奇}}
- 结果为:错误:不正确的数字
- 使用<math></math>数学模式
{{#invoke:Factorization|factorization|1=360|use math=yes}}
- 结果为:
factor
同于英文维基的en:Module:Factorization函数,差别在于用我们的接近对数时间短除法 (质数表内) 的算法,设计能支援英文维基的参数之Adaptor。
所以最大上限从英文维基的1,000,000,000改为我们的35,184,372,088,831查表上限。
下面为英文区的原始说明文件:
此模块文档已评为beta版,可广泛使用。因其新近完成,请谨慎使用,以确保输出结果符合预期。 |
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,[7]=2}
。 - times:乘法字元的格式,预设为
x
。 - pow_h:指数符号开头,预设为
<sup>
。 - pow_f:指数符号结尾,预设为
</sup>
。
_findDivisorByPrimeFactor
利用质因数分解表格列出所有因数,不支援#invoke
- 语法
_findDivisorByPrimeFactor(prime_factors)
- 参数
- prime_factors:质因数表格,如 表示为
{[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,[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,表示预设可存的质数之最大上限。
- 说明
- 考量到记忆体限制,根据素数计数函数,107的以下质数有664,579个,其质数表容量已经要以 MB 为单位计算
- 因此限制质数表最大只能建立到5,931,641(第408,493个质数),对应上方算法
- 因此限制订为35,184,372,088,831(5,931,6412)
- 约为 245,位于维基lua整数的运算限制内
设计考量
- 前提
- 根据mw:Lua_reference_manual#number,支援最大的整数计算为9,007,199,254,740,992,为
- WP:关注度 (数字),WP:1729之取值为 ,超过的话数字建立条目几率极低,无须刻意支援
- 根据素数计数函数,107的以下质数有664,579个,若这些质数全部建档,质数表容量已经要以 MB 为单位计算