同余筛法(2)

小草

                  同余筛法(2)

                 素数的同余筛法

命a1，a2，a3，... ，an=0. 这样筛剩后的集合N中的数都是素数用P表示，不大于x的素数个数用π(x)表示.
再命p1*p2*p3*...*pn=mn
    在不大于mn个自然数中筛去p1,p2,p3,...,pn的合数及p1,p2,p3,...,pn本数后所剩下的数的个数是
          (p1-1)(p2-1)(p3-1)...(pn-1)= φ(mn) 个.
    当n=1时m1=2
      筛去2
      剩下数1
      所以φ(m1)= 1
    当n=2时m2=6
      筛去2，3，4，6
      剩下数1，5
      所以φ(m2)=2
    当n=3时m3=30
      筛去2，3，4，5，6，8，9，10，12，14，15，16，18，20，21，22，24，25，26，27，28，30
      剩下数1，7，11，13，17，19，23，29
      所以φ(m3)=8
    这样可以一直做下去.
    命π(x)为不大于x的素数个数.   
       根据已有的资料
       我们有
       φ(m1)= 1
       π(m1)=0
       φ(m2)=2
       π(m2)=3
       φ(m3)=8
       π(m3)=10
       φ(m4)=48
       π(m4)=46
       φ(m5)=480
       π(m5)=343
       φ(m6)=5760
       π(m6)=3248
       φ(m7)=92160
       π(m7)=8899
      
       命φ(mn)=(mn)^t
       π(mn)=(mn)^s

       我们有
       φ(m1）=φ(2）=2^0=1
       π(m1)=π(2)=2^0=1
       φ(m2)=φ（6）=6^0.386852807=2
       π(m2)= π(6)=6^0.613147192=3
       φ(m3)=φ（30）=30^0.611385141=8
       π(m3)= π(30)=30^0.676992492=10
       φ(m4)=φ（210）=210^0.723980392=48
       π(m4)= π(210)=210^0.716021021=46
       φ(m5)=φ（2310）=2310^0.797131551=480
       π(m5)= π(2310)=2310^0.753741553=343
       φ(m6)=φ（30030）=30030^0.839838305=5760
       π(m6)= π(30030)=30030^0.784270826=3248
       我们从这里可以看出当x趋向无穷时不管t和s趋向的形式不同，但是他们都趋向1
         作者施承忠 2011.4.5