AtCoder Beginner Contest 170 [ D - Not Divisible ] https://atcoder.jp/contests/abc170/tasks/abc170_d

abc170_d.py

'''
[問題]
https://atcoder.jp/contests/abc170/tasks/abc170_d

[解説]
https://youtu.be/IhnlLGb-rzg?t=1775
　snukeさんの説明に基づいて実装している

[結果]
Python(3.8.2) AC 509ms
PyPy3(7.3.0) AC 134ms
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N = int(input())
A = list(map(int, input().split()))

#A_MAX = 10**6 + 1  # これTLE
A_MAX = max(A) + 1
f = [0] * (A_MAX + 1)

# f[j]にjの約数がAの中に何個入っているかを保存する
# 計算量はO(A_MAX x log(A_MAX))。調和級数
for a in A:
    for j in range(a, (A_MAX+1), a):
        f[j] += 1

ans = 0
for a in A:
    # aの約数の数が1ならば、自分自身しか割れる数が存在しない
    if f[a] == 1:
        ans += 1

print(ans)