Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
An = list(map(int, input().split()))

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx + 1, len(An)):
            if An[i] != 0 and An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                    flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

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

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
An = list(map(int, input().split()))

An.sort()

idx = 0

while True:
    if idx >= len(An):
        print(len(An))
        exit()

    flg = False
    div_idx = idx + 1

    while True:
        if div_idx == len(An):
            break

        if An[div_idx] % An[idx] == 0:
            if An[div_idx] == An[idx]:
                flg = True
            An.pop(div_idx)
        else:
            div_idx += 1

    if flg:
        An.pop(idx)

    idx += 1


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

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
An = list(map(int, input().split()))

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx+1, len(An)):
            if An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                   flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

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

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))