论坛 › 算法交流 › 快速生成素数表的方法

lyg_wangyushi 发表于 2008-3-11 17:32:21

快速生成素数表的方法

前天在图书馆看到一本书，介绍了一种生成某一范围内素数表的新方法，跟大家分享一下，同时想向各位大虾问一下是否还有更好生成素数表的方法。书中作者给出了一个定理，将形如6n+-1的数中的含有小于等于sqrt(6n+1)因子的数划去，剩下的数加上2和3，就是1到6*n+1中的所有的素数，由此也能够引出一个关于孪生素数的定理：即任意孪生素数的和为6的倍数。用这个算法求一定范围内的素数的效率大概是普通筛法的4-7倍，
例如求100以内的素数，100以内形如6n+-1的数由：5，7，11，13，17，19，23，25，29，31，35，37，41，43，47，49，63，55，59，61，65，67，71，73，77，79，83，85，89，91，95，97
小于sqrt(100)的素数有2，3，5，7那么在上面的数中由于没有偶数，可以划去5的倍数（5本身不划）：25，35，55，65，85，95；划去7的倍数：49，77，91；那么剩下的数加上2和3就是100以内的素数，用同样的方法可以求得更大范围内的素数，我用程序验证了一下，这种方法确实比普通的方法效率提高了4-7倍，例如求10000以内的素数sqrt(10000)=100,则只要找到100以内的素数，101到10000之间形如6n+-1的数用100以内的素数验证即可，而100以内的素数可以用上面的方法求，只要最后问题在一个较小的范围就可以直接求解，然后不断生成大范围的素数，不知道各位是否还有更好的生成素数表的方法，如果有希望能够讲解一下。

gxqcn 发表于 2008-3-11 22:54:25

这即普通的Eratosthenes筛法，通过简单的加减，替换费时的乘除运算，从而提高搜索效率。
该法在小数字范围内比较有效。

liangbch 发表于 2008-3-12 09:53:20

此法相对于普通筛法，只少了一次 筛去2的倍数的过程和 3的倍数的过程，当n较大时，减少的工作量所占比重并不大，没有什么特别的创造性。

liangbch 发表于 2008-3-12 10:01:47

至于筛素数，gxq应该有很快的算法，我只提一点。对于筛较大范围的素数，需采用分段筛的方法，基于cache的特性，在分段的时候，每段的大小不能超过L2 cache, 否则cache的命中率会大为降低，速度大打折扣。

无心人 发表于 2008-3-12 11:53:40

预先计算的筛法
m = 2 * 3 * 5 * 7 * 11 * 13 * 17

将要筛选的范围设为m * k--m *k + m(m-1)
则可预先计算出m应该保留的数字,消掉2, 3, 5, 7, 11, 13, 17的倍数就是了, 保存到文件

操作时, 从文件拷贝到内存
每次都拷贝到工作区t
1、对p > 17这么做
n = * p;
如果n为偶, 则n = n + p, 否则n = n + 2 * p
2、 n = n - m * k
3、t置否标志
4、n = n + 2 * p
5、如果n < m转3

重复直到p <= sqrt(m * k)
后面的 sqrt(m * k) < p < sqrt(m * k + m)
从p * p位置开始标记

lyg_wangyushi 发表于 2008-3-12 20:05:46

对了，我也想到了用素数乘积来减小筛选的范围，及2*3*5*7*11*13*17*19*……*Pn,
其中Pn代表第n 个素数，那么可以证明筛选的个数占总共数字的比重是(1-1/p_1)(1-1/p_2)(1-1/p_3)\cdots(1-1/p_n)
而可以证明$(1-1/p_1)(1-1/p_2)\cdots(1-1/p_n)$是随n增大是收敛的，
问一下，这个极限可以用数学方法精确求得吗？

lyg_wangyushi 发表于 2008-3-12 20:23:36

按照上面的想到的方法，生成素数表则可表述为已经求得$p_1,p_2,p_3,\cdots,p_n$,然后求得
范围为$p_n$到$p_1*p_2*p_3*p_4\cdotsp_n$范围内的素数，然后需要筛选的数可以表示为
$p_1*p_2*p_3\cdotsp_n*k+r$，其中k取1，2，3，...r取小于$p_1*p_2*p_3\cdotsp_n$且与
其互素的数，可以证明其个数占1到$p_1*p_2*p_3\cdotsp_n$的比重为(1-1/p_1)(1-1/p_2)(1-1/p_3)\cdots(1-1/p_n)，
这个序列是收敛的，请问一下它的极限可以用数学方法精确求得吗？

mathe 发表于 2008-3-12 20:46:21

这个无限乘积是发散的，也就是乘积是0。

lyg_wangyushi 发表于 2008-3-12 21:11:15

以0为极限也是收敛的吧？以0为极限（mathe可以详细讲解一下吗？这个式子收敛的很慢阿）
下面是一些测试数据，其中编号为第r个素数的上述表达式的值：
    1:0.50000000000000000   2:0.33333333333333337   3:0.26666666666666672
    4:0.22857142857142862   5:0.20779220779220783   6:0.19180819180819186
    7:0.18052535699594527   8:0.17102402241721132   9:0.16358819535559344
   10:0.15794722310195228    11:0.15285215138898609    12:0.14872101216225675
   13:0.14509367040220170    14:0.14171939899749933    15:0.13870409263585040
   16:0.13608703428423058    17:0.13378047438110804    18:0.13158735185027021
   19:0.12962336152414677    20:0.12779768037591935    21:0.12604702722008482
   22:0.12445149522995717    23:0.12295207962477696    24:0.12157059558404912
   25:0.12031729047493521    26:0.11912603017320318    27:0.11796946677346334
   28:0.11686694839240294    29:0.11579477455394054    30:0.11477004203576407
   31:0.11386634091737223    32:0.11299713220807932    33:0.11217233562261889
   34:0.11136534040231227    35:0.11061792201035045    36:0.10988535299041435
   37:0.10918544628346905    38:0.10851559691976678    39:0.10786580292623524
   40:0.10724230117521653    41:0.10664318217423767    42:0.10605399332244630
   43:0.10549873681290471    44:0.10495211123356324    45:0.10441935939989033
   46:0.10389463900089591    47:0.10340224734686322    48:0.10293856013902976
   49:0.10248508630581817    50:0.10203755317784516    51:0.10159962376506471
   52:0.10117452073675900    53:0.10075470944739486    54:0.10035329626234547
   55:0.09996281651035191    56:0.09958272975555969    57:0.09921253373416356
   58:0.09884643582370539    59:0.09848958948499165    60:0.09813909272525859
   61:0.09779231147887958    62:0.09745854932366156    63:0.09714109476560404
   64:0.09682874397857637    65:0.09651938696906015    66:0.09621490940764356
   67:0.09592422992302832    68:0.09563958829120925    69:0.09536396988114812
   70:0.09509072068378094    71:0.09482134187164558    72:0.09455721557116746
   73:0.09429956648241768    74:0.09404675263125838    75:0.09379860816521284
   76:0.09355370318305824    77:0.09331320523143083    78:0.09307815937442471
   79:0.09284604426376530    80:0.09261903682057762    81:0.09239798900000344
   82:0.09217851634204619    83:0.09196464507443124    84:0.09175225559388983
   85:0.09154325273376708    86:0.09133660882240417    87:0.09113318653104024
   88:0.09093377036795264    89:0.09073651706997443    90:0.09054054187111919
   91:0.09034666490779773    92:0.09015804974097560    93:0.08997292027538839
   94:0.08978967603857498    95:0.08960973680803674    96:0.08943158623784184
   97:0.08925588567548852    98:0.08908456919626492    99:0.08891423541195084
100:0.08874988377532986   101:0.08858763535892159   102:0.08842859113027002
103:0.08827152436094450   104:0.08811638987173370   105:0.08796207044989179
106:0.08780962318741364   107:0.08766003268794616   108:0.08751220801224979
109:0.08736611083693718   110:0.08722074293205043   111:0.08707705142804376
112:0.08693500077318561   113:0.08679410125815613   114:0.08665388461638206
115:0.08651655674852726   116:0.08638158552115047   117:0.08624724401956237
118:0.08611394070577634   119:0.08598206637085172   120:0.08585159282552418
121:0.08572171144454760   122:0.08559433891639820   123:0.08546790710115980
124:0.08534277107319324   125:0.08521926489219006   126:0.08509769675397010
127:0.08497767179380934   128:0.08485948309868582   129:0.08474275753733963
130:0.08462714668121775   131:0.08451263092116197   132:0.08439888579206216
133:0.08428650378701282   134:0.08417516098148176   135:0.08406454973183461
136:0.08395523302217033   137:0.08384662340635898   138:0.08374008385946399
139:0.08363501474546216   140:0.08353163401030089   141:0.08342863569462851
142:0.08332701738074955   143:0.08322576948599772   144:0.08312513373087560
145:0.08302486215822075   146:0.08292590523073777   147:0.08282868846024452
148:0.08273203888211121   149:0.08263572684615998   150:0.08253997281736954
151:0.08244585654277734   152:0.08235227441276283   153:0.08225901022882991
154:0.08216627177310405   155:0.08207568051425829   156:0.08198558646319983
157:0.08189637472602551   158:0.08180821931727844   159:0.08172091065205189
160:0.08163406590109329   161:0.08154786308599182   162:0.08146229345001492
163:0.08137805116102835   164:0.08129424266343718   165:0.08121103463614605
166:0.08112841913804214   167:0.08104655393205018   168:0.08096526350684251
169:0.08088502043101808   170:0.08080517342170809   171:0.08072587491982221
172:0.08064680942039045   173:0.08056858749078774   174:0.08049059273039007
175:0.08041312343998545   176:0.08033646650629624   177:0.08026002838402574
178:0.08018438273993146   179:0.08010895058307357   180:0.08003401236924469
181:0.07996038402299883   182:0.07988709311188701   183:0.07981400336521556
184:0.07974124675321445   185:0.07966895187855151   186:0.07959711332861594
187:0.07952585360316508   188:0.07945503806122103   189:0.07938466158818186
190:0.07931569142172819   191:0.07924690070930691   192:0.07917876063990940
193:0.07911114427727925   194:0.07904415770295471   195:0.07897756616318812
196:0.07891136535332795   197:0.07884566063613117   198:0.07878066009150123
199:0.07871592659923211   200:0.07865156361754837   201:0.07858756722729812
202:0.07852372679900625   203:0.07846024763425362   204:0.07839742918138393
205:0.07833515957917472   206:0.07827381646282454   207:0.07821261723181373
208:0.07815165650131349   209:0.07809102682210378   210:0.07803053803293097
211:0.07797037570599734   212:0.07791044459477059   213:0.07785065146768327
214:0.07779108708247465   215:0.07773210976095647   216:0.07767326637733728
217:0.07761473339589241   218:0.07755770567113422   219:0.07750096996837552
220:0.07744452352265929   221:0.07738844493936989   222:0.07733312796657549
223:0.07727824285091432   224:0.07722393628531284   225:0.07716982000200147
226:0.07711581732880203   227:0.07706200308084055   228:0.07700845061170862
229:0.07695523122635153   230:0.07690219522964144   231:0.07684926873602159
232:0.07679659617348833   233:0.07674438910606923   234:0.07669256980214886
235:0.07664085532487162   236:0.07658931473622006   237:0.07653787799025887
238:0.07648661350399613   239:0.07643558841159853   240:0.07638500231734863
241:0.07633484801510480   242:0.07628498854546724   243:0.07623554914913187
244:0.07618633317163082   245:0.07613727564866132   246:0.07608843839680202
247:0.07603988163968854   248:0.07599147942349523   249:0.07594335309073810
250:0.07589537876787598   251:0.07584785504917349   252:0.07580047974933016
253:0.07575331081358074   254:0.07570622982488368   255:0.07565929477849503
256:0.07561256266312845   257:0.07556591703532886   258:0.07551947209554071
259:0.07547333924758985   260:0.07542779106457984   261:0.07538243460573162
262:0.07533721418905151   263:0.07529207505532530   264:0.07524760247702918
265:0.07520326093166853   266:0.07515899768215018   267:0.07511501933359420
268:0.07507137318639280   269:0.07502780303364388   270:0.07498450943697127
271:0.07494143964407238   272:0.07489854242618796   273:0.07485581650352613
274:0.07481326061011878   275:0.07477115973189137   276:0.07472922414034236
277:0.07468740588396836   278:0.07464565775323388   279:0.07460421096936201
280:0.07456301593293498   281:0.07452211466253841   282:0.07448141443607061
283:0.07444108881915883   284:0.07440108823408674   285:0.07436123762442734
286:0.07432149351025073   287:0.07428181305455919   288:0.07424223830066758
289:0.07420272673158793   290:0.07416344524575860   291:0.07412443238660775
292:0.07408556273144959   293:0.07404683530712578   294:0.07400848893979946
295:0.07397020208571782   296:0.07393224918572515   297:0.07389435464488162
298:0.07385690185489435   299:0.07381958154066752   300:0.07378243026661585
301:0.07374540947872492   302:0.07370848138184023   303:0.07367160870481081
304:0.07363482807140850   305:0.07359821204551521   306:0.07356172309556701
307:0.07352543216162741   308:0.07348919488604258   309:0.07345315310336184
310:0.07341737465567388   311:0.07338178698012582   312:0.07334631970753996
313:0.07331107399888664   314:0.07327587905217570   315:0.07324076842493460
316:0.07320570821984847   317:0.07317083175094906   318:0.07313617005897798
319:0.07310155757906364   320:0.07306722147874468   321:0.07303293371643650
322:0.07299875826780924   323:0.07296466263106576   324:0.07293061472503166
325:0.07289674077485747   326:0.07286300790082931   327:0.07282956916383948
328:0.07279650989504065   329:0.07276352552263692   330:0.07273064548399134
331:0.07269789868278288   332:0.07266540073969714   333:0.07263294634008137
334:0.07260056428642997   335:0.07256831170345066   336:0.07253630097927621
337:0.07250433257866834   338:0.07247243450010316   339:0.07244066227980500
340:0.07240898730722965   341:0.07237740903103811   342:0.07234589949293144
343:0.07231456735802760   344:0.07228327589660050   345:0.07225229292364868
346:0.07222140267442952   347:0.07219055201117688   348:0.07215979336098038
349:0.07212910012688384   350:0.07209849804791613   351:0.07206808957130377
352:0.07203777064426493   353:0.07200751538569951   354:0.07197729821600345
355:0.07194716958552375   356:0.07191710390663302   357:0.07188712595585910
358:0.07185730964480316   359:0.07182757968632372   360:0.07179793561711764
361:0.07176847401038103   362:0.07173907275105683   363:0.07170975559831835
364:0.07168059343662729   365:0.07165153766304130   366:0.07162256413386094
367:0.07159364908980205   368:0.07156504595392918   369:0.07153665839107558
370:0.07150839420364331   371:0.07148023020435082   372:0.07145212158059763
373:0.07142409014804346   374:0.07139609168071770   375:0.07136816986152304
376:0.07134049705428709   377:0.07131296309170343   378:0.07128546098484200
379:0.07125813807913681   380:0.07123090913833469   381:0.07120373214133417
382:0.07117668932624062   383:0.07114979975717140   384:0.07112302151112053
385:0.07109627347745708   386:0.07106957566541147   387:0.07104296781229826
388:0.07101642953519242   389:0.07098996049697580   390:0.07096354071264495
391:0.07093715040371500   392:0.07091080909275929   393:0.07088453609939406
394:0.07085835045620995   395:0.07083221310819954   396:0.07080610466252751
397:0.07078006343241992   398:0.07075412716879501   399:0.07072821939612244
400:0.07070241559481046   401:0.07067669627302260   402:0.07065102366268006
403:0.07062549022442105   404:0.07060005792689696   405:0.07057474417360657
406:0.07054945762965328   407:0.07052423436986435   408:0.07049905613553023
409:0.07047390484900311   410:0.07044890523749230   411:0.07042403799243847
412:0.07039921457404143   413:0.07037445227556305   414:0.07034976814638888
415:0.07032514449635514   416:0.07030056387961402   417:0.07027614548299033
418:0.07025180320883619   419:0.07022755336306165   420:0.07020336199090765
421:0.07017922883106204   422:0.07015517013074285   423:0.07013120184576481
424:0.07010733957905989   425:0.07008359852264978   426:0.07005989761006180
427:0.07003625269017991   428:0.07001266351783562   429:0.06998909816491815
430:0.06996576068637032   431:0.06994244653752448   432:0.06991921756159039
433:0.06989605783401119   434:0.06987293641229964   435:0.06984992918924653
436:0.06982695979457726   437:0.06980405820067939   438:0.06978125386934954
439:0.06975850158572731   440:0.06973584536566049   441:0.06971322588938231
442:0.06969065767122454   443:0.06966824189198001   444:0.06964590516806465
445:0.06962358991488681   446:0.06960139559231272   447:0.06957939072491079
448:0.06955742059837940   449:0.06953547127032690   450:0.06951361164402375
451:0.06949180003070590   452:0.06947002259415601   453:0.06944833354557838
454:0.06942669180873026   455:0.06940511061761781   456:0.06938356292726772
457:0.06936207529551570   458:0.06934073968330545   459:0.06931942374734379
460:0.06929814053464888   461:0.06927687691374226   462:0.06925569780126481
463:0.06923470486467757   464:0.06921373100679672   465:0.06919280154474446
466:0.06917191630431441   467:0.06915107511229744   468:0.06913026527928140
469:0.06910949920379950   470:0.06908875183087730   471:0.06906808513873525
472:0.06904744932005023   473:0.06902689336609964   474:0.06900635576021862
475:0.06898588517114707   476:0.06896543278894395   477:0.06894508300057306
478:0.06892475121555372   479:0.06890452088059172   480:0.06888433203767330
481:0.06886426669190060   482:0.06884430024751327   483:0.06882438578403409
484:0.06880450009036636   485:0.06878463162369285   486:0.06876479181070649
487:0.06874496915524074   488:0.06872527709876544   489:0.06870563569347857
490:0.06868606701341776   491:0.06866653728154018   492:0.06864706845894830
493:0.06862761618678652   494:0.06860819144402207   495:0.06858880512261940
496:0.06856943522566300   497:0.06855010355517367   498:0.06853083166775305
499:0.06851157602525017   500:0.06849239048169788   501:0.06847326387167785
502:0.06845415327612338   503:0.06843510118781943   504:0.06841612832915910

lyg_wangyushi 发表于 2008-3-12 21:12:31

测试数据续：
505:0.06839719222942781   506:0.06837828230622366   507:0.06835940891889100
508:0.06834058231219344   509:0.06832179194037265   510:0.06830303767412495
511:0.06828437054166413   512:0.06826576951454845   513:0.06824718368021288
514:0.06822862311897268   515:0.06821013798672695   516:0.06819168785473162
517:0.06817326264861037   518:0.06815488215180568   519:0.06813655602054679
520:0.06811827414342832   521:0.06810002654789030   522:0.06808181311474029
523:0.06806371106392542   524:0.06804564265111313   525:0.06802758862016298
526:0.06800958714130080   527:0.06799165685204657   528:0.06797375017391856
529:0.06795587645575556   530:0.06793809161501864   531:0.06792032073047377
532:0.06790260084507578   533:0.06788495005203053   534:0.06786732217614062
535:0.06784970802556285   536:0.06783214403176903   537:0.06781464799255527
538:0.06779717449397435   539:0.06777974143290622   540:0.06776239314996972
541:0.06774506704586591   542:0.06772777190493003   543:0.06771049000344880
544:0.06769323012835232   545:0.06767600100386050   546:0.06765878502802639
547:0.06764162581295460   548:0.06762448833491737   549:0.06760744157708150
550:0.06759049310839835   551:0.06757359970847122   552:0.06755671896909864
553:0.06753985929378815   554:0.06752302902733069   555:0.06750622807459933
556:0.06748943965677426   557:0.06747268042169684   558:0.06745601638602836
559:0.06743936469104292   560:0.06742274172710626   561:0.06740618814455603
562:0.06738966296972285   563:0.06737319030705609   564:0.06735672971817090
565:0.06734029723958633   566:0.06732391672456818   567:0.06730760368441199
568:0.06729130249679165   569:0.06727502102994026   570:0.06725876709879024
571:0.06724257187435036   572:0.06722639612937216   573:0.06721023205239948
574:0.06719414150127370   575:0.06717814670443931   576:0.06716219368931120
577:0.06714626715535595   578:0.06713035194626485   579:0.06711447813402879
580:0.06709861557715476   581:0.06708279416343697   582:0.06706698393620071
583:0.06705121460068785   584:0.06703547118331271   585:0.06701973885024927
586:0.06700404703595514   587:0.06698836623861464   588:0.06697272571416015
589:0.06695711071632518   590:0.06694152842386153   591:0.06692605776788191
592:0.06691062635036568   593:0.06689520560218629   594:0.06687982385796872
595:0.06686447388692030   596:0.06684914854337527   597:0.06683386174974541
598:0.06681864110256942   599:0.06680344468658066   600:0.06678829307744330
601:0.06677318602178226   602:0.06675808921282413   603:0.06674305699278071
604:0.06672804843487813   605:0.06671305673673504   606:0.06669808858400075
607:0.06668314390809128   608:0.06666826259947532   609:0.06665339124935275
610:0.06663855630805532   611:0.06662377073975977   612:0.06660900810498473
613:0.06659426181140381   614:0.06657952530735171   615:0.06656480509392979
616:0.06655016581416424   617:0.06653553618879292   618:0.06652094826154259
619:0.06650638269371655   620:0.06649187115483508   621:0.06647738806375365
622:0.06646292702654161   623:0.06644848798091342   624:0.06643410830379139
625:0.06641978134491629   626:0.06640546365115796   627:0.06639116137598003
628:0.06637688063573997   629:0.06636260910689978   630:0.06634835902978857
631:0.06633413034460096   632:0.06631993515300144   633:0.06630576119806385
634:0.06629162652289905   635:0.06627753091870536   636:0.06626349204327246
637:0.06624946208518581   638:0.06623545289464126   639:0.06622145850357965
640:0.06620752007830000   641:0.06619360801272356   642:0.06617976866335858
643:0.06616594376913185   644:0.06615212753531077   645:0.06613832571441879
646:0.06612454402537639   647:0.06611077094809553   648:0.06609703507214539
649:0.06608331345390330   650:0.06606963444056156   651:0.06605604266223600
652:0.06604248157772312   653:0.06602893995755135   654:0.06601543434496032
655:0.06600197005078431   656:0.06598852495605000   657:0.06597510992759786
658:0.06596173026628624   659:0.06594835874180494   660:0.06593500075947928
661:0.06592166169398070   662:0.06590834687642991   663:0.06589505086132472
664:0.06588178429179355   665:0.06586852573186362   666:0.06585528050247858
667:0.06584207511236379   668:0.06582888823571401   669:0.06581571982438460
670:0.06580256457357021   671:0.06578942770701531   672:0.06577629870527772
673:0.06576319846653937   674:0.06575010605195317   675:0.06573705780705300
676:0.06572404314504407   677:0.06571105163621920   678:0.06569810874639524
679:0.06568517859312888   680:0.06567226623248544   681:0.06565938679215744
682:0.06564651492648557   683:0.06563366070386437   684:0.06562082407943568
685:0.06560800500850787   686:0.06559525816471372   687:0.06558252863663984
688:0.06556983606287621   689:0.06555715576195514   690:0.06554449749669893
691:0.06553186606530623   692:0.06551925650862635   693:0.06550667842137185
694:0.06549414605511561   695:0.06548162566779862   696:0.06546911245823092
697:0.06545661119558853   698:0.06544416933829987   699:0.06543175815503829
700:0.06541936342911388   701:0.06540697574431381   702:0.06539462781610080
703:0.06538229618724617   704:0.06536998081783814   705:0.06535770015264598
706:0.06534544481790894   707:0.06533322386320202   708:0.06532101432781365
709:0.06530887513169252   710:0.06529675170954073   711:0.06528464402333463
712:0.06527255203518435   713:0.06526048017425681   714:0.06524842392445555
715:0.06523637880281545   716:0.06522434034944716   717:0.06521233071211528
718:0.06520033653688775   719:0.06518835338369222   720:0.06517637683521092
721:0.06516441567227549   722:0.06515250479388539   723:0.06514060913845469
724:0.06512871999643272   725:0.06511684169623275   726:0.06510500442270135
727:0.06509317360234469   728:0.06508135352360811   729:0.06506956128705736
730:0.06505777545817001   731:0.06504600455615117   732:0.06503424429497667
733:0.06502254117381508   734:0.06501085277885305   735:0.06499917907571445
736:0.06498751584602205   737:0.06497587142461979   738:0.06496424991300745
739:0.06495269660518013   740:0.06494117812732853   741:0.06492966577524072
742:0.06491816769382135   743:0.06490667978589464   744:0.06489519797450495
745:0.06488372631143716   746:0.06487226072983061   747:0.06486081739578055
748:0.06484940426584991   749:0.06483800517914472   750:0.06482661610393320
751:0.06481524500831770   752:0.06480389581465490   753:0.06479256051715365
754:0.06478126671193889   755:0.06476998274281993   756:0.06475870466816508
757:0.06474744032572846   758:0.06473623640803929   759:0.06472504217729261
760:0.06471386534389988   761:0.06470270970429569   762:0.06469156751216476
763:0.06468043873743361   764:0.06466932716919148   765:0.06465822894932376
766:0.06464715543862855   767:0.06463609140381105   768:0.06462504061027304
769:0.06461399548284007   770:0.06460296355600331   771:0.06459194104046739
772:0.06458093167604938   773:0.06456992793918176   774:0.06455894479103766
775:0.06454796724558773   776:0.06453702134644485   777:0.06452608842736193
778:0.06451519427095009   779:0.06450430930481699   780:0.06449344816501150
781:0.06448261439243212   782:0.06447183314943054   783:0.06446106451185757
784:0.06445033352059540   785:0.06443961145546139   786:0.06442892318021583
787:0.06441825083912253   788:0.06440759086049618   789:0.06439693969614022
790:0.06438630084933762   791:0.06437568830593078   792:0.06436508799499617
793:0.06435449989037452   794:0.06434393091354904   795:0.06433336714226132
796:0.06432282241727487   797:0.06431230011686308   798:0.06430179328789447
799:0.06429130530986675   800:0.06428082246210712   801:0.06427035838552204
802:0.06425990961973022   803:0.06424948289417128   804:0.06423907474855421
805:0.06422870859158333   806:0.06421834745130400   807:0.06420799466274181
808:0.06419765687580530   809:0.06418733072864818   810:0.06417701288091814
811:0.06416670994097899   812:0.06415643833701853   813:0.06414618479085631
814:0.06413594270482871   815:0.06412571205517090   816:0.06411548629978019
817:0.06410527194797204   818:0.06409507546762402   819:0.06408490003097254
820:0.06407472943899810   821:0.06406457657424783   822:0.06405443496009962
823:0.06404430457342239   824:0.06403418539115451   825:0.06402408058045683
826:0.06401398692121350   827:0.06400391073879240   828:0.06399384564825320
829:0.06398378530465183   830:0.06397373602158216   831:0.06396369777648227
832:0.06395367054685748   833:0.06394366058120607   834:0.06393366469867032
835:0.06392370773484869   836:0.06391376161570526   837:0.06390385096884285
838:0.06389394493086907   839:0.06388406798776644   840:0.06387419867400346
841:0.06386434306550570   842:0.06385450415885564   843:0.06384471202510945
844:0.06383493338947995   845:0.06382518313235615   846:0.06381544031704056
847:0.06380570196204025   848:0.06379597992913426   849:0.06378626825613545
850:0.06377656101701566   851:0.06376686410945644   852:0.06375717456924834
853:0.06374751292739818   854:0.06373786444655553   855:0.06372823491574324
856:0.06371863295176618   857:0.06370905552309464   858:0.06369948816230125
859:0.06368992511048287   860:0.06368038068891678   861:0.06367084627048754
862:0.06366132753132317   863:0.06365181306001375   864:0.06364231420714700
865:0.06363281960559439   866:0.06362333491046759   867:0.06361386574319412
868:0.06360441767164457   869:0.06359497661217127   870:0.06358557046269454
871:0.06357616848569281   872:0.06356679008644725   873:0.06355741583632391
874:0.06354805677052559   875:0.06353870183798172   876:0.06352936203174359
877:0.06352005097179463   878:0.06351074673113669   879:0.06350144657785932
880:0.06349215322990412   881:0.06348287210825086   882:0.06347361399652442
883:0.06346436532772119   884:0.06345512608396989   885:0.06344589087423565
886:0.06343667310714655   887:0.06342747805378995   888:0.06341829498182618
889:0.06340911855367080   890:0.06339995141205541   891:0.06339082517750640
892:0.06338170288290609   893:0.06337259500779718   894:0.06336349105793254
895:0.06335439625513967   896:0.06334530797565965   897:0.06333622881441905
898:0.06332715875444277   899:0.06331810037098483   900:0.06330905104979417
901:0.06330000819148110   902:0.06329098209591694   903:0.06328196500201526
904:0.06327295945697441   905:0.06326397054385366   906:0.06325498801218479
907:0.06324602457332802   908:0.06323707761837352   909:0.06322814456601890
910:0.06321924295478899   911:0.06321035010868478   912:0.06320147349723854
913:0.06319260560422643   914:0.06318374144296900   915:0.06317490579180930
916:0.06316608124846640   917:0.06315728006674026   918:0.06314849235558585
919:0.06313971319635388   920:0.06313095230927238   921:0.06312219749685949
922:0.06311344632571062   923:0.06310470364025200   924:0.06309597425809123
925:0.06308725573187068   926:0.06307854563167299   927:0.06306984154092762
928:0.06306114585065589   929:0.06305248717348294   930:0.06304384629542710
931:0.06303521842539898   932:0.06302659409670486   933:0.06301798508234935
934:0.06300938898562553   935:0.06300079640564657   936:0.06299222370236644
937:0.06298365449767288   938:0.06297510738754970   939:0.06296658918013898
940:0.06295809281133853   941:0.06294960446122240   942:0.06294113552479549
943:0.06293268818409964   944:0.06292424877305175   945:0.06291581275632389
946:0.06290739817657849   947:0.06289898922080031   948:0.06289058812700830
949:0.06288219039858969   950:0.06287380498848187   951:0.06286542963148327
952:0.06285706653056117   953:0.06284871121133605   954:0.06284036366037160
955:0.06283202607729341   956:0.06282369402238328   957:0.06281536969562795
958:0.06280704867699030   959:0.06279873976725661   960:0.06279043415427324
961:0.06278214279891152   962:0.06277385691494704   963:0.06276557867982704
964:0.06275730808044902   965:0.06274904074965196   966:0.06274078755476183
967:0.06273253978460872   968:0.06272430824809322   969:0.06271609718535620
970:0.06270789149424207   971:0.06269969331258508   972:0.06269151757998467
973:0.06268334717498272   974:0.06267518634342759   975:0.06266703294335689
976:0.06265888484389734   977:0.06265074626942742   978:0.06264261297768790
979:0.06263449549511985   980:0.06262638537010429   981:0.06261828049300190
982:0.06261019132099660   983:0.06260211571267453   984:0.06259404530972072
985:0.06258597802717017   986:0.06257794285217631   987:0.06256991283256227
988:0.06256190849421860   989:0.06255391131813599   990:0.06254592129242158
991:0.06253794451378461   992:0.06252998094005306   993:0.06252203255045855
994:0.06251409122789403   995:0.06250615494615887   996:0.06249822168623424
997:0.06249029345818828   998:0.06248238429561921   999:0.06247448213496465

查看完整版本: 快速生成素数表的方法