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

题目

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

答案

郭敦顒回答：
抽象地讲容斥原理,确实不易理解,那么我就很通俗地说一下——
容斥原理即逐步淘汰法,也叫筛法,在数论中占有非常重要的地位,最著明的筛法是爱拉托斯特尼筛法：为找出≤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.