Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in arr:
    if tmp[i] >= 2:
        continue
    flg = True
    for k in range(1,int(i**0.5)+1):
        if i % k == 0:
            if tmp[k] != 0 and i != k:
                flg = False
                break
            if k != i // k:
                if tmp[i // k] != 0 and i // k != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Fixed submission:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    target = arr[i]
    if tmp[target] >= 2:
        continue
    flg = True
    for k in range(1,int(target**0.5)+1):
        if target % k == 0:
            if tmp[k] != 0 and target != k:
                flg = False
                break
            if k != target // k:
                if tmp[target // k] != 0 and target // k != target:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Fixed submission:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    if tmp[arr[i]] >= 2:
        continue
    flg = True
    for k in range(1,int(arr[i]**0.5)+1):
        if arr[i] % k == 0:
            if tmp[k] != 0 and arr[i] != k:
                flg = False
                break
            if k != arr[i] // k:
                if tmp[arr[i] // k] != 0 and arr[i] // k != arr[i]:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Fixed submission:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    flg = True
    for k in make_divisors(arr[i]):
        if k == arr[i]:
            if tmp[k] >= 2:
                flg = False
                break
        elif tmp[k] != 0:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Fixed submission:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(len(arr)):
    flg = True
    for k in make_divisors(arr[i]):
        if k == arr[i]:
            if tmp[k] >= 2:
                flg = False
                break
        elif tmp[k] != 0:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Fixed submission:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)