题目内容

已知所有大于 $1$ 的整数都可以被唯一分解成质数的乘积，我们把这组质数称为该整数的质因子；如：$12=2\times2\times3$，$12$ 的质因子为 $[2,3]$，$7=1\times7$，$7$ 的质因子为 $[7]$。

现给定一个正整数 $n$ 和一个质数列表 $\text{nums}$（数字严格递增），请统计数字 $1\sim n$ 之中，有哪些数字的质因子仅出现在列表 $\text{nums}$ 内，返回符合条件的数字数量。

注意：数字 $1$ 无质因子，作为符合条件的数字纳入统计。

质数定义：大于 $1$ 的自然数，除了 $1$ 和它自身外不能被其他自然数整除的数。

数据范围：整数 $n$ 范围：$1\le n\le10^{12}$；列表 $\text{nums}$ 长度 $m$ 范围：$1\le m\le5$。

输入描述

输入为一行，包含正整数 $n$，质数列表长度 $m$，以及质数列表 $\text{nums}$（以数组形式给出），格式为 n,m,[p1,p2,...,pm]。

输出描述

输出一个整数，表示 $1\sim n$ 中质因子仅出现在列表 $\text{nums}$ 内的数字数量。

样例1

输入

10,2,[2,3]

输出

7

说明

输入参数：上限 $n=10$，质数个数 $m=2$，允许质因子列表 $[2,3]$

统计所有 $\le 10$ 且质因子仅为 $2$、$3$ 的正整数：

• $1$（无质因子）
• $2$ $(2)$
• $3$ $(3)$
• $4$ $(2^2)$
• $6$ $(2\times3)$
• $8$ $(2^3)$
• $9$ $(3^2)$

共 $7$ 个，返回结果 $7$。

样例2

输入

15,3,[2,3,5]

输出

11

说明

输入参数：上限 $n=15$，质数个数 $m=3$，允许质因子列表 $[2,3,5]$

统计所有 $\le 15$ 且质因子仅为 $2$、$3$、$5$ 的正整数：

• $1$（无质因子）
• $2$ $(2)$
• $3$ $(3)$
• $4$ $(2^2)$
• $5$ $(5)$
• $6$ $(2\times3)$
• $8$ $(2^3)$
• $9$ $(3^2)$
• $10$ $(2\times5)$
• $12$ $(2^2\times3)$
• $15$ $(3\times5)$

共 $11$ 个，返回结果 $11$。