|
同余筛法(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
|
|