快速生成素数表的方法

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

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