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.
Line 2:k space separated primes \(p_i (1\leq i\leq k)\)
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(:*) }
}