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