主題
Search

Mapes 方法

一種用於計算素數計數函式的方法。定義函式

T_k(x,a)=(-1)^(beta_0+beta_1+...+beta_(a-1))|_x/(p_1^(beta_0)p_2^(beta_1)...p_a^(beta_(a-1)))_|,
(1)

其中 |_x_| 是向下取整函式，並且 beta_i 是二進位制數字 (0 或 1) 在

k=2^(a-1)beta_(a-1)+2^(a-2)beta_(a-2)+...+2^1beta_1+2^0beta_0.
(2)

勒讓德公式可以寫成

phi(x,a)=sum_(k=0)^(2^a-1)T_k(x,a).
(3)

的前幾個值 T_k(x,3) 是

T_0(x,3)=|_x_|
(4)
T_1(x,3)=-|_x/(p_1)_|
(5)
T_2(x,3)=-|_x/(p_2)_|
(6)
T_3(x,3)=|_x/(p_1p_2)_|
(7)
T_4(x,3)=-|_x/(p_3)_|
(8)
T_5(x,3)=|_x/(p_1p_3)_|
(9)
T_6(x,3)=|_x/(p_2p_3)_|
(10)
T_7(x,3)=-|_x/(p_1p_2p_3)_|.
(11)

Mapes 方法的時間複雜度為 ∼x^(0.7)，這比 Lehmer-Schur 方法稍快。

另請參閱

Lehmer-Schur 方法, 素數計數函式

使用 探索

參考文獻

Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17, 179-185, 1963.Riesel, H. "Mapes' Method." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 23, 1994.

在 中被引用

Mapes 方法

請引用為

Eric W. Weisstein "Mapes 方法。" 來自 —— 資源。 https://mathworld.tw/MapesMethod.html

主題分類