模组:Factorization/doc

这是Module:Factorization的文档页面

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

此模块用于处理整数分解

原理说明

质因数分解

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

考虑下列问题:

 数字n中,大于等于k、小于等于 的质因数

将之改为递回问题

 
并且从 开始计算
也就是说,每找到一个质因数,就会变成更小的问题,例如950
 
(5以上、4.36以下没有质数,达结束条件)
  • 另外一个例子,如496
  •  
    2是496的质因数
  •  
    2是248的质因数
  •  
    2是124的质因数
  •  
    2是62的质因数
  •  
    2不是31的质因数
    3不是31的质因数
    5不是31的质因数
     
     是个质数

 

许多情况可以在对数时间复杂度的情况下除完
最糟情况为除完 以下的所有质数,约为  (参阅素数计数函数

质数查表

本模组建有质数表和反质数表,因此在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查表上限。

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

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 为单位计算