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