塞尔伯格筛法

在數論中，塞爾伯格篩法（Selberg sieve）是一個用以估計滿足特定條件的「篩選過的」正整數集大小的技巧，而這些條件一般都以同餘表示。這篩法由阿特勒·塞爾伯格於1940年代發展。

描述
在篩法的術語中，塞爾伯格篩法是一種「組合篩法」，也就是一種透過小心應用容斥原理進行「篩選」的篩法。在此篩法中，塞爾伯格以一組針對問題最佳化的權重取代默比烏斯函數，而這可給出「篩選過的」的集合大小的上界。

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

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

我們可以假定說可由下式估計：

其中是一個積性函數、是的元素個數。

另外，設是個由對進行默比烏斯反演所得到的函數，也就是說，且，其中是默比烏斯函數。

在這種狀況下，設，就可得下列關係式：

其中是及的最小公倍數。

此外，的數值可由下式估計：

應用
 相關問題上的。
 不大於且與歐拉函數互質的的數量，與呈現非病態的（asymptotic）關係。

參考資料
 
 
 
 
 
 

篩法