素数的个数公式 作者姓名：弯国强 作者地址：漯河市舞阳县莲花镇第二初级中学 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 = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− − ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 又因为 ( ) 1 1 1 10 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 = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− − ≥ ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" ，故 ( ) 1 1 1 1 mm m m m i i j i jk i i j i jk i i nn n n n p pp pp p p = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ − + − + +− ≥ ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 当m n = π ( ) 时，有容斥原理可以知道这个公式表示 n 减去 n 以内的全部质数倍数 的个数也就是只剩下 1。故 ( ) 1 1 1 1 mm m m m i i j i jk i i j i jk i i nn n n n p pp pp p p = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ − + − + +− = ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" 当π π ( ) nm n < < ( )时，有容斥原理可以知道这个公式表示 n 减去 n 以内 m 个 质数倍数的个数也就是还剩有质数和 1。故 ( ) 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 当0<r<m=πVn时，π(n,r）>j+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 , , r pp p "" 是最初 r 个素数，不大于 n 且不能被任何一个素数 ( ) 1, 2 i pi r = "" 整除的自然数个数记为π (n r, ) ，那么： ( ) ( ) 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 π = < << = ⎡ ⎤ ⎡⎤ ⎡ ⎤ ⎢ ⎥ ⎡ ⎤ = − + − + +− ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣⎦ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ∑∑ ∑ ∏ "" π ( ) n r, 这个函数我们把它叫筛法函数。它表示从自然数列 1、2、3……n 中依 次筛去最初 r 个素数 1 2 , , r pp p "" 及其倍数，剩余自然数的个数。 当r = 0时，π ( ) nr n , = 。这个结论很好理解，从自然数列 1、2、3……n 中不筛 去任何数，所以π ( ) nr n , = 当0 << = rm n π ( ) 时，π ( ) nr j , 1 > + 。这个结论可以这样理解，从自然数列 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 和后部素数还没有