Count Integers <= N Divisible by at Least One of k Primes

In the Census Bureau of Prime City, the Statistician must count how many integers from 1 to N are divisible by at least one of k given primes. The inclusion-exclusion principle is the key: add counts for individual primes, subtract for pairs, add for triples, and so on. "Inclusion-exclusion: |A1 Ôê¬ A2 Ôê¬ ... Ôê¬ Ak| = sum of |Ai| - sum of |Ai Ôê® Aj| + sum of |Ai Ôê® Aj Ôê® Ak| - ...," the Statistician says. "The intersection of sets for primes pi is just the count of multiples of their product." Given N and k primes, count integers from 1 to N divisible by at least one of the primes. Use bitmask enumeration over subsets. Constraints: 1 <= N <= 10^9, 1 <= k <= 15, primes <= 10^9 Input: 10 2 2 3 Output: 7 Input: 20 3 2 3 5 Output: 14