AT_abc170_d [ABC170D] Not Divisible

题目描述

给定一个长度为 $N$ 的数列 $A$。

请你求出满足以下性质的整数 $i$ 的个数（$1 \leq i \leq N$）：

• 对于任意的整数 $j$（$1 \leq j \leq N$，且 $i \neq j$），$A_i$ 不能被 $A_j$ 整除。

输入格式

输入以如下格式从标准输入中给出。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出答案。

样例 1

输入

5
24 11 8 3 16

输出

3

样例 2

输入

4
5 5 5 5

输出

0

样例 3

输入

10
33 18 45 28 8 19 89 86 2 4

输出

5

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^6$

样例解释 1

满足题目性质的是 $2$、$3$、$4$。

样例解释 2

请注意存在相同数字的情况。

由 ChatGPT 4.1 翻译