算法

(数学) $O(1e6)$

注意到本题的范围，暴力肯定是过不去的。
我们不妨换个思路，先开个$bool$数组，然后预处理一下$a[i]$的不含自身的倍数，把他们都置为$true$。
如果某个元素仅出现一次且他不是其他元素的倍数的话，我们可以将这个数计入答案。

C++ 代码

#include <iostream>
using namespace std;

int n;
int a[200000];
int cnt[1000001];
bool ng[1000001];

int main() {
    int i, j;

    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }

    for (i = 1; i <= 1000000; i++) {
        if (cnt[i] > 0) {
            for (j = i * 2; j <= 1000000; j += i) {
                ng[j] = true;
            }
        }
    }

    int ans = 0;
    for (i = 1; i <= 1000000; i++) {
        if (cnt[i] == 1 && !ng[i]) {
            ans++;
        }
    } 
    cout << ans << endl;
    return 0;
}