素数的精确公式

yangchuanju

素数的精确公式
下面是王元给出的简化的容斥公式：
π(N)＝( r-1) +{N-∑[N/pi]+∑[N/pipj]-∑[N/pipjpk]+…+(-1)^r*[N/p1p2…pr]}
(第一个∑：1≤i≤r。第二个∑：1≤i＜j≤r。第三个∑：1≤i＜j＜k≤r。)
转引自童信平《“1+1”浅见之十：哈代－李特伍德猜想(A)未揭示的6个细节》9楼贴。

yangchuanju

用此式子
π(N)＝( r-1) +{N-∑[N/pi]+∑[N/pipj]-∑[N/pipjpk]+…+(-1)^r*[N/p1p2…pr]}
可以求出
π(1000)=168
π(10000)=1229
π(100000)=9592
π(1000000)=78498
转引自大傻在童信平《“1+1”浅见之十：哈代－李特伍德猜想(A)未揭示的6个细节》贴中20楼贴。

yangchuanju

素数的精确公式
下面是王元给出的简化的容斥公式：
π(N)＝( r-1) +{N-∑[N/pi]+∑[N/pipj]-∑[N/pipjpk]+…+(-1)^r*∑[N/p1p2…pr]}
(第一个∑：1≤i≤r。第二个∑：1≤i＜j≤r。第三个∑：1≤i＜j＜k≤r。)
转引自童信平《“1+1”浅见之十：哈代－李特伍德猜想(A)未揭示的6个细节》9楼贴。

N=100，100平方根等于10，10以内素数共有4个：2,3,5,7；
r=4
∑[N/pi]=[100/2]+[100/3]+[100/5]+[100/7]=50+33+20+14=117
∑[N/pipj]=[100/(2*3)]+[100/(2*5)]+[100/(2*7)]+[100/(3*5)]+[100/(3*7)]+[100/(5*7)]=[100/6]+[100/10]+[100/14]+[100/15]+[100/21]+[100/35]=16+10+7+6+4+2=45
∑[N/pipjpk]=[100/(2*3*5)]+[100/(2*3*7)]+[100/(2*5*7)]+[100/(3*5*7)]=[100/30]+[100/42]+[100/70]+[100/105]=3+2+1+0=6
∑[N/p1p2…pr]=[100/(2*3*5*7)]=[100/210]=0
π(N)＝( r-1) +{N-∑[N/pi]+∑[N/pipj]-∑[N/pipjpk]+…+(-1)^r*∑[N/p1p2…pr]}
=(4-1)+100-117+45-6+0=25

朱明君

朱明君

第2步中的2是质数3的对应数，即(3^2+1)÷2-3=2，
第3步中的8是质数5的对应数，即(5^2+1)÷2-5=8，
第4步中的18是质数7的对应数，即(7^2+1)÷2-7=18，

朱明君

，，，，，，，

yangchuanju

N=1000，1000平方根等于31.6，31.6以内素数共有11个：2,3,5,7,…31；
仍采用公式
π(N)＝( r-1) +{N-∑[N/pi]+∑[N/pipj]-∑[N/pipjpk]+…+(-1)^r*∑[N/p1p2…pr]}
共有11个和号，其中
第1个和号为11项连加和，
第2个和号为11*10/2=55项连加和，
第3个和号为11*10*9/(2*3)=165项连加和，
以下第4-11个和号项数见表：               
和号号        组合未项        项数
1        11        11
2        10        55
3        9        165
4        8        330
5        7        462
6        6        462
7        5        330
8        4        165
9        3        55
10        2        11
11        1        1
合计  ——2047

1000并不是一个很大的数字，然而要算1000以内的素数个数，确需2047+3个整数相加减才能算出来，
你能正确地算出来吗？

非也，在2047个整数之中有相当多的0，不必计算和加减。
第1个和号之中的分母最小是2，最大是31，11项必须全算；
第2个和号之中的分母最小是2*3=6，最大是29*31=899，55项要全算；
第3个和号之中的分母最小是2*3*5=30，最大是23*29*31=20077>1000（取整为0），165项不必全算，实际只算70项即可；
第4个和号之中的分母最小是2*3*5*7=210，最大是19*23*29*31>1000（取整为0），330项不必全算；（有效项仅16项）
第5个和号之中的分母最小是2*3*5*7*11=2310>1000（取整为0），各项不必再算；
以下第6-11个和号中的各项都是0，各个和号也都等于0了，不用再计算了。

至此只需计算前4个和号即可，总项数等于561。
具体计算结果是
第1和号11项-1560
第2和号55项+974
第3和号70有效项-279
第4和号16有效项+23
11-1+1000-1560+974-279+23=168

yangchuanju

N=10000，10000平方根等于100，100以内素数共有25个：2,3,5,7,…97；
仍采用公式
π(N)＝( r-1) +{N-∑[N/pi]+∑[N/pipj]-∑[N/pipjpk]+…+(-1)^r*∑[N/p1p2…pr]}
共有25个和号，其中
第1个和号为25项连加和，
第2个和号为25*24/2=300项连加和，
第3个和号为25*24*23/(2*3)=2300项连加和，
以下第4-25个和号项数见表：
和号号        组合未项        项数
1        25        25
2        24        300
3        23        2300
4        22        12650
5        21        53130
6        20        177100
7        19        480700
8        18        1081575
9        17        2042975
10        16        3268760
11        15        4457400
12        14        5200300
13        13        5200300
14        12        4457400
15        11        3268760
16        10        2042975
17        9        1081575
18        8        480700
19        7        177100
20        6        53130
21        5        12650
22        4        2300
23        3        300
24        2        25
25        1        1
合计        ——        33554431
10000并不是一个很大的数字，然而要算10000以内的素数个数，确需33554431+3个整数相加减才能算出来，
你能正确地算出来吗？

非也，在3355多万个整数之中有相当多的0，不必计算和加减。
第1个和号之中的分母最小是2，最大是97，25项必须全算；
第2个和号之中的分母最小是2*3=6，最大是89*97=8633，300项要全算；
第3个和号之中的分母最小是2*3*5=30，最大是83*89*97=716539>10000（取整为0），2300项不必全算；
第4个和号之中的分母最小是2*3*5*7=210，最大是79*83*89*97>10000（取整为0），12650项不必全算；
第5个和号之中的分母最小是2*3*5*7*11=2310，最大是73*79*83*89*97>10000（取整为0），53130项不必全算；
第6个和号之中的分母最小是2*3*5*7*11*13=30030>10000（取整为0），最大是71*73*79*83*89*97>10000（取整为0），177100项都是0全不用再算；
以下第7-25个和号中的各项都是0，各个和号也都等于0了，不用再计算了。
至此只需计算前5个和号即可，总项数等于68405。

68405仍然太大，其中还有许多个0项，不需计算！
第3个和号中的19*23*29=12673>10000，取整为0，第1个素数是23及大于23的素数不用再算；
第4个和号中的7*11*13*17=17017>10000，取整为0，第1个素数是7及大于7的素数不用再算；
第5个和号中的3*5*7*11*13=30030>10000，取整为0，第1个素数是3及大于3的素数不用再算。

yangchuanju

经计算第5个和号53130项中仅剩[10000/(2*3*5*7*11)]=4等24项，                               
2310=2*3*5*7*11        2730=2*3*5*7*13        3570=2*3*5*7*17        3990=2*3*5*7*19
4290=2*3*5*11*13        4830=2*3*5*7*23        5610=2*3*5*11*17        6006=2*3*7*11*13
6090=2*3*5*7*29        6270=2*3*5*11*19        6510=2*3*5*7*31        6630=2*3*5*13*17
7410=2*3*5*13*19        7590=2*3*5*11*23        7770=2*3*5*7*37        7854=2*3*7*11*17
8610=2*3*5*7*41        8778=2*3*7*11*19        8970=2*3*5*13*23        9030=2*3*5*7*43
9282=2*3*7*13*17        9570=2*3*5*11*29        9690=2*3*5*17*19        9870=2*3*5*7*47


经计算第4个和号12650项中仅剩[10000/(2*3*5*7)]=47等335项，                                       
1        210=2*3*5*7        3010=2*5*7*43        5330=2*5*13*41        7638=2*3*19*67
2        330=2*3*5*11        3045=3*5*7*29        5358=2*3*19*47        7665=3*5*7*73
3        390=2*3*5*13        3066=2*3*7*73        5394=2*3*29*31        7670=2*5*13*59
4        462=2*3*7*11        3094=2*7*13*17        5406=2*3*17*53        7714=2*7*19*29
5        510=2*3*5*17        3102=2*3*11*47        5434=2*11*13*19        7735=5*7*13*17
6        546=2*3*7*13        3135=3*5*11*19        5474=2*7*17*23        7755=3*5*11*47
7        570=2*3*5*19        3162=2*3*17*31        5478=2*3*11*83        7790=2*5*19*41
8        690=2*3*5*23        3190=2*5*11*29        5510=2*5*19*29        7810=2*5*11*71
9        714=2*3*7*17        3198=2*3*13*41        5530=2*5*7*79        7826=2*7*13*43
10        770=2*5*7*11        3230=2*5*17*19        5538=2*3*13*71        7905=3*5*17*31
11        798=2*3*7*19        3255=3*5*7*31        5565=3*5*7*53        7917=3*7*13*29
12        858=2*3*11*13        3290=2*5*7*47        5590=2*5*13*43        7930=2*5*13*61
13        870=2*3*5*29        3306=2*3*19*29        5642=2*7*13*31        7990=2*5*17*47
14        910=2*5*7*13        3315=3*5*13*17        5655=3*5*13*29        7995=3*5*13*41
15        930=2*3*5*31        3318=2*3*7*79        5658=2*3*23*41        7998=2*3*31*43
16        966=2*3*7*23        3354=2*3*13*43        5694=2*3*13*73        8030=2*5*11*73
17        1110=2*3*5*37        3410=2*5*11*31        5698=2*7*11*37        8058=2*3*17*79
18        1122=2*3*11*17        3458=2*7*13*19        5810=2*5*7*83        8094=2*3*19*71
19        1155=3*5*7*11        3486=2*3*7*83        5830=2*5*11*53        8142=2*3*23*59
20        1190=2*5*7*17        3498=2*3*11*53        5865=3*5*17*23        8151=3*11*13*19
21        1218=2*3*7*29        3534=2*3*19*31        5874=2*3*11*89        8162=2*7*11*53
22        1230=2*3*5*41        3542=2*7*11*23        5890=2*5*19*31        8170=2*5*19*43
23        1254=2*3*11*19        3666=2*3*13*47        5934=2*3*23*43        8178=2*3*29*47
24        1290=2*3*5*43        3705=3*5*13*19        6018=2*3*17*59        8211=3*7*17*23
25        1302=2*3*7*31        3710=2*5*7*53        6042=2*3*19*53        8246=2*7*19*31
26        1326=2*3*13*17        3738=2*3*7*89        6045=3*5*13*31        8265=3*5*19*29
27        1330=2*5*7*19        3770=2*5*13*29        6105=3*5*11*37        8294=2*11*13*29
28        1365=3*5*7*13        3774=2*3*17*37        6110=2*5*13*47        8295=3*5*7*79
29        1410=2*3*5*47        3795=3*5*11*23        6118=2*7*19*23        8322=2*3*19*73
30        1430=2*5*11*13        3885=3*5*7*37        6162=2*3*13*79        8385=3*5*13*43
31        1482=2*3*13*19        3894=2*3*11*59        6195=3*5*7*59        8398=2*13*17*19
32        1518=2*3*11*23        3910=2*5*17*23        6222=2*3*17*61        8418=2*3*23*61
33        1554=2*3*7*37        3927=3*7*11*17        6230=2*5*7*89        8463=3*7*13*31
34        1590=2*3*5*53        4002=2*3*23*29        6279=3*7*13*23        8466=2*3*17*83
35        1610=2*5*7*23        4026=2*3*11*61        6290=2*5*17*37        8510=2*5*23*37
36        1722=2*3*7*41        4030=2*5*13*31        6314=2*7*11*41        8547=3*7*11*37
37        1770=2*3*5*59        4070=2*5*11*37        6402=2*3*11*97        8554=2*7*13*47
38        1785=3*5*7*17        4074=2*3*7*97        6405=3*5*7*61        8602=2*11*17*23
39        1794=2*3*13*23        4130=2*5*7*59        6438=2*3*29*37        8645=5*7*13*19
40        1806=2*3*7*43        4134=2*3*13*53        6474=2*3*13*83        8690=2*5*11*79
41        1830=2*3*5*61        4182=2*3*17*41        6486=2*3*23*47        8710=2*5*13*67
42        1870=2*5*11*17        4186=2*7*13*23        6490=2*5*11*59        8715=3*5*7*83
43        1914=2*3*11*29        4218=2*3*19*37        6545=5*7*11*17        8742=2*3*31*47
44        1938=2*3*17*19        4270=2*5*7*61        6555=3*5*19*23        8745=3*5*11*53
45        1974=2*3*7*47        4278=2*3*23*31        6578=2*11*13*23        8806=2*7*17*37
46        1995=3*5*7*19        4305=3*5*7*41        6622=2*7*11*43        8835=3*5*19*31
47        2002=2*7*11*13        4370=2*5*19*23        6670=2*5*23*29        8855=5*7*11*23
48        2010=2*3*5*67        4386=2*3*17*43        6699=3*7*11*29        8866=2*11*13*31
49        2030=2*5*7*29        4389=3*7*11*19        6710=2*5*11*61        8930=2*5*19*47
50        2046=2*3*11*31        4422=2*3*11*67        6726=2*3*19*59        8990=2*5*29*31
51        2090=2*5*11*19        4466=2*7*11*29        6734=2*7*13*37        9006=2*3*19*79
52        2130=2*3*5*71        4485=3*5*13*23        6765=3*5*11*41        9010=2*5*17*53
53        2145=3*5*11*13        4510=2*5*11*41        6783=3*7*17*19        9078=2*3*17*89
54        2170=2*5*7*31        4515=3*5*7*43        6790=2*5*7*97        9086=2*7*11*59
55        2190=2*3*5*73        4522=2*7*17*19        6834=2*3*17*67        9102=2*3*37*41
56        2210=2*5*13*17        4602=2*3*13*59        6882=2*3*31*37        9130=2*5*11*83
57        2226=2*3*7*53        4641=3*7*13*17        6890=2*5*13*53        9165=3*5*13*47
58        2262=2*3*13*29        4674=2*3*19*41        6902=2*7*17*29        9177=3*7*19*23
59        2346=2*3*17*23        4686=2*3*11*71        6942=2*3*13*89        9222=2*3*29*53
60        2370=2*3*5*79        4690=2*5*7*67        6954=2*3*19*61        9230=2*5*13*71
61        2415=3*5*7*23        4730=2*5*11*43        6970=2*5*17*41        9246=2*3*23*67
62        2418=2*3*13*31        4758=2*3*13*61        7030=2*5*19*37        9338=2*7*23*29
63        2442=2*3*11*37        4774=2*7*11*31        7035=3*5*7*67        9345=3*5*7*89
64        2470=2*5*13*19        4785=3*5*11*29        7095=3*5*11*43        9394=2*7*11*61
65        2478=2*3*7*59        4794=2*3*17*47        7106=2*11*17*19        9430=2*5*23*41
66        2490=2*3*5*83        4810=2*5*13*37        7130=2*5*23*31        9435=3*5*17*37
67        2530=2*5*11*23        4818=2*3*11*73        7134=2*3*29*41        9462=2*3*19*83
68        2562=2*3*7*61        4845=3*5*17*19        7161=3*7*11*31        9471=3*7*11*41
69        2590=2*5*7*37        4862=2*11*13*17        7215=3*5*13*37        9490=2*5*13*73
70        2618=2*7*11*17        4902=2*3*19*43        7238=2*7*11*47        9546=2*3*37*43
71        2622=2*3*19*23        4930=2*5*17*29        7242=2*3*17*71        9614=2*11*19*23
72        2670=2*3*5*89        4935=3*5*7*47        7293=3*11*13*17        9646=2*7*13*53
73        2706=2*3*11*41        4970=2*5*7*71        7310=2*5*17*43        9735=3*5*11*59
74        2805=3*5*11*17        5005=5*7*11*13        7314=2*3*23*53        9758=2*7*17*41
75        2814=2*3*7*67        5106=2*3*23*37        7315=5*7*11*19        9790=2*5*11*89
76        2838=2*3*11*43        5110=2*5*7*73        7370=2*5*11*67        9798=2*3*23*71
77        2870=2*5*7*41        5115=3*5*11*31        7378=2*7*17*31        9842=2*7*19*37
78        2886=2*3*13*37        5170=2*5*11*47        7395=3*5*17*29        9858=2*3*31*53
79        2910=2*3*5*97        5187=3*7*13*19        7446=2*3*17*73        9867=3*11*13*23
80        2926=2*7*11*19        5214=2*3*11*79        7455=3*5*7*71        9890=2*5*23*43
81        2958=2*3*17*29        5226=2*3*13*67        7462=2*7*13*41        9894=2*3*17*97
82        2982=2*3*7*71        5270=2*5*17*31        7482=2*3*29*43        9933=3*7*11*43
83        2990=2*5*13*23        5278=2*7*13*29        7566=2*3*13*97        9982=2*7*23*31
84        3003=3*7*11*13        5313=3*7*11*23        7626=2*3*31*41       

第3个和号2300项中有效项（不等于0的项）要多一些，为711项（数据略），
据此仅需计算3+(25+300+711+335+24)=1398项之代数和即可，前面的3为r-1+N=25-1+10000。
如觉得第3个和号筛减麻烦，可对2300项全取亦可，总项变为3363了。。

实际计算可在Execl之中进行，公式中的和号Σ改为sum函数，取整号[]改为int函数。
具体计算结果是
第1和号25项-18016
第2和号300项+13848
第3和号711有效项-5537
第4和号335有效项+943
第5和号24有效项-33
25-1+10000-18016+13848-5537+943-33=1229