Bội số nguyên tố

Cho số nguyên $n$ và $k$ số nguyên tố phân biệt $a_1,a_2,\dots ,a_k$. Đếm số lượng số nguyên trong đoạn $[1,n]$ chia hết cho ít nhất một trong $k$ số nguyên tố đã cho.

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $k$.
• Dòng hai: $k$ số nguyên tố $a_1,a_2,\dots ,a_k$.

Dữ liệu ra

In một số nguyên — số lượng số nguyên trong $[1,n]$ chia hết cho ít nhất một $a_i$.

Ràng buộc

• $1\le n\le {10}^{18}$
• $1\le k\le 20$
• $2\le a_i\le n$, $a_i$ là số nguyên tố, đôi một phân biệt

Ví dụ