arrays - 不能被所有数组元素整除的数字

Question

给定一个由 3 个元素组成的数组：- 2,4,5 并给定一个数字 n = 10 查找 1 到 n 范围内的所有数字的计数，这些数字不能被所有数组元素的倍数整除。

输出：- 4 (1,3,7,9)

有没有更好的方法蛮力？n 在 1 到 10^9 的范围内

Answer 1

取一个哈希集并将所有小于 n 的 arrayElements 的倍数减去集合大小。

int n = 10;
    int k = 3;
    int[] jump = { 2, 5, 4 };
    Set<Integer> jumpSet = new HashSet<Integer>();
    for (int i = 0; i < jump.length; i++) {
        if (!jumpSet.contains(jump[i])) {
            for (int j = 1; j <= n / jump[i]; j++)
                jumpSet.add(jump[i] * j);
        }
    }
    System.out.println(n - jumpSet.size());