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

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