思路
1. 思想是所有的合数都可由若干个素数因子的积构成，如 18 = 2 * 3 * 3 等等。
2. 考虑到 11*11 = 121 > 120 可以大胆推论，120以内的任意一个合数的其中一个素数因子必属于集合{2,3,5,7}。当然如果N是121到168，必须将11也纳入其中，依次类推
3. 现设集合A、B、C、D是120内能分别整除2,3,5,7的数的集合，可以非常肯定地认为除开2,3,5,7本身，A、B、C、D的并集包含了120以内所有的合数,相应的素数个数就是这个并集的补集包含的元素数（当然还不够，还得剔除1，加上2,3,5,7）
4. 现在求素数的个数，相当于求~(A∪B∪C∪D)的元素数，再加上3（去掉1就是减1，加上2,3,5,7就是加4）
5. 总结公式：
由 |A∪B|= (|A|+|B|) - |AB| 可以推广
|A∪B∪C∪D| = (|A|+|B|+|C|+|D|) -(|AB|+|AC|+|AD|+|BC|+|BD|+|CD|) + (|ABC|+|ABD|+|ACD|+|BCD|) - |ABCD|
最终素数个数 S = 120 - |A∪B∪C∪D| + 3;
Codes
/**
* 集合论包含排斥算法的简单应用
* 求120以内的素数个数
* @author Fairy2016
*
*/
public class CollectionAlgorithm {
public static void main(String args[]) {
int N = 120;
/**
* |A∪B∪C∪D| = (|A|+|B|+|C|+|D|)-(|AB|+|AC|+|AD|+|BC|+|BD|+|CD|)+
* (|ABC|+|ABD|+|ACD|+|BCD|)-|ABCD|
* 最终素数个数 S = 120 - |A∪B∪C∪D| + 3;
*/
int CountA = N / 2; //|A| 能被2整除的数的个数
int CountB = N / 3; //|B| 能被3整除的数的个数
int CountC = N / 5; //|C| 能被5整除的数的个数
int CountD = N / 7; //|D| 能被7整除的数的个数
int CountAB = N / (2 * 3); //|AB| 能同时被2，3整除的数的个数
int CountAC = N / (2 * 5); //|AC| 能同时被2，5整除的数的个数
int CountAD = N / (2 * 7); //|AD| 能同时被2，7整除的数的个数
int CountBC = N / (3 * 5); //|AB| 能同时被3，5整除的数的个数
int CountBD = N / (3 * 7); //|AB| 能同时被3，7整除的数的个数
int CountCD = N / (5 * 7); //|AB| 能同时被5，7整除的数的个数
int CountABC = N / (2 * 3 * 5); //|ABC| 能同时被2，3，5整除的数的个数
int CountABD = N / (2 * 3 * 7); //|ABD| 能同时被2，3，7整除的数的个数
int CountACD = N / (2 * 5 * 7); //|ABD| 能同时被2，5，7整除的数的个数
int CountBCD = N / (3 * 5 * 7); //|ABD| 能同时被3，5，7整除的数的个数
int CountABCD = N / (2 * 3 * 5 * 7); //|ABCD| 能同时被2，3，5，7整除的数的个数
int S = N - (CountA + CountB + CountC + CountD)
+ (CountAB + CountAC + CountAD + CountBC + CountBD + CountCD)
- (CountABC + CountABD + CountACD + CountBCD)
+ CountABCD + 3;
System.out.println(N+"以内的素数个数为"+S);
}
}
结语
属于估值法，适用于N不是特别大的情况，当N足够大时，素因子集合过大，本算法运算起来将会复杂。
