7658: [CSES Problem Set] Prime Multiples
[Creator : ]
Description
You are given $k$ distinct prime numbers $a_1,a_2,\ldots,a_k$ and an integer $n$.
Your task is to calculate how many of the first $n$ positive integers are divisible by at least one of the given prime numbers.
Your task is to calculate how many of the first $n$ positive integers are divisible by at least one of the given prime numbers.
Input
The first input line has two integers $n$ and $k$.
The second line has $k$ prime numbers $a_1,a_2,\ldots,a_k$.
The second line has $k$ prime numbers $a_1,a_2,\ldots,a_k$.
Output
Print one integer: the number integers within the interval $1,2,\ldots,n$ that are divisible by at least one of the prime numbers.
Constraints
$1≤n≤10^{18}$
$1 \le k \le 20$
$2 \le a_i \le n$
$1 \le k \le 20$
$2 \le a_i \le n$
Sample 1 Input
20 2
2 5
Sample 1 Output
12
The 12 numbers are 2,4,5,6,8,10,12,14,15,16,18,20.