级数展开的筛法解释

小草

   级数展开的筛法解释
      引理
      如果在a个数中筛去p≤a^0.5的素因子后的剩余数是b,那么在na个数中筛去p≤a^0.5的素因子后的剩余数大约是nb
      证：
      由欧拉φ(p1p2)=(p1-1p2)-p1-1=p1-1p2-1，由于p1⊥a所以只能是近似，得此结论.
      证毕.   
            分配筛法
      首先我们对筛法要有一个再起码的估计，表不大于N的素数个数为π(N)，不大于N的非素数个数为g(N),我们的估计是
          π(N)≈N/lnN
           g(N)≈N(lnN)-1/lnN
      将自然数1，2，3，4，5，6，7，8，9，10进行分配，数值用四舍五入计算
      首先计算10/ln10=4
          10*((ln10)-1)/ln10=6
          π(10)=4={2,3,5,7}
           g(10)=6={1,4,6,8,9,10}
      将自然数1,2,3,...,100进行分配，数值用四舍五入计算
      将自然数100分成10段，用π(10)k表其中的一段，筛去所有p≤10^0.5的素因子，我们有
          π(10)1=4={2,3,5,7}
          π(10)2=4={11,13,17,19}
          π(10)3=3={23,25,29}
          π(10)4=3={31,35,37}
          π(10)5=4={41,43,47,49}
          π(10)6=3={53,55,59}
          π(10)7=3={61,65,67}
          π(10)8=4={71,73,77,79}
          π(10)9=3={83,85,89}
          π(10)10=4={91,95,97}
           g(10)1=6={1,4,6,8,9,10}
           g(10)2=6={12,14,15,16,18,20}
           g(10)3=7={21,22,24,26,27,28,30}
           g(10)4=7={32,33,34,36,38,39,40}
           g(10)5=6={42,44,45,46,48,50}
           g(10)6=7={51,52,54,56,57,58,60}
           g(10)7=7={62,63,64,66,68,69,70}
           g(10)8=6={72,74,75,76,78,80}
           g(10)9=7={81,82,84,86,87,88,90}
           g(10)10=6={92,93,94,96,98,99,100}
                Σ10  π(10)k=10*4-5
                Σ10   g(10)k=10*6+5
       将自然数100筛去所有pp≤100^0.5的素因子，我们有
           100/ln100=22
           100((ln100)-1)/ln100=78
78={ 1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,35,36,38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64,65, 66,68,69,70,72,74,75,76,77,78,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}
       但是在78个数中，其实还包含了素数83，89，97，所以应当是
           π(100)=(100/ln100)+3=25
            g(100)=(100((ln100)-1)/ln100)-3=75
            3*100/(ln100)^3=3
            
        所以π(100)=(100/ln100)+3*100/(ln100)^3=25
             g(100)=(100((ln100)-1)/ln100)-3*100/(ln100)^3=75
            作者施承忠     2010.4.8