快速生成素数表的方法

lyg_wangyushi

1000:0.06246659294666625  1001:0.06245871271543797  1002:0.06245083943764704
1003:0.06244297111971361  1004:0.06243511566983064  1005:0.06242726318389556
1006:0.06241942351754068  1007:0.06241161425649758  1008:0.06240382157148616
1009:0.06239603180471903  1010:0.06238824883954443  1011:0.06238048814184079
1012:0.06237274189967740  1013:0.06236500238585439  1014:0.06235727342286197
1015:0.06234955689354346  1016:0.06234184704355044  1017:0.06233414005294053
1018:0.06232643782384712  1019:0.06231874415172962  1020:0.06231106091363917
1021:0.06230338430147782  1022:0.06229571430464150  1023:0.06228806784406648
1024:0.06228043543776284  1025:0.06227280957325472  1026:0.06226518837516718
1027:0.06225757556328612  1028:0.06224997483375819  1029:0.06224239169636828
1030:0.06223481870796381  1031:0.06222724848308752  1032:0.06221968837514400
1033:0.06221213102200722  1034:0.06220457825631316  1035:0.06219703190446840
1036:0.06218950473129831  1037:0.06218198393014565  1038:0.06217446767438230
1039:0.06216696502352260  1040:0.06215946689723825  1041:0.06215197148340764
1042:0.06214448058651920  1043:0.06213700320947835  1044:0.06212953212576914
1045:0.06212207270301422  1046:0.06211463560583919  1047:0.06210720829080799
1048:0.06209978718813254  1049:0.06209237405846940  1050:0.06208497065152311
1051:0.06207756989211775  1052:0.06207019638340031  1053:0.06206282725169150
1054:0.06205546423979783  1055:0.06204810384788231  1056:0.06204075478903499
1057:0.06203341008028762  1058:0.06202607839253437  1059:0.06201875276617408
1060:0.06201145730060930  1061:0.06200417297577662  1062:0.06199689634475025
1063:0.06198962568726874  1064:0.06198236439809371  1065:0.06197510566002156
1066:0.06196785117030366  1067:0.06196061447158005  1068:0.06195338705825081
1069:0.06194616722524088  1070:0.06193896166897413  1071:0.06193175862656584
1072:0.06192456478771968  1073:0.06191738346279938  1074:0.06191020630000086
1075:0.06190303163244958  1076:0.06189586775886638  1077:0.06188870968464886
1078:0.06188156565721210  1079:0.06187442739839825  1080:0.06186729654356381
1081:0.06186016979589148  1082:0.06185305043005008  1083:0.06184593515909299
1084:0.06183882561372465  1085:0.06183172341714561  1086:0.06182462692645157
1087:0.06181753613313509  1088:0.06181045589763708  1089:0.06180338133475535
1090:0.06179631081864338  1091:0.06178924596088430  1092:0.06178218675307431
1093:0.06177513479704724  1094:0.06176809810325557  1095:0.06176106541532397
1096:0.06175404950422374  1097:0.06174703757626823  1098:0.06174003598452582
1099:0.06173303677400722  1100:0.06172604628178958  1101:0.06171906132690876
1102:0.06171207874275593  1103:0.06170510483850203  1104:0.06169814116568423
1105:0.06169117984997107  1106:0.06168422245966432  1107:0.06167728150968573
1108:0.06167034602317841  1109:0.06166343463171554  1110:0.06165652865852350
1111:0.06164962655075919  1112:0.06164273139064838  1113:0.06163584470408927
1114:0.06162896800603013  1115:0.06162209667500036  1116:0.06161522764181844
1117:0.06160838074464745  1118:0.06160153612952194  1119:0.06159469683384863
1120:0.06158786133314572  1121:0.06158102810765663  1122:0.06157420774791494
1123:0.06156739719512788  1124:0.06156058890173020  1125:0.06155378587499778
1126:0.06154699110892260  1127:0.06154020308740402  1128:0.06153343373275796
1129:0.06152667404543150  1130:0.06151991955272699  1131:0.06151317912108979
1132:0.06150644385566538  1133:0.06149971227595041  1134:0.06149299173040610
1135:0.06148627632233245  1136:0.06147956457947443  1137:0.06147286234851624
1138:0.06146616668765702  1139:0.06145947612853134  1140:0.06145279502448432
1141:0.06144611755028846  1142:0.06143944515181411  1143:0.06143278216025661
1144:0.06142612422353175  1145:0.06141947565504777  1146:0.06141282924495632
1147:0.06140619504065202  1148:0.06139957585394935  1149:0.06139296023323457
1150:0.06138634675049911  1151:0.06137974109605485  1152:0.06137314892109018
1153:0.06136656311264280  1154:0.06135998083621755  1155:0.06135340913429657
1156:0.06134684095004067  1157:0.06134027487480252  1158:0.06133371371586843
1159:0.06132716866051512  1160:0.06132062849109415  1161:0.06131409876811565
1162:0.06130757390924919  1163:0.06130105390776995  1164:0.06129454152554242
1165:0.06128803398317852  1166:0.06128152851306036  1167:0.06127503063070292
1168:0.06126853481488285  1169:0.06126204244073695  1170:0.06125555213006413
1171:0.06124907759754853  1172:0.06124260511761642  1173:0.06123613605612729
1174:0.06122967177490105  1175:0.06122321226738181  1176:0.06121676160757069
1177:0.06121031570237878  1178:0.06120387996316078  1179:0.06119745165941505
1180:0.06119103212184457  1181:0.06118461729512040  1182:0.06117820851568234
1183:0.06117180309127488  1184:0.06116542238791708  1185:0.06115905165336985
1186:0.06115268953419235  1187:0.06114633204489677  1188:0.06113997785887942
1189:0.06113362829216856  1190:0.06112728070331048  1191:0.06112094167181579
1192:0.06111460723905884  1193:0.06110828133001846  1194:0.06110196653397319
1195:0.06109565369519501  1196:0.06108934802343372  1197:0.06108304820410573
1198:0.06107676329329144  1199:0.06107048032206489  1200:0.06106420574276539
1201:0.06105793567338016  1202:0.06105166882172529  1203:0.06104540646981004
1204:0.06103915630021141  1205:0.06103290805000154  1206:0.06102666810438760
1207:0.06102043262179800  1208:0.06101420032350143  1209:0.06100797629000928
1210:0.06100175796605759  1211:0.06099554407607429  1212:0.06098933840468595
1213:0.06098313588883070  1214:0.06097693778578274  1215:0.06097074786214192
1216:0.06096456233430767  1217:0.06095837868867076  1218:0.06095220318682813
1219:0.06094603580817925  1220:0.06093987154846364  1221:0.06093371662759217
1222:0.06092756605560997  1223:0.06092142602073588  1224:0.06091529031462039
1225:0.06090915646200588  1226:0.06090302939667423  1227:0.06089690787396876
1228:0.06089079802066547  1229:0.06088469245583836  1230:0.06087860824553999
1231:0.06087252585886345  1232:0.06086646104608484  1233:0.06086039804568180
1234:0.06085434890563155  1235:0.06084830397179766  1236:0.06084226083901667
1237:0.06083622430157853  1238:0.06083019554087082  1239:0.06082416857212605
1240:0.06081814578090196  1241:0.06081212597037233  1242:0.06080611151819446
1243:0.06080011071768936  1244:0.06079411406015729  1245:0.06078811917660929
1246:0.06078213078933940  1247:0.06077614770726544  1248:0.06077016756875248
1249:0.06076419154676716  1250:0.06075822080965929  1251:0.06075225300484546
1252:0.06074629281128077  1253:0.06074034370807724  1254:0.06073440217000543
1255:0.06072847281315977  1256:0.06072254634953012  1257:0.06071662393205723
1258:0.06071070555561391  1259:0.06070479236718929  1260:0.06069888205734924
1261:0.06069297347348305  1262:0.06068707465207442  1263:0.06068118327505742
1264:0.06067529361347584  1265:0.06066941023389535  1266:0.06066353198467203
1267:0.06065765999435312  1268:0.06065178970886059  1269:0.06064592226282124
1270:0.06064005878778857  1271:0.06063420380480240  1272:0.06062835616242563
1273:0.06062252146353597  1274:0.06061669181439052  1275:0.06061087837890434
1276:0.06060506661570759  1277:0.06059925763778985  1278:0.06059346033006596
1279:0.06058766579431670  1280:0.06058187292063907  1281:0.06057608281522756
1282:0.06057030099955368  1283:0.06056452524852864  1284:0.06055875664911456
1285:0.06055298969771478  1286:0.06054722987752095  1287:0.06054147935706530
1288:0.06053573047477900  1289:0.06052999738163810  1290:0.06052426917141934
1291:0.06051855340324752  1292:0.06051284248946030  1293:0.06050713426924622
1294:0.06050142981612382  1295:0.06049572912547875  1296:0.06049003648135290
1297:0.06048434651460646  1298:0.06047866136125422  1299:0.06047298314687423
1300:0.06046730866220248  1301:0.06046163790269182  1302:0.06045596980126661
1303:0.06045031283768457  1304:0.06044465851976878  1305:0.06043901423379252
1306:0.06043337152870114  1307:0.06042773566452799  1308:0.06042210347740295
1309:0.06041647391404905  1310:0.06041084802021219  1311:0.06040522997426964
1312:0.06039962183853719  1313:0.06039401942486141  1314:0.06038842168462368
1315:0.06038282964631600  1316:0.06037725464588702  1317:0.06037168324654717
1318:0.06036611749719283  1319:0.06036055533765195  1320:0.06035499676362693
1321:0.06034943972497823  1322:0.06034388626590719  1323:0.06033834148172398
1324:0.06033280026200851  1325:0.06032726056865969  1326:0.06032172748046666
1327:0.06031619794270147  1328:0.06031068306678095  1329:0.06030516970330469
1330:0.06029966187887294  1331:0.06029415857852806  1332:0.06028866380421123
1333:0.06028317253325721  1334:0.06027768576047727  1335:0.06027220248150333
1336:0.06026672468431334  1337:0.06026125930617927  1338:0.06025580431755737
1339:0.06025035475580305  1340:0.06024490667236370  1341:0.06023946400304647
1342:0.06023402280857416  1343:0.06022858799644670  1344:0.06022315563530334
1345:0.06021772670213510  1346:0.06021230802790652  1347:0.06020689179078968
1348:0.06020147701501931  1349:0.06019606856321668  1350:0.06019066932843659
1351:0.06018527541595981  1352:0.06017988295332959  1353:0.06017449580061691
1354:0.06016911009437860  1355:0.06016372679742106  1356:0.06015835359684971
1357:0.06015298854257370  1358:0.06014763637703027  1359:0.06014228659170811
1360:0.06013694108583381  1361:0.06013159890398378  1362:0.06012625909411751
1363:0.06012092544210881  1364:0.06011559510028399  1365:0.06011026900875389
1366:0.06010494904512801  1367:0.06009963519586224  1368:0.06009432463341673
1369:0.06008901641641881  1370:0.06008371241638206  1371:0.06007841916359231
1372:0.06007312730953052  1373:0.06006784336834752  1374:0.06006256639010203
1375:0.06005729450680614  1376:0.06005202586091556  1377:0.06004676321733823
1378:0.06004150656293769  1379:0.06003625680281153  1380:0.06003101025410902
1381:0.06002576599707625  1382:0.06002053134407223  1383:0.06001529897275813
1384:0.06001007252505520  1385:0.06000484926171417  1386:0.05999962736203079
1387:0.05999440864172444  1388:0.05998919309720199  1389:0.05998398524989778
1390:0.05997878146875352  1391:0.05997358805101442  1392:0.05996839598209822
1393:0.05996321691689553  1394:0.05995804187444132  1395:0.05995286995674319
1396:0.05994770026889662  1397:0.05994253992627211  1398:0.05993738180391377
1399:0.05993222944581149  1400:0.05992708813763222  1401:0.05992195607561820
1402:0.05991682621036047  1403:0.05991170029486638  1404:0.05990657919902102
1405:0.05990145941616494  1406:0.05989634706151647  1407:0.05989123601560286
1408:0.05988613063362216  1409:0.05988103090351625  1410:0.05987594632926954
1411:0.05987086305001584  1412:0.05986578192780163  1413:0.05986070382262496
1414:0.05985563131149686  1415:0.05985056180770153  1416:0.05984549530792944
1417:0.05984043266557194  1418:0.05983537301962068  1419:0.05983031551196963
1420:0.05982525928653973  1421:0.05982020605068480  1422:0.05981516346398239
1423:0.05981012300190570  1424:0.05980509144448987  1425:0.05980006453926633
1426:0.05979504059030058  1427:0.05979001959436554  1428:0.05978500491520809
1429:0.05977999233828889  1430:0.05977498270179026  1431:0.05976997600251043
1432:0.05976497056108990  1433:0.05975997056355279  1434:0.05975497349268034
1435:0.05974998101432019  1436:0.05974498978710322  1437:0.05974000314243357
1438:0.05973501940979467  1439:0.05973004439360330  1440:0.05972507144843690
1441:0.05972010965800337  1442:0.05971514992794291  1443:0.05971019143338774
1444:0.05970523581952490  1445:0.05970028964805447  1446:0.05969534470565008
1447:0.05969040998260258  1448:0.05968547729852833  1449:0.05968054746642306
1450:0.05967561885568176  1451:0.05967069227937072  1452:0.05966576854867682
1453:0.05966085495495627  1454:0.05965594419234577  1455:0.05965103706524267
1456:0.05964613195570684  1457:0.05964122805601468  1458:0.05963633822834755
1459:0.05963145120562950  1460:0.05962656778484450  1461:0.05962169115379969
1462:0.05961681970260647  1463:0.05961194944529885  1464:0.05960708356092653
1465:0.05960221886790760  1466:0.05959735853855361  1467:0.05959250098222967
1468:0.05958764698687394  1469:0.05958279496773975  1470:0.05957794650204135
1471:0.05957310316032100  1472:0.05956826885835229  1473:0.05956343730114098
1474:0.05955861161554581  1475:0.05955378788414421  1476:0.05954897467894869
1477:0.05954416341816830  1478:0.05953935332337727  1479:0.05953454827509033
1480:0.05952974748900251  1481:0.05952495018482900  1482:0.05952015481302647
1483:0.05951536291585129  1484:0.05951057602910506  1485:0.05950579106681278
1486:0.05950101186907229  1487:0.05949623535692097  1488:0.05949146535488802
1489:0.05948669802855139  1490:0.05948193413826320  1491:0.05947717215490412
1492:0.05947241283889589  1493:0.05946765618746511  1494:0.05946290295781221
1495:0.05945815238635277  1496:0.05945340598638579  1497:0.05944866450732157
1498:0.05944392416249202  1499:0.05943918646231170  1500:0.05943445140404178
1501:0.05942972275009922  1502:0.05942499747994338  1503:0.05942027483848427
1504:0.05941555482300739  1505:0.05941083967700127  1506:0.05940612864380193
1507:0.05940141873112106  1508:0.05939671143111860  1509:0.05939201120864245
1510:0.05938731284528444  1511:0.05938261708242801  1512:0.05937792391740134
1513:0.05937323334753663  1514:0.05936854759003150  1515:0.05936386884879184
1516:0.05935919342397899  1517:0.05935452057556334  1518:0.05934985177035800
1519:0.05934518626829288  1520:0.05934052772474406  1521:0.05933587100907862
1522:0.05933121976889605  1523:0.05932657107973450  1524:0.05932192930122893
1525:0.05931729151455852  1526:0.05931265698908664  1527:0.05930802644361165
1528:0.05930340059333136  1529:0.05929877582529008  1530:0.05929415358070163
1531:0.05928953601559138  1532:0.05928492312085743  1533:0.05928032346819850
1534:0.05927572559931863  1535:0.05927113022559979  1536:0.05926653805621686
1537:0.05926194766522807  1538:0.05925735976187085  1539:0.05925277292389872
1540:0.05924818786060662  1541:0.05924360952911287  1542:0.05923903579256310
1543:0.05923446452658637  1544:0.05922989643338620  1545:0.05922533080504785
1546:0.05922076763910248  1547:0.05921620623051901  1548:0.05921165148809685
1549:0.05920709779652660  1550:0.05920254585543360  1551:0.05919799496406182
1552:0.05919345280224458  1553:0.05918891238245458  1554:0.05918437439944588
1555:0.05917983885079085  1556:0.05917530851022201  1557:0.05917078889603807
1558:0.05916627169709952  1559:0.05916175622188796  1560:0.05915724315786920
1561:0.05915273456529563  1562:0.05914822837693840  1563:0.05914372938641760
1564:0.05913923210640951  1565:0.05913473790228257  1566:0.05913024540529083
1567:0.05912575597810949  1568:0.05912126893584053  1569:0.05911678427613213
1570:0.05911230131683311  1571:0.05910782887215453  1572:0.05910335744247965
1573:0.05909888973082779  1574:0.05909442640557057  1575:0.05908996611223481
1576:0.05908550951927061  1577:0.05908105594954730  1578:0.05907661075686431
1579:0.05907216790428427  1580:0.05906772939140544  1581:0.05906329254551110
1582:0.05905886069344046  1583:0.05905443050360523  1584:0.05905000263898023
1585:0.05904557577020153  1586:0.05904115850561185  1587:0.05903674619274244
1588:0.05903233947883688  1589:0.05902793375158270  1590:0.05902353229503572
1591:0.05901913313484379  1592:0.05901473561356111  1593:0.05901034496289423
1594:0.05900595790282710  1595:0.05900157312480059  1596:0.05899719062661112
1597:0.05899281040605825  1598:0.05898843311063597  1599:0.05898405938533674
1600:0.05897968987208499  1601:0.05897532520917726  1602:0.05897096409661280
1603:0.05896660781648452  1604:0.05896225700059014  1605:0.05895791099506197
1606:0.05895356851064015  1607:0.05894923081889484  1608:0.05894489536027758
1609:0.05894056531580830  1610:0.05893623749692910  1611:0.05893191253637307
1612:0.05892758979651123  1613:0.05892327244067590  1614:0.05891896171769392
1615:0.05891465446118996  1616:0.05891034814919074  1617:0.05890604403958680
1618:0.05890174150185840  1619:0.05889743990677319  1620:0.05889313988195704
1621:0.05888884393477768  1622:0.05888454892756195  1623:0.05888025736361417
1624:0.05887596673784985  1625:0.05887167829974527  1626:0.05886739703450639
1627:0.05886311794771171  1628:0.05885883979392526  1629:0.05885456319436165
1630:0.05885029249098785  1631:0.05884602457507727  1632:0.05884176006137518
1633:0.05883749832746765  1634:0.05883324368155490  1635:0.05882898995849210
1636:0.05882473961603429  1637:0.05882049510058469  1638:0.05881625517446196
1639:0.05881201677602033  1640:0.05880777929372506  1641:0.05880354333757050
1642:0.05879931317115530  1643:0.05879508391752866  1644:0.05879085618445053
1645:0.05878663057845726  1646:0.05878240770434057  1647:0.05877818816463026
1648:0.05877396953345502  1649:0.05876976026828755  1650:0.05876555250998095
1651:0.05876135407085042  1652:0.05875715653144968  1653:0.05875296228799679

无心人

我觉得算这种东西只有理论意义

实际上, 参与的小素数不要太多, 否则不合算的
如果实现位运算, 乘到29就可以了
否则如果是双字, 乘的更少

要看综合效益
这算法存在拷贝的消耗
假设每次都计算N个数字的筛, 占字节<= N
则拷贝消耗是c0 * N   (c0<= 2)

假设须剔除素数为p0, p1, ...pn, p0 >> 2
则, 运算工作量为 c1 * N / 2 * (1/p0 + 1/p1 ... + pn) (c1 > 10)
那么总工作量c0 * N + c1* N / 2 * (1/p0 + 1/p1 ... + pn)
                   = N * (c0 + c1/2p0 + c1/2p1 ... + c1/2pn)

理论上可证明p0越大, 工作量越小
但素数乘积如果太大, 比如超过64位, 将存在高精度运算问题
除非使用X86-64CPU在64位操作环境下, 否则总会遇到高精度计算的麻烦
而且N必须被小于p0素数整除, 才能有高效的加法筛, 否则小素数还要筛一次
决定了p0不能太大, 否则N太大
一般建议不要超过32位,  N要< 1M, 采用位运算的可适当大些

无心人

我给出的算法曾在查找很大的相邻素数差时使用过
速度达到1200亿/小时的筛速度

mathe

通常数学里面把无穷乘积中结果为0和无穷都表示发散。
将这个乘积取倒数，也就是
$1/(1-1/p_1)xx1/(1-1/p_2)xx...xx1/(1-1/p_n)xx...$
将每一项按泰勒级数展开就成为
$(1+1/p_1+1/p_1^2+1/p_1^3+...)(1+1/p_2+1/p_2^2+...)...(1+1/p_n+1/p_n^2+...)...$
现在将乘积式展开，我们可以由算术基本定理（唯一因子分解），知道，展开后，每个正整数正好在一项的分母中出现，也就是上面乘积就是
$1+1/2+1/3+...+1/n+...$
我们知道这个级数是发散的，所以原来的无穷乘积也是发散的。

lyg_wangyushi

谢谢无心人和mathe的回复，原来无穷乘积为0也表示为发散，学习了

mathe

无穷乘积为0也表示发散，数学里面有一个结论:
无穷乘积
$\prod a_i$
同无穷级数
$\sum log(a_i)$
同敛散

sir_chen

不知道有没有比筛法更好的求质数的方法