素数的个数公式 作者姓名：弯国强 作者地址：漯河市舞阳县莲花镇第二初级中学 E-mail:632158@163.com 摘要：■1.素数的个数公式在素数分布的研究中具有重要的理论意义。 ■2.素数的个数公式的简化计算一直是素数的个数计算中的一个 关键。 关键词：素数、素数的个数公式、筛法函数 中图分类号：0156.1 素数，又称质数，只有两个正因数(1和本身)的自然数。除了1和本身 外还有别的约数的数称之为合数，而1和0既非素数也非合数。在素数中，只有 2为偶数，其余的全为奇数，并且，当素数p>3时，p一定是6k±1的形状(k 为整数)。 对于正整数n,定义π(n)为不大于n的素数总个数。√n表示n的算术平方 根，[V们表示不超过m的最大整数。m为整数，当2≤pp,…pm≤[m们时， PP2…pm表示自然数n的前部质数，m为前部素数的个数，m=π（√n);j 为整数，当Vn<g,q2…q,≤n时，qpq2…q,表示自然数n的后部质数， j为后部素数的个数。所以π(n)=m+j。 定理1：任大于1的整数n,除1外的最小正因数q为素数，并且当n为合 数时g≤√n。证明可以参考《初等数论》郭凤琴编P17 定理2：“若自然数n不能被不大于√n的任何素数整除，则n是一个素 数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。 定理3：（容斥原理)设A,A,…Am是有限集A的子集，4=n,那么A 中所有不属于A,A,…An中任何一个元素个数为： 设4n4n…n4简记为门4.：4U4U…UA简记丸U4 U4-24-24n4a4n4n4-+-l4 那么
素数的个数公式 作者姓名：弯国强 作者地址：漯河市舞阳县莲花镇第二初级中学 E-mail：632158@163.com 摘 要：■1.素数的个数公式在素数分布的研究中具有重要的理论意义。 ■2. 素数的个数公式的简化计算一直是素数的个数计算中的一个 关键。 关键词：素数、素数的个数公式、筛法函数 中图分类号：O156.1 素数，又称质数，只有两个正因数（1 和本身）的自然数。 除了 1 和本身 外还有别的约数的数称之为合数，而 1 和 0 既非素数也非合数。在素数中，只有 2 为偶数，其余的全为奇数，并且，当素数 p＞3 时，p 一定是6 1 k ± 的形状（k 为整数）。 对于正整数 n，定义 π(n)为不大于 n 的素数总个数。 n 表示 n 的算术平方 根，⎡ ⎤ n ⎣ ⎦ 表示不超过 n 的最大整数。m 为整数，当 2≦ 12 m pp p ， ≦ "" ⎡ ⎤ n ⎣ ⎦ 时， 12 m pp p ， 表示自然数 "" n 的前部质数，m 为前部素数的个数，m n = π ( ) ；j 为整数，当⎡ ⎤ n ⎣ ⎦ ﹤q，q q 1 j ２"" ≦n 时，q，q q 1 j ２"" 表示自然数 n 的后部质数， j 为后部素数的个数。所以 π(n)＝m+j。 定理 1：任大于 1 的整数 n，除 1 外的最小正因数 q 为素数，并且当 n 为合 数时q n ≤ 。证明可以参考《初等数论》郭凤琴编 P17. 定理 2：“若自然数 n 不能被不大于 n 的任何素数整除，则 n 是一个素 数”。见（代数学辞典[上海教育出版社]1985 年。屉部贞世朗编。259 页）。 定理 3：（容斥原理）设 1 2 , , AA A "" m 是有限集 A 的子集， A n = ，那么 A 中所有不属于 1 2 , , AA A "" m 中任何一个元素个数为： 设 1 2 1 m m m i AA A A = ∩ ∩""∩ 简记为 ； ∩ 1 2 1 m m m i AA A A = ∪ ∪""∪ 简记为∪ ( ) 1 1 1 1 1 m mm m m m i i i j i jk i i i i j i jk i A A AA AA A A − = = < << = ∪ ∩ = − + − +− ∑∑ ∑ ∩ ∩ ∩ "" 那么
0=n-24-24n4-an4,n4++erh4 根据定理2，可以求出不超过正整数n的一切素数，具体方法是： 首先写出1,2,3，…n一1，n 划去1，剩下第一个数是2，因为2没有小于自身的真因数，所以2是一个 素数。 留下2，从2起，再划去2的倍数，第一个留下来未划去的是3,3没有小 于自身的真因数，所以3是素数。 留下3，从3起，再划去3的倍数，第一个留下来未划去的是5,5没有小 于自身的真因数，所以5是素数。 这样继续做下去，当我们把所有不大于V的素数的倍数都划去后，剩下 的数就是所有不超过n的素数。这个方法就是古老的筛法，也叫埃拉托塞 尼筛法。 定理4：（素数的个数公式） 设n为正整数，p,P2,pm为n的前部素数，m=π(n列是前部质数的个 数，那么所有不大于n的素数的个数 π(n)=m+n-j 证明：记A,={不大于n能被素数p,整除的数，A,={不大于n能被素数P2整除 的数}… An={不大于n能被素数pm整除的数}，P,P2,…pm表示n的前部素数，且 P,P,…Pn为连续素数。任意给定正整数n中，能被素数p整除的数的个数 为14= 任意给定正整数n中，能被素数P,整除的数的个数为 4-A …任意给定正整数n中，能被素数pm整除的数的个数为 P,P2,…Pm表示正整数N的前部素数，为前部素数的个数。由容斥原理可知
( ) 1 1 1 1 m mm m m m i i i j i jk i i i i j i jk i A n A AA AA A A = = < << = ∪ ∩ = − + − + +− ∑∑ ∑ ∩ ∩ ∩ "" 根据定理 2，可以求出不超过正整数 n 的一切素数，具体方法是： 首先写出 1，2，3，…………n—1，n 划去 1，剩下第一个数是 2，因为 2 没有小于自身的真因数，所以 2 是一个 素数。 留下 2，从 2 起，再划去 2 的倍数，第一个留下来未划去的是 3，3 没有小 于自身的真因数，所以 3 是素数。 留下 3，从 3 起，再划去 3 的倍数，第一个留下来未划去的是 5，5 没有小 于自身的真因数，所以 5 是素数。 这样继续做下去，当我们把所有不大于 n 的素数的倍数都划去后，剩下 的数就是所有不超过 n 的素数。这个方法就是古老的筛法，也叫埃拉托塞 尼筛法。 定理 4：（素数的个数公式） 设 n 为正整数， 1 2 , , m p p p "" 为 n 的前部素数，m n = π ( ) 是前部质数的个 数，那么所有不大于 n 的素数的个数 1 1 ( ) ( 1) 1 mm m m m i i j i jk i i j i jk i i nn n n n mn p pp pp p p π = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = + − + − + +− − ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 证明：记A ={ 1 不大于 n 能被素数 1 p 整除的数}，A2 ={不大于 n 能被素数 2 p 整除 的数}…… Am ={不大于 n 能被素数 mp 整除的数}, 1 2 , , m p p p "" 表示 n 的前部素数，且 1 2 , , m p p p "" 为连续素数。任意给定正整数 n 中，能被素数 1 p 整除的数的个数 为｜ 1 1 n A p ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ ，任意给定正整数 n 中，能被素数 2 p 整除的数的个数为 2 2 n A p ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ ，……任意给定正整数 n 中，能被素数 mp 整除的数的个数为 m m n A p ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 1 2 , , m p p p "" 表示正整数Ｎ的前部素数，m 为前部素数的个数。由容斥原理可知
4-24-24n会4n4n4-+少4 其中94 表示正整数n中能被P,或P2或…或pm整除的所有整数的个数， 即不大于血的所有合数和前部素数之和的个数。么门4的补门4 就表示不 大于n的后部素数加1的个数， A=n-立4利+空An4外三4nn小++(-门4甲：后部秦数 的个数=n-24小2n4小三n4n4+…+-l少门4 又因为 4-[w-[}w-[ nw4a一 即： 所以不大于N的所有素数的个数π()=m+j=m+ m-24+2An4三4n4n4++-l旷门4 即： x=m+n-】 点六位 命题证毕。 当m=π（√n时，根据容斥定理我们可以知道后部质数的个数为
( ) 1 1 1 1 1 m mm m m m i i i j i jk i i i i j i jk i A A AA AA A A − = = < << = ∪ ∩ = − + − +− ∑∑ ∑ ∩ ∩ ∩ "" 其中 1 m i i A = ∪ 表示正整数 n 中能被 1 p 或 2 p 或……或 m p 整除的所有整数的个数， 即不大于 n 的所有合数和前部素数之和的个数。那么 1 m i i A = ∪ 的补 1 m i i A = ∪ 就表示不 大于 n 的后部素数加１的个数， ( ) 1 1 1 1 m mm m m m i i i j i jk i i i i j i jk i A n A AA AA A A = = < << = ∪ ∩ = − + − + +− ∑∑ ∑ ∩ ∩ ∩ "" 即：后部素数 的个数 ( ) 1 1 1 1 mm m m m i i j i jk i i i j i jk i jn A A A A A A A = < << = = − + − + +− − ∑∑ ∑ ∩ ∩ ∩ "" ∩ 又因为 1 2 1 2 , ,, i i nn n AA A p p p ⎡⎤ ⎡ ⎤ ⎡ ⎤ == = ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎣ ⎦ "" ， i j i j n A A p p ⎡ ⎤ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ∩ , i jk i jk n AA A p p p ⎡ ⎤ = ⎢ ⎥ ⎢⎣ ⎥⎦ ∩ ∩ ,……， 1 1 m i m i i i n A p = = ⎡ ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ∏ ∩ 即： 1 1 ( 1) 1 mm m m m i i j i jk i i j i jk i i nn n n j n p pp pp p p = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− − ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 所以不大于Ｎ的所有素数的个数 π(n)＝m+j＝m+ ( ) 1 1 1 1 mm m m m i i j i jk i i i j i jk i n A AA AA A A = < << = − + − + +− − ∑∑ ∑ ∩ ∩ ∩ "" ∩ 即： 1 1 ( ) ( 1) 1 mm m m m i i j i jk i i j i jk i i nn n n n mn p pp pp p p π = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = + − + − + +− − ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 命题证毕。 当m n = π ( ) 时，根据容斥定理我们可以知道后部质数的个数为
-}… 又因为 -引}r n -1≥0，故 ·卧品小 n 当m=π(n)时，有容斥原理可以知道这个公式表示n减去n以内的全部质数倍数 的个数也就是只剩下1。故 当π(Wm<m<π(n)时，有容斥原理可以知道这个公式表示n减去n以内m个 质数倍数的个数也就是还剩有质数和1。故 当0<m<π(n时，有容斥原理可以知道这个公式表示n减去n以内m个质数 倍数的个数也就是还剩有质数，合数和1。故 当m=0时，有容斥原理可以知道这个公式表示n减去n以内0个质数倍数的个 数也就是没有减去一个数。故
( ) 1 1 1 1 mm m m m i i j i jk i i j i jk i i nn n n j n p pp pp p p = ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 当0 < < m n π ( ) 时，有容斥原理可以知道这个公式表示 n 减去 n 以内 m 个质数 倍数的个数也就是还剩有质数，合数和 1。故 ( ) 1 1 1 mm m m m i i j i jk i i j i jk i i nn n n n j p pp pp p p = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ − + − + +− ≥ ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 当m = 0时，有容斥原理可以知道这个公式表示 n 减去 n 以内 0 个质数倍数的个 数也就是没有减去一个数。故
=n Πp, 筛法函数在简化计算素数的个数个数公式中具有至关重要的作用，那么什 么是筛法函数呢？ 设p,P2,…p,是最初r个素数，不大于n且不能被任何一个素数 p,(i=l,2…r)整除的自然数个数记为π(n,r）,那么： π(n,r）这个函数我们把它叫筛法函数。它表示从自然数列1、2、3n中依 次筛去最初r个素数P,P2,…p,及其倍数，剩余自然数的个数。 当r=0时，π(n,r）=n。这个结论很好理解，从自然数列1、2、3n中不筛 去任何数，所以π(n,r)=n 当0j+1。这个结论可以这样理解，从自然数列1、 2、3n中依次筛去r个素数及其倍数，但是不到m=π(Vn个素数，也就是 自然数列1、2、3中还有合数没有筛去，最后剩下自然数1和后部素数还 没有筛去的合数。所以π(n,r)>j+1 当r=m=π(Vn时，π(n,r）=j+1。这个结论很好理解，从自然数列1、2、3… n中依次筛去前部素数及其倍数，最后只剩下自然数1和后部素数。所以 π(n,r）=j+1 当m<r<π(n)时，π(n,r)<j+1。这个结论很好理解，从自然数列1、2、3… n中依次筛去r个素数及其倍数，但是超过了m个素数，也就是自然数列1、2、 3中除了筛去了全部合数没有筛去，最后剩下自然数1和后部素数还没有
( ) 1 1 1 mm m m m i i j i jk i i j i jk i i nn n n n n p pp pp p p = + 。这个结论可以这样理解，从自然数列 1、 2、3……n 中依次筛去 r 个素数及其倍数，但是不到m n = π ( ) 个素数，也就是 自然数列 1、2、3……n 中还有合数没有筛去，最后剩下自然数 1 和后部素数还 没有筛去的合数。所以π ( ) nr j , 1 > + 当rm n = = π ( ) 时，π ( ) nr j , 1 = + 。这个结论很好理解，从自然数列 1、2、3…… n 中依次筛去前部素数及其倍数，最后只剩下自然数 1 和后部素数。所以 π ( ) nr j , 1 = + 当mr n < < π ( ) 时，π ( ) nr j , 1 < + 。这个结论很好理解，从自然数列 1、2、3…… n 中依次筛去 r 个素数及其倍数，但是超过了 m 个素数，也就是自然数列 1、2、 3……n 中除了筛去了全部合数没有筛去，最后剩下自然数 1 和后部素数还没有
筛去的合数。所以π(n,r)>j+1 当π(n)≤r时，π(n,r)=1。这个结论很好理解，从自然数列1、2、3…n中依 次筛去全部素数及其倍数，最后只剩下自然数1还没有筛去。所以π(n,r)=1 例如：计算π(20，r) 解：π(20)=8，m=πV20)=2 当r=0时，π(20，r）=20。这个结论很好理解，从自然数列1、2、3…20中不 筛去任何数，所以π(20，r)=20 当0j+1=6+1.这个结论可以这样理解， 从自然数列1、2、3…20中依次筛去素数2及其倍数，但是不到m个素数， 也就是自然数列1、2、3…20中还有合数没有筛去，最后剩下自然数1和后部 素数还没有筛去的合数。所以π(20,1)=20- 20 =10>j+1=6+1 当r=m=2时，π(20,2)=20 20 =7=j+1。这个结论很好理 解，从自然数列1、2、3…20中依次筛去前部素数及其倍数，最后只剩下自然 数1和后部素数。所以 π(20,2)=20 [引[-[兴-7=+1/=6说后的个 当m<r=4<π(20)时，π(20,4)=π(20)+1-4=5<j+1。这个结论很好理解，从 自然数列1、2、3…20中依次筛去素数2、3、5、7及其倍数，但是超过了m 个素数，也就是自然数列1、2、3…20中除了筛去了全部合数外，还筛去素数 5,7,最后剩下自然数1和后部素数中的一部分素数。所以 π(20,4)=π(20)+1-4=5<j+1 当π(20)≤r时，π(20，r）=1。这个结论很好理解，从自然数列1、2、3…20 中依次筛去全部素数及其倍数，最后只剩下自然数1还没有筛去。所以 π(20，r）=1 筛法函数有一个很好的性质，那就是递推性。下面我们就研究一下这个函数 的递推性。由公式
筛去的合数。所以π ( ) nr j , 1 > + 当π ( ) n r ≤ 时，π (n r, 1 ) = 。这个结论很好理解，从自然数列 1、2、3……n 中依 次筛去全部素数及其倍数，最后只剩下自然数 1 还没有筛去。所以π ( ) n r, 1 = 例如：计算π ( ) 20,r 解：π ( ) 20 8 = ，m = = π ( ) 20 2 当r = 0时，π ( ) 20, 20 r = 。这个结论很好理解，从自然数列 1、2、3……20 中不 筛去任何数，所以π ( ) 20, 20 r = 当0 1 += + ⎢ ⎥ ⎣ ⎦ 。这个结论可以这样理解， 从自然数列 1、2、3……20 中依次筛去素数 2 及其倍数，但是不到 m 个素数， 也就是自然数列 1、2、3……20 中还有合数没有筛去，最后剩下自然数 1 和后部 素数还没有筛去的合数。所以 ( ) 20 20,1 20 10 1 6 1 2 π j ⎡ ⎤ = − = > += + ⎢ ⎥ ⎣ ⎦ 当r m= = 2 时， ( ) 20 20 20 20,2 20 7 1 2 3 23 π j ⎡ ⎤⎡ ⎤⎡ ⎤ = − − + ==+ ⎢ ⎥⎢ ⎥⎢ ⎥ ⎣ ⎦⎣ ⎦⎣ ⎦ × 。这个结论很好理 解，从自然数列 1、2、3……20 中依次筛去前部素数及其倍数，最后只剩下自然 数 1 和后部素数。所以 ( ) 20 20 20 20,2 20 7 1, 6 2 3 23 π j j ⎡ ⎤⎡ ⎤⎡ ⎤ = − − + ==+ = ⎢ ⎥⎢ ⎥⎢ ⎥ ⎣ ⎦⎣ ⎦⎣ ⎦ × 是后部素数的个数。 当m r < < =4 20 π ( ) 时，π π ( ) 20, 4 = 20 +1 4 5 1 ( ) − =<+j 。这个结论很好理解，从 自然数列 1、2、3……20 中依次筛去素数 2、3、5、7 及其倍数，但是超过了 m 个素数，也就是自然数列 1、2、3……20 中除了筛去了全部合数外，还筛去素数 5 ， 7 ，最后剩下自然数 1 和后部素数中的一部分素数。所以 π π ( ) () 20, 4 = 20 +1 4 5 1 −=<+j 当π ( ) 20 ≤ r 时，π ( ) 20, 1 r = 。这个结论很好理解，从自然数列 1、2、3……20 中依次筛去全部素数及其倍数，最后只剩下自然数 1 还没有筛去。所以 π ( ) 20, 1 r = 筛法函数有一个很好的性质，那就是递推性。下面我们就研究一下这个函数 的递推性。由公式
品的 我们可以得到： o一含啡 (a2)- 对这个公式可以这样理解，先在自然数列中筛去素数2及其倍数：然后再在自然 数列中找出素数3的倍数的个数，共有 个3的倍数，并在素数3的倍数中 筛去素数2的倍数， 即 ✉[日}这个试子洗是长示，在白数中先游去素数 2的倍数后，素数3的倍数的个数：接着，我们在自然数列中先筛去素数2的倍 数的个数，即π(n,)再减减去素数3的倍数的个数， 就等于在自然 数列中筛去素数2、3的倍数后剩余的自然数的个数，即π(n,2) -引 …g副 即：π(m,3)=π(n,2)-元
( ) ( ) 1 1 , 1 rr r r r i i j i jk i i j i jk i i nn n n nr n p pp pp p p π = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 我们可以得到： ( ) ,1 2 n π n n ⎡ ⎤ = − ⎢ ⎥ ⎣ ⎦ ( ) ( ) ( ) () 2 2 1 2 2 2 ,2 ,1 ,1 2 2 ,2 ,1 ,1 i i n n nn n p nn n n pp p n n n p π ππ π ππ = ⎛ ⎞ ⎡ ⎤ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎢ ⎥ ⎡ ⎤ ⎡ ⎤ ⎡⎤ ⎛ ⎞ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎣ ⎦ =− =− − − = − ⎢ ⎥ ⎢ ⎥ ⎢⎥ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣⎦ ⎝ ⎠ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎢ ⎥ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ = − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ ∑ 即： 对这个公式可以这样理解，先在自然数列中筛去素数 2 及其倍数；然后再在自然 数列中找出素数 3 的倍数的个数，共有 2 n p ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 个 3 的倍数，并在素数 3 的倍数中 筛去素数 2 的倍数，即 2 ,1 n p π ⎛ ⎞ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ 这个式子就是表示，在自然数列中先筛去素数 2 的倍数后，素数 3 的倍数的个数；接着，我们在自然数列中先筛去素数 2 的倍 数的个数，即π ( ) n,1 再减减去素数 3 的倍数的个数，即 2 ,1 n p π ⎛ ⎞ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ 就等于在自然 数列中筛去素数 2、3 的倍数后剩余的自然数的个数，即π (n, 2) ( ) ( ) () () 33 3 1 2 2 3 1 1 3 3 3 ,3 ,2 ,2 ,3 ,2 ,2 i i j i jk i i j i jk i i i i nn n n n p pp pp p n nn n p n n pp p p n n n p π π π πππ = < << = = ⎡ ⎤ ⎡⎤ ⎡ ⎤ =− + − ⎢ ⎥ ⎢⎥ ⎢ ⎥ ⎣ ⎦ ⎣⎦ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎢ ⎥ ⎡⎤ ⎡⎤ ⎡⎤ ⎛ ⎞ ⎜ ⎣ ⎦⎟ ⎢ ⎥ =− − − = − ⎢⎥ ⎢⎥ ⎢⎥ ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎣⎦ ⎣⎦ ⎣⎦ ⎝ ⎠ ⎢ ⎥ ⎝ ⎠ ⎢ ⎥ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ = − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ ∑∑ ∑ ∑ ∑ 即： …………………………………………………………
-卧a n -引 副 :za=a-小}- 定理5：设p,P2,…p,是最初r个素数，那么筛法函 aa-小-- 公式π(n,r)表示从自然数列1、2、3…n中依次筛去最初r个素数 乃，P2,…p,及其倍数，剩余自然数的个数。公式π(n,r-1)表示从自然数列1、 2、3…n中依次筛去最初r一1个素数p,P2,…p,-及其倍数，剩余自然数的 *引 表示在自然数列1、2、3… 中先筛去 r一1个素数P,P2,…p,1及其倍数后，剩余的自然数个数。这个公式的意思就 是在自然数列中先筛去r一1个素数P,P2,…P及其倍数后，在剩余的自然数 中删去素数p,及其倍数的个数，也就是先在自然数列中找到素数P,的倍数的个 数 因为素数p,的p,P2,…P,倍，己经被p,P2,…P筛去，应该从总 P
( ) ( ) ( ) 1 1 11 1 1 1 1 1 , 1 1 rr r r r i i j i jk i i j i jk i i rr r r r i i j i jk i i j i jk i i r r nn n n nr n p pp pp p p nn n n n p pp pp p p n n p p π = < << = −− − − − = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− − ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤ ⎢ ⎥ − ⎣ ⎦ ∑∑ ∑ ∏ ∑∑ ∑ ∏ "" "" ( ) ( ) ( ) 11 1 1 1 1 1 1 ,1 ,1 , , rr r r rr r r i i j i jk i i j i jk i i r nn n pp p p pp pp p p n nr r p nr nr π π π π −− − − − = < << = ⎛ ⎞ ⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡⎤ ⎡⎤ ⎡⎤ ⎡⎤ ⎜ ⎟ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎣⎦ ⎣⎦ ⎣⎦ ⎣⎦ + − + +− ⎝ ⎠ ⎣ ⎦⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ = −− − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ = − ∑∑ ∑ ∏ "" 即： ( ) 1 ,1 r n r p π ⎛ ⎞ ⎡ ⎤ − − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ 定理５：设 1 2 , , r p p p "" 是最初 r 个素数，那么筛法函 () ( ) , ,1 ,1 r n nr nr r p ππ π ⎛ ⎞ ⎡ ⎤ = −− − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ 公式π ( ) n r, 表示从自然数列 1、2、3……n 中依次筛去最初 r 个素数 1 2 , , r pp p "" 及其倍数，剩余自然数的个数。公式π (n r, 1− )表示从自然数列 1、 2、3……n 中依次筛去最初 r－1 个素数 12 1 , , r p p p "" − 及其倍数，剩余自然数的 个数。公式 , 1 r n r p π ⎛ ⎞ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ − ⎝ ⎠ ⎣ ⎦ 表示在自然数列 1、2、3…… r n p ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 中先筛去 r－1 个素数 12 1 , , r p p p "" − 及其倍数后，剩余的自然数个数。这个公式的意思就 是在自然数列中先筛去 r－1 个素数 12 1 , , r p p p "" − 及其倍数后，在剩余的自然数 中删去素数 r p 及其倍数的个数，也就是先在自然数列中找到素数 r p 的倍数的个 数 r n p ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ ，因为素数 r p 的 12 1 , , r pp p "" − 倍，已经被 12 1 , , r pp p "" − 筛去，应该从总
数中减去，就是从1、2 这个数列中筛去r一1个素数p,P2,…p,及 其倍数，也就是 定理6：设，P2,P,是最初r个素数，P=PP…P,n=SP+1,那么 π(n,)=sx(P,r）+πr)=s(p,-）+π化，月 (P,月=Π(n-0 M-名 a-到 -听 -引[ Πp }名小… P mr Tin =sπ(P,r）+π(t,r)
数中减去，就是从 1、2、…… r n p ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 这个数列中筛去 r－1 个素数 12 1 , , r pp p "" − 及 其倍数，也就是 , 1 r n r p π ⎛ ⎞ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ − ⎝ ⎠ ⎣ ⎦ 。 定理 6：设 1 2 , , r p p p "" 是最初 r 个素数， P pp p = 1 2"" r ，n sP t = + ，那么 ( ) ( ) () ( ) () 1 , , , 1, r i i π ππ π nr s Pr tr s p tr = = + = −+ ∏ () ( ) 1 , 1 r i i π Pr p = = − ∏ 证明： ( ) ( ) 1 1 , 1 rr r r r i i j i jk i i j i jk i i nn n n nr n p pp pp p p π = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" ( ) ( ) ( ) 1 1 1 1 , 1 1 rr r r r i i j i jk i i j i jk i i rr r r r i i j i jk i i j i jk i i sP t sP t sP t sP t sP t r sP t p pp pp p p sP sP sP sP sP p pp pp p p π = < << = = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ ++ + + + = +− + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ + ∑∑ ∑ ∏ ∑∑ ∑ ∏ "" "" ( ) ( ) 1 1 1 1 1 1 1 rr r r r i i j i jk i i j i jk i i rr r r r i i j i jk i i j i jk i i r i i ij tt t t t p pp pp p p PP P P sP s s s s p pp pp p p t t t p pp = < << = = < << = = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤ ⎡ − + ⎢ ⎥ ⎣ ⎦ ⎣ ∑∑ ∑ ∏ ∑∑ ∑ ∏ ∑ "" "" ( ) ( ) () 1 1 , , r r r r i j i jk i jk i i t t pp p p s Pr tr π π < << = ⎡ ⎤ ⎤⎡ ⎤ ⎢ ⎥ ⎢⎥ ⎢ ⎥ − + +− ⎢ ⎥ ⎢ ⎥ ⎦⎣ ⎦ ⎢ ⎥ ⎣ ⎦ = + ∑ ∑ ∏
)-引…W a小-}[n小 (p- =x4 =Π(p-) 所以，π(n,r)=sx(P,）+x）=s(p-)+π） 定理7：设p,P2,…pn是前部素数，m=π(N,那么不超过n的素数的个数 为：π(n）=π(n,m)+m-1 证明：π(n,m)表示从自然数列1、2、3n中依次筛去前部素数p,P2,…P 及其倍数，剩余自然数的个数，也就是后部素数和1的个数，j=π(n,m)-1。 又因为π(n)=m+j, 所以，π(n）=m+j=m+π(n,m)-1=π(n,m)+m-1 推论l:设p,P2,…p,是前r个素数，π(Nn≤r≤π(n),那么不超过n的素数 的个数为：π(n)=π(n,r)+r-1 推论2：设p,P,…p,是前r个素数，πN≤r≤π(n),那么筛法函数值 π(n,r）=π(n+l-r 定理8：设n,P,…p.是前a个素数，m=π(n),a=π(n,那么不超过n
( ) ( ) ( ) 1 1 11 1 1 1 1 , 1 1 rr r r r i i j i jk i i j i jk i i rr r r r rr r ii i i r ii i i i i i i j i jk i i j i jk PP P P Pr P p pp pp p p p pp p p p pp pp p π = < << = == = = = = < << ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ = − + − + +− ⎣ ⎦⎣ ⎦ ⎣ ⎦ ∑∑ ∑ ∏ ∏∏ ∏ ∏ ∑∑ ∑ "" "" ( ) ( ) ( ) 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 r i i r rr r r i r i i i j i jk i i j i jk i i r r r i i i i r i i i i p p p pp pp p p p p p p = = = < << = = = = = ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ ⎜ ⎟ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎜ ⎟ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ − =× = − ∏ ∏ ∏ ∑∑ ∑ ∏ ∏ ∏ ∏ ∏ "" 所以， ( ) ( ) () ( ) () 1 , , , 1, r i i π ππ π nr s Pr tr s p tr = = + = −+ ∏ 定理 7：设 1 2 , , m p p p "" 是前部素数，m n = π ( ) ，那么不超过 n 的素数的个数 为：π π () ( ) n nm m = +− , 1 证明：π ( ) n m, 表示从自然数列 1、2、3……n 中依次筛去前部素数 1 2 , , m pp p "" 及其倍数，剩余自然数的个数，也就是后部素数和 1 的个数， j nm = − π ( ) , 1。 又因为π ( ) n mj = + ， 所以，π ππ () ( ) n m j m nm nm m = + = + −= + − ,1 , 1 ( ) 推论 1：设 1 2 , , r p p p "" 是前 r 个素数，π π ( nr n ) ≤ ≤ ( ) ，那么不超过 n 的素数 的个数为：π π () ( ) n nr r = , 1 + − 推论 2：设 1 2 , , r p p p "" 是前 r 个素数，π π ( nr n ) ≤ ≤ ( ) ，那么筛法函数值 π π ( ) () nr n r , 1 = +− 定理 8：设 1 2 p , , p p "" α是前 α 个素数，m n = π ( ) ， ( ) 3 α π = n ，那么不超过 n
