跳转到内容

图兰筛法

维基百科,自由的百科全书
圖蘭·帕爾

數論中,圖蘭篩法(Turán sieve)是一個用以估計滿足特定條件的「篩選過的」正整數集大小的技巧,而這些條件一般都以同餘表示。這篩法由圖蘭·帕爾於1934年發展。

描述

篩法的術語中,圖蘭篩法是一種「組合篩法」,也就是一種透過小心應用容斥原理進行「篩選」的篩法。此種篩法可給出「篩選過的」的集合大小的上界。

為不大於的正整數的集合,並假定為質數的集合,然後設中可為中的質數整除的數組成的集合;此外,可設中的不同質數的乘積,在這種狀況下,可相應地定義中可被整除的數的集合,並定義本身。

為任意實數,而中不大於的質數的乘積,那這篩法的目標就是估計下式:

我們可以假定說在為質數的狀況下,可由下式估計:

而在為相異質數的乘積狀況下,可由下式估計:

其中的元素個數,而則是一個使得的函數。

,可得下式:

應用

參考資料