Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = set([i for i in range(n)])

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1

    if i in erat:
        kouho.append(arr[i])

        dis = []
        for val in erat:
            if arr[val]%arr[i] == 0:
                dis.append(val)
        for d in dis:
            if len(erat) > 0:
                erat.discard(d)

    # print(erat)

# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Fixed submission:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = set([i for i in range(n)])

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1

    if i in erat:
        kouho.append(arr[i])

        dis = []
        for val in erat:
            if arr[val]%arr[i] == 0:
                dis.append(val)
        for d in dis:
            if len(erat) > 0:
                erat.discard(d)

    # print(erat)

# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Fixed submission:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
    tp = arr[i]
    while True:
        erat[tp] = False
        tp += arr[i]
        if tp > 10**6:
            break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Fixed submission:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1

    flag = True
    for j in range(i):
        # print(arr[j],end=" ")
        if arr[j] > arr[i]//2+1:
            break
        if arr[i]%arr[j] == 0:
            flag = False

    if flag:
        kouho.append(arr[i])

# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
       ans += 1

print(ans)

Fixed submission:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):


n = int(input())
arr = list(map(int,input().split()))

nums = {}
for a in arr:
    if a not in nums:
        nums[a] = 1
    else:
        nums[a] += 1

# def factorize(N):
#     up = int(np.sqrt(N))+2
#     out = {}
#
#     for i in range(2,up):
#         if N%i == 0:
#             temp = N
#             count = 0
#             while(True):
#                 N = N//i
#                 count += 1
#                 if N%i != 0:
#                     break
#             out[i] = count
#         else:
#             continue
#     if N != 1:
#         out[N] = 1
#     return out

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)

    # divisors.sort()
    return divisors

# print(nums)
ans = 0
for i in range(n):
    f = make_divisors(arr[i])
    # print(f)
    cnt = 0
    for key in f:
        if key == arr[i]:
            if key in nums and nums[key] > 1:
                cnt += 1
        else:
            if key in nums:
                cnt += 1

    if cnt == 0:
        ans += 1

print(ans)


Fixed submission:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)