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

外层循环用于从输入数组中生成所有可能的 sub-sets 质因数。 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 参数并使用 hard-coded 值 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;
    }
}

java 中的包含和排除主体

Inclusion and exclusion principal in java

c++

java

logic

combinatorics

discrete-mathematics