Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
import numpy as np
U = 10 ** 6 + 1

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

C = Counter(A)
memo = np.zeros(U, dtype=bool)
tmp = np.arange(U)
ans = 0

for k in sorted(C.keys()):
    if memo[k]:
        continue
    if C[k] == 1:
        ans += 1
    memo[tmp % k == 0] = True
print(ans)

Fixed submission:
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import chain


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


N = int(input())
A = list(map(int, input().split()))
prime = prime_set(10 ** 6 + 1)


C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a, v in C.items():
    if v >= 2:
        ans += v
        continue
    if a in prime:
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)

Fixed submission:
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

U = 10 ** 6 + 1
memo = np.zeros(U, dtype=int)
tmp = np.arange(U)
ans = 0

for k in sorted(C.keys()):
    v = C[k]
    if v >= 2:
        ans += v
        if not memo[k]:
            memo[tmp % k == 0] = 1
        continue
    if memo[k]:
        ans += 1
    else:
        memo[tmp % k == 0] = 1

print(N-ans)

Fixed submission:
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a, v in C.items():
    if v >= 2:
        ans += v
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)

Fixed submission:
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()

C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a in A:
    if C[a] >= 2:
        ans += 1
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)

Fixed submission:
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)