# Codingame Solution: Magic count of numbers

`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.

The answer is 15.

**Input**

**Line 1:**An integer

`n`and an integer

`k`

**Line 2:**

`k`space separated primes \(p_i (1\leq i\leq k)\)

**Output**

**Constraints**

`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(:*) } }