numbers not divisible by all array elements

Question

Given an array of 3 elements :- 2,4,5 and given a number n = 10 Find count of all numbers in the range 1 to n which are not dvisible by multiple of all array elements.

output:- 4 (1,3,7,9)

Any better approach brute force? n is in the range of 1 to 10^9

Answer 1

take a hashset and put all multiples of the arrayElements lesser than n and subtract the set size.

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());