集合包含排斥法求120内素数个数

思路

  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足够大时，素因子集合过大，本算法运算起来将会复杂。