筛去的合数。所以π(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 当0<r=1<m时，π(20，)=20 [9 =10>j+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 < =< r m时， ( ) 20 20,1 20 10 1 6 1 2 π j ⎡ ⎤ = − = > += + ⎢ ⎥ ⎣ ⎦ 。这个结论可以这样理解， 从自然数列 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 π π π πππ = < << = = ⎡ ⎤ ⎡⎤ ⎡ ⎤ =− + − ⎢ ⎥ ⎢⎥ ⎢ ⎥ ⎣ ⎦ ⎣⎦ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎢ ⎥ ⎡⎤ ⎡⎤ ⎡⎤ ⎛ ⎞ ⎜ ⎣ ⎦⎟ ⎢ ⎥ =− − − = − ⎢⎥ ⎢⎥ ⎢⎥ ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎣⎦ ⎣⎦ ⎣⎦ ⎝ ⎠ ⎢ ⎥ ⎝ ⎠ ⎢ ⎥ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ = − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ ∑∑ ∑ ∑ ∑ 即： …………………………………………………………