请通俗讲一下集合容斥原理。。。公式都看不懂的说

郭敦顒回答：

抽象地讲容斥原理，确实不易理解，那么我就很通俗地说一下——

容斥原理即逐步淘汰法，也叫筛法，在数论中占有非常重要的地位，最著明的筛法是爱拉托斯特尼筛法：为找出≤x的所有素数，写下所有≤x的自然数构成的序列2,3,4,5,…, x；从4往下划掉2的倍数,再从6往下划掉3的倍数,从10往下划掉5的倍数,依此继续下去,精确地说,在第k步后，没有划掉的k＋1个最小的数是素数，而如果Pk＋1是其中最大者，则k＋1步就是从2Pk＋1往下划掉Pk＋1的倍数．我们会在最后一个素数Pr处停下，Pr≤√x．事实上，如果自然数m满足√x＜m≤x且未被划去，则它不可能是一个积ab，其中a＞1，b＞1，因为否则数a和b至少有一个会≤√x，因此m会被已经找到的素数之一整除从而应当会被划去．这样，所有未被划去且＞√x的数是素数．

上面对为找出≤x的所有素数，写下所有≤x的自然数构成的序列2,3,4,5,…, x；从4往下划掉2的倍数,再从6往下划掉3的倍数,从10往下划掉5的倍数,依此继续下去,精确地说,在第k步后，没有划掉的k＋1个最小的数是素数，而如果Pk＋1是其中最大者，则k＋1步就是从2Pk＋1往下划掉Pk＋1的倍数．我们会在最后一个素数Pr处停下，Pr≤√x．事实上，如果自然数m满足√x＜m≤x且未被划去，则它不可能是一个积ab，其中a＞1，b＞1，因为否则数a和b至少有一个会≤√x，因此m会被已经找到的素数之一整除从而应当会被划去．这样，所有未被划去且＞√x的数是素数．

上面对爱氏筛法的描述只涉及到他筛法的操作方法步骤，并未涉及到其计算问题，下面谈谈其筛法的计算问题，这就涉及到容斥原理了。

如求小于210的奇素数，及个数。小于210的奇素数的个数记为p（1，210）

小于210的奇数是1，3，5，7，9，…，207，209

3为素数（略去了 “奇”字，下同），

小于210的素数3的奇合数的个数h₃=210/（2×3）－1=35－1=34，

小于210的素数3的奇合数集合记为H₃={9，15，21，27，33，…，201，207}

5为素数，小于210的素数5的奇合数的个数h₅=210/（2×5）－1=21－1=20，

小于210的素数5的奇合数集合记为H₅={15，25，45，45，…，195，205}

7为素数，小于210的素数7的奇合数的个数h₇=210/（2×7）－1=15－1=14，

小于210的素数7的奇合数集合记为H₇={21，35，49，63，…，189，203}

11为素数，小于210的素数11的奇合数的个数h₁₁=210/（2×11）－1=10－1=9，

小于210的素数11的奇合数集合记为H₁₁={33，55，77，99，121，143，165，187，209}，

13为素数，小于210的素数13的奇合数的个数h₁₃=210/（2×13）－1=8－1=7，

小于210的素数13的奇合数记为H₁₃={39，65，91，117，143， 169，195}

13为小于√210的最大素数了，再大的素数为17，17²=289＞20与问题无关了。

3与5的二合数最小的是15，3与5的二合数的个数记为h₍₃.₅₎，

h₍₃.₅₎=210/（2×15）=7，（均在小于210的范围内，下同）

3与5的二合数的集合记为H₍₃.₅₎， H₍₃.₅₎={15，45，75，105，135，165，195}；

3与7的二合数最小的是21，3与7的二合数的个数记为h₍₃.₇₎，

h₍₃.₇₎=210/（2×21）=5，

3与7的二合数的集合记为H₍₃.₇₎， H₍₃.₇₎={21，63， 105，147，189 }；

3与11的二合数最小的是33，3与11的二合数的个数记为h₍₃.₁₁₎，

h₍₃.₁₁₎=210/（2×33）=3，

3与11的二合数的集合记为H₍₃.₁₁₎， H₍₃.₁₁₎={33，99， 165， }；

3与13的二合数最小的是39，3与13的二合数的个数记为h₍₃.₁₃₎，

h₍₃.₁₃₎=210/（2×39）=3，

3与13的二合数的集合记为H₍₃.₁₃₎， H₍₃.₁₃₎={39，117， 195 }；

5与7的二合数最小的是35，5与7的二合数的个数记为h₍₅.₇₎，

h₍₅.₇₎=210/（2×35）=3，

5与7的二合数的集合记为H₍₅.₇₎， H₍₅.₇₎={35， 105，175}；

5与11的二合数最小的是55，5与11的二合数的个数记为h₍₅.₁₁₎，

h₍₅.₁₁₎=210/（2×55）=2，

5与11的二合数的集合记为H₍₅.₁₁₎， H₍₅.₁₁₎={55， 165}；

5与13的二合数最小的是65，5与13的二合数的个数记为h₍₅.₁₃₎，

h₍₅.₁₃₎=210/（2×65）=2，

5与13的二合数的集合记为H₍₅.₁₃₎， H₍₅.₁₃₎={65， 195}；

7与11的二合数最小的是77，7与11的二合数的个数记为h₍₇.₁₁₎，

h₍₇.₁₁₎=210/（2×77）=1，

7与11的二合数的集合记为H₍₇.₁₁₎， H₍₇.₁₁₎={77}；

7与13的二合数最小的是91，7与13的二合数的个数记为h₍₇.₁₃₎，

h₍₇.₁₃₎=210/（2×91）=1，

7与13的二合数的集合记为H₍₇.₁₃₎， H₍₇.₁₃₎={91}；

11与13的二合数最小的是143，11与13的二合数的个数记为h₍₁₁.₁₃₎，

h₍₁₁.₁₃₎=210/（2×143）=1，

11与13的二合数的集合记为H₍₁₁.₁₃₎， H₍₁₁.₁₃₎={143}；

3、5、7的三合数最小的是105，3、5、7的三合数的个数记为h ₍₃.₅.₇₎，

h₍₃.₅.₇₎=210/（2×105）=1，

3、5、7的三合数的集合记为H₍₃.₅.₇₎， H₍₃.₅.₇₎={105}；

3、5、11的三合数最小的是165，3、5、11的三合数的个数记为h ₍₃.₅.₁₁₎，

h₍₃.₅.₁₁₎=210/（2×165）=1，

3、5、11的三合数的集合记为H₍₃.₅.₁₁₎， H₍₃.₅.₁₁₎={165}；

3、5、13的三合数最小的是195，3、5、13的三合数的个数记为h ₍₃.₅.₁₃₎，

h₍₃.₅.₁₃₎=210/（2×195）=1，

3、5、13的三合数的集合记为H₍₃.₅.₁₃₎， H₍₃.₅.₁₃₎={195}；

小于210的奇素数的个数：

p（1，210）=210/2－1－（h₃+h₅+h₇+h₁₁+h₁₃）

+（h₍₃.₅₎+h₍₃.₇₎+h ₍₃.₁₁₎+h ₍₃.₁₃₎+h₍₅.₇₎+h₍₅.₁₁₎+h₍₅.₁₃₎+h₍₇.₁₁₎+h₍₇.₁₃₎+h₍₁₁.₁₃₎）

－（h₍₃.₅.₇₎+ h₍₃.₅.₁₁₎+ h₍₃.₅.₁₃₎）

=105－1－（34+20+14+9+7）+（7+5+3+3+3+2+2+1+1+1）－（1+1+1）

=104－84+28－3=45

区间（1，210）内奇素数的集合记为P（1，210），

P（1，210）={3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113，127，131，137，139，149，151，157，163，167，173，179，181，191，193，197，199}，区间（1，210）内奇素数的个数为45，这与前面的计算结果一致。

小于210的奇数共105个，减自然数1的个数1后为104个奇数；减3、5、7、11、13的合数个数的和84；多减了二合数，二合数个数的和为28，进行补偿，故加28；又多补偿了三合数，三合数个数的和为3，故再扣除3，故有计算式：

210/2－1－84+28－3=45。