# 素数计数函数

## 历史

$x/\operatorname {ln} (x)\!$ $\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\operatorname {ln} (x)}}=1.\!$ $\lim _{x\rightarrow \infty }\pi (x)/\operatorname {li} (x)=1\!$ $\pi (x)=\operatorname {li} (x)+\mathrm {O} \left(x\exp \left(-{\frac {\sqrt {\ln(x)}}{15}}\right)\right)\!$ $\sum _{p\leq x}p^{n}\sim \pi (x^{n+1})\sim Li(x^{n+1}).$ ## π(x)、x / ln x和li(x)

x π(x) π(x) − x / ln x li(x) − π(x) x / π(x) x / ln x  % Error
10 4 −0.3 2.2 2.500 -7.5%
102 25 3.3 5.1 4.000 13.20%
103 168 23 10 5.952 13.69%
104 1,229 143 17 8.137 11.64%
105 9,592 906 38 10.425 9.45%
106 78,498 6,116 130 12.740 7.79%
107 664,579 44,158 339 15.047 6.64%
108 5,761,455 332,774 754 17.357 5.78%
109 50,847,534 2,592,592 1,701 19.667 5.10%
1010 455,052,511 20,758,029 3,104 21.975 4.56%
1011 4,118,054,813 169,923,159 11,588 24.283 4.13%
1012 37,607,912,018 1,416,705,193 38,263 26.590 3.77%
1013 346,065,536,839 11,992,858,452 108,971 28.896 3.47%
1014 3,204,941,750,802 102,838,308,636 314,890 31.202 3.21%
1015 29,844,570,422,669 891,604,962,452 1,052,619 33.507 2.99%
1016 279,238,341,033,925 7,804,289,844,393 3,214,632 35.812 2.79%
1017 2,623,557,157,654,233 68,883,734,693,281 7,956,589 38.116 2.63%
1018 24,739,954,287,740,860 612,483,070,893,536 21,949,555 40.420 2.48%
1019 234,057,667,276,344,607 5,481,624,169,369,960 99,877,775 42.725 2.34%
1020 2,220,819,602,560,918,840 49,347,193,044,659,701 222,744,644 45.028 2.22%
1021 21,127,269,486,018,731,928 446,579,871,578,168,707 597,394,254 47.332 2.11%
1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1,932,355,208 49.636 2.02%
1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 7,250,186,216 51.939 1.93%
1024 18,435,599,767,349,200,867,866 339,996,354,713,708,049,069 17,146,907,278 54.243 1.84%
1025 176,846,309,399,143,769,411,680 3,128,516,637,843,038,351,228 55,160,980,939 56.546 1.77%
1026 1,699,246,750,872,437,141,327,603 28,883,358,936,853,188,823,261 155,891,678,121 58.850 1.70%
1027 16,352,460,426,841,680,446,427,399 267,479,615,610,131,274,163,365 508,666,658,006 61.153 1.64%

## 计算π(x)的方法

$\lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i （其中$\lfloor \cdot \rfloor$ 取整函数）。因此这个数等于：

$\pi (x)-\pi \left({\sqrt {x}}\right)+1\,$ $\Phi (m,n)=\Phi (m,n-1)-\Phi \left(\left[{\frac {m}{p_{n}}}\right],n-1\right).\,$ $\pi (m)=\Phi (m,n)+n(\mu +1)+{\frac {\mu ^{2}-\mu }{2}}-1-\sum _{k=1}^{\mu }\pi \left({\frac {m}{p_{n+k}}}\right).\,$ 1959年，德里克·亨利·勒梅尔推广并简化了梅塞尔的方法。对于实数$m$ 和自然数$n$ $k$ ，定义$P_{k}(m,n)$ 为不大于m且正好有k个大于$p_{n}$ 的素因子的整数个数。更进一步，设定$P_{0}(m,n)=1$ 。那么：

$\Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n),\,$ $\pi (m)=\Phi (m,n)+n-1-P_{2}(m,n).$ $P_{2}(m,n)$ 的计算可以用这种方法来获得：

$P_{2}(m,n)=\sum _{y 1. $\Phi (m,0)=\lfloor m\rfloor ;\,$ 2. $\Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right).\,$ ## 其它素数计数函数

$\Pi _{0}(x)={\frac {1}{2}}{\bigg (}\sum _{p^{n} $\Pi _{0}(x)=\sum _{2}^{x}{\frac {\Lambda (n)}{\ln n}}-{\frac {1}{2}}{\frac {\Lambda (x)}{\ln x}}=\sum _{n=1}^{\infty }{\frac {1}{n}}\pi _{0}(x^{1/n})$ $\pi _{0}(x)=\lim _{\varepsilon \rightarrow 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.$ $\pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\Pi _{0}(x^{1/n})$ $\ln \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s+1}\,dx$ ## 不等式

${\frac {x}{\ln x}}<\pi (x)<1.25506{\frac {x}{\ln x}}\!$ ，左不等式适用于x ≥ 17，右不等式适用于x>1，常数1.25506为 ${\frac {30\ln 113}{113}}$ 保留5位有效小数，${\frac {\pi (x)\ln x}{x}}$ 最大值为x = 113。

Pierre Dusart 在2010年证明：

${\frac {x}{\ln x-1}}<\pi (x)\!$ （其中$x\geq 5393$ $\pi (x)<{\frac {x}{\ln x-1.1}}\!$ （其中$x\geq 60184$ n个素数pn的不等式：

$n\ln n+n\ln \ln n-n n个素数的一个估计是：

$p_{n}=n\ln n+n\ln \ln n-n+{\frac {n\ln \ln n-2n}{\ln n}}+O\left({\frac {n(\ln \ln n)^{2}}{(\ln n)^{2}}}\right).$ ## 参考文献

• Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory. MIT Press. 1996: volume 1 page 234 section 8.8. ISBN 0-262-02405-5.
• Dickson, Leonard Eugene. History of the Theory of Numbers I: Divisibility and Primality. Dover Publications. 2005. ISBN 0-486-44232-2.
• Ireland, Kenneth; Rosen, Michael. A Classical Introduction to Modern Number Theory Second edition. Springer. 1998. ISBN 0-387-97329-X.
• Hwang H. Cheng Prime Magic conference given at the University of Bordeaux (France) at year 2001 Démarches de la Géométrie et des Nombres de l'Université du Bordeaux
• Titchmarsh, E. C. The Theory of Functions, 2nd ed. Oxford, England: Oxford University Press, 1960.
{"ft_lang_label":"__label__zh","ft_lang_prob":0.6381897,"math_prob":0.9999192,"size":3883,"snap":"2022-27-2022-33","text_gpt3_token_len":2453,"char_repetition_ratio":0.05516886,"word_repetition_ratio":0.0,"special_character_ratio":0.6211692,"punctuation_ratio":0.3125,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9990363,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74],"im_url_duplicate_count":[null,null,null,3,null,3,null,3,null,3,null,3,null,3,null,null,null,3,null,3,null,3,null,null,null,null,null,null,null,4,null,null,null,4,null,3,null,3,null,4,null,3,null,3,null,3,null,3,null,3,null,3,null,3,null,3,null,2,null,2,null,2,null,2,null,5,null,2,null,5,null,2,null,3,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-19T20:24:59Z\",\"WARC-Record-ID\":\"<urn:uuid:93709047-4ae6-4166-89ec-1f6200595e19>\",\"Content-Length\":\"160855\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2ea22e54-9deb-4efc-9c71-717478e0fa59>\",\"WARC-Concurrent-To\":\"<urn:uuid:3c76fa30-2a7d-432e-80da-b297da5ef409>\",\"WARC-IP-Address\":\"208.80.154.224\",\"WARC-Target-URI\":\"https://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E8%AE%A1%E6%95%B0%E5%87%BD%E6%95%B0\",\"WARC-Payload-Digest\":\"sha1:LTDENIJF76CQ4CYXUYJJTQEJVMCTWFZU\",\"WARC-Block-Digest\":\"sha1:4S7YGGGXP7C4UYDSMTS5LM7QOLV5WI7A\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882573760.75_warc_CC-MAIN-20220819191655-20220819221655-00789.warc.gz\"}"}