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