こんにちは。コンテスト中には計算量が$O(N^2)$となる解法しか思いつかずTLEしました。(表現を訂正しました。)まだ基本アルゴリズムも覚えていないのでちゃんと使いこなせるようにしたいところです。この問題はエラトステネスの篩と同じ原理を使うとかなり計算量が節約できるようです。
code.py
N = int(input())
A = list(map(int, input().split()))
A.sort() #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1) #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
p = A[i]
if dp[p] == 1: #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
for q in range(Amax//p+1):
dp[p*q] = 0 #A[i]の倍数をすべて0にする
if A[i] != A[i+1]:
ans += 1 #A[i]が重複していなければカウント
if dp[Amax] == 1: #重複チェック時にレンジオーバーするためAmaxだけ別で判定
ans += 1
print(ans)
dpは初期状態では
dp = [1 1 1 1 1 1 1 ...] となっています。
たとえば、
A[0]=3なら、一回操作後のdpは
dp = [0 1 1 0 1 1 0 ...] となります。