模組: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 為單位計算