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的因子个数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;
    }
}