java - java中的包含和排除原理

Question

您好，我想用 Java 编写包含和排除原则。 我想为这个问题编写代码

给定 N 个素数和一个数字 M，找出从 1 到 M 有多少个数字可以被给定的 N 个素数中的任何一个整除。

 The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is

 P(3 U 5 U 7) = P(3) + P(5) + P(7) - P(3X5) - P(5X7)- P(3X7)+ P(3X5X7)

 P(3) = 500/3 = 166.66 Take 166 ,
 P(5) = 500/5 = 100 ,
 P(7) = 500/7 = 71.42 Take 71,
 P(3X5) = p(15) = 500/15 = 33.33 Take 33 ,
 P(7X5) = p(35) = 500/35 = 14.28 Take 14,
 P(3X7) = p(21) = 500/21 = 23.8  Take 23,
 P(3X5x7) = p(105 ) = 500/105 = 4.76  Take 4


 Answer = 166+100+71-33-14-23+4 = 271

我正在尝试使用此 C++ 实现构建 Java 代码 https://www.geeksforgeeks.org/inclusion-exclusion-principle-and-programming-applications/

 int count(int a[], int m, int n)
{
    int odd = 0, even = 0;
    int counter, i, j, p = 1;
    int pow_set_size = (1 << n);


   //this for loop will run 2^n time   
    for (counter = 1; counter < pow_set_size; counter++) {

    //I am not understanding  below for loop code
        p = 1;
        for (j = 0; j < n; j++) {

            /* Check if jth bit in the counter is set
             If set then pront jth element from set */
            if (counter & (1 << j)) {
                p *= a[j];
            }
        }

        // if set bits is odd, then add to
        // the number of multiples
        if (__builtin_popcount(counter) & 1)
            odd += (100 / p);
        else
            even += 100 / p;
    }

    return odd - even;
}

我只是不明白这个 for 循环的真正作用

    for (j = 0; j < n; j++) {

        /* Check if jth bit in the counter is set
         If set then pront jth element from set */
        if (counter & (1 << j)) {
            p *= a[j];
        }
    }

以及这部分

// if set bits is odd, then add to
        // the number of multiples
        if (__builtin_popcount(counter) & 1)
            odd += (100 / p);
        else
            even += 100 / p;

给出的解释我不明白

The numbers that are formed by multiplication of an odd number of prime numbers will be added and the numbers formed by multiplication of even numbers will thus be subtracted to get the total number of multiples in the range 1 to M.

请有人帮我解决这个逻辑，以便在 java 中实现它吗？

提前致谢:)

Answer 1

外部循环用于从输入数组生成质因数的所有可能子集。 counter 中的每一位代表数组中的位置。

内部循环检查 counter 中的每一位，如果该位被设置，它将数组中相应的质数乘以 p ，正在检查的子集的所有素因数的乘积。例如，给定素数数组 {3, 5, 7} :

counter bits factors            product
1       001  a[0]               3
2       010  a[1]               5
3       011  a[0] * a[1]        15
4       100  a[2]               7
5       101  a[0] * a[2]        21
6       110  a[1] * a[2]        35
7       111  a[0] * a[1] * a[2] 105

C++ 内置函数 __builtin_popcount(counter)计算 counter 中设置的位数。 Java 等效项是 Integer.bitCount() 。用于测试p中是否包含因子个数。是奇数(如果是，则结果的低位将被设置...这可以通过其他方式检查，例如 if (Integer.bitCount(counter) % 2 == 1) )。

最后是p的倍数小于m (在您的情况下为 500)被计算，并且如果 p 中的因子数量添加到包含集中。为奇数，如果为偶数则排除集。

请注意，C++ 示例中存在一个错误，它忽略了 m参数并使用硬编码值 100 .

在 Java 中:

public class IncExc {
    public static void main(String[] args) {
        int a[] = {3, 5, 7};
        int m = 500;
        System.out.println(count(a, m));
    }

    static int count(int a[], int m) {
        int odd = 0;
        int even = 0;
        int powSetSize = 1 << a.length;

        // For all sub-sets of elements in the array of primes
        for (int counter = 1; counter < powSetSize; counter++) {
            int p = 1;
            for (int j = 0; j < a.length; j++) {
                // If the jth bit of this combination is set then multiply in the jth element
                if ((counter & (1 << j)) != 0) {
                    p *= a[j];
                }
            }

            // If the number of factors in p is odd, accumulate the count of multiples in our "odd" register
            // Otherwise use the "even" register
            if ((Integer.bitCount(counter) & 1) == 1)
                odd += m / p;
            else
                even += m / p;
        }

        return odd - even;
    }
}