#T2167. 素数倍数(Prime Multiples)

素数倍数(Prime Multiples)

链接: https://cses.fi/problemset/task/2185

板块: Mathematics

时限: 1.00 s | 内存: 512 MB

题目描述

给定 kk 个不同的素数 a1,a2,…,aka_1,a_2,\ldots,a_k 和一个整数 nn。

你的任务是计算前 nn 个正整数中有多少个能被给定的至少一个素数整除。

输入

第一行输入包含两个整数 nn 和 kk。

第二行包含 kk 个素数 a1,a2,…,aka_1,a_2,\ldots,a_k。

输出

输出一个整数:在区间 1,2,…,n1,2,\ldots,n 中能被至少一个给定素数整除的整数个数。

数据范围

1≤n≤10181 \le n \le 10^{18} 1≤k≤201 \le k \le 20 2≤ai≤n2 \le a_i \le n

样例输入

20 2
2 5

样例输出

12