# Codingame Solution: Magic count of numbers

Original Problem

You should calculate a count of natural numbers not greater than n and divisible at least by one of k given primes.
For example, you are given:
n = 25
k = 2
p = {2, 5}
The numbers are: 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 22, 24, 25.
Input
Line 1: An integer n and an integer k
Line 2: k space separated primes $$p_i (1\leq i\leq k)$$
Output
A single line containing a one integer - count of numbers.
Constraints
1<=n<=10^13
1<=k<=10
2<=p_i<40

## Solution

The idea is this, for a list from 1 to n, the number of numbers that are divisible by prime $$p_i$$ is $$\left\lfloor\frac{n}{p_i}\right\rfloor$$. When we sum over all these numbers however, we count too much, since every product of 2-combination of the primes is counted twice. When we subtract them, we remove too many 3-combinations, so we need to add them again. As an example with primes 2,3,5 and n equals 30:

 1
2 O
3 O
4 O
5 O
6 OO
7
8 O
9 O
10 OO
11
12 OO
13
14 O
15 OO
16 O
17
18 OO
19
20 OO
21 O
22 O
23
24 OO
25 O
26 O
27 O
28 O
29
30 OOO

Now the solution is $$\left\lfloor\frac{30}{2}\right\rfloor+\left\lfloor\frac{30}{3}\right\rfloor+\left\lfloor\frac{30}{5}\right\rfloor-\left\lfloor\frac{30}{2\cdot 3}\right\rfloor-\left\lfloor\frac{30}{2\cdot 5}\right\rfloor-\left\lfloor\frac{30}{3\cdot 5}\right\rfloor+\left\lfloor\frac{30}{2\cdot3\cdot5}\right\rfloor$$. This pattern continues and when implemented in Ruby, this algorithm is super small:

n, k = gets.split.map(&:to_i)
primes = gets.split.map(&:to_i)

p (1..k).inject(0) {|sum, i|
sum - (-1) ** i * primes.combination(i).inject(0) {|sum, a| sum + n / a.inject(:*) }
}

« Back to problem overview