Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)

    return sorted(ans)


def main():
    N = int(input())

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

    # is_in_A_flag = [0] * (10**6+1)
    is_in_A_flag = {f"{i}": 0 for i in range(10**6+1)}

    for a in A:
        is_in_A_flag[f"{a}"] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[f"{b}"] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[f"{B[i][-1]}"] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())


Fixed submission:
# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)

    return sorted(ans)


def main():
    N = int(input())

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

    is_in_A_flag = [0] * (10**6+1)

    for a in A:
        is_in_A_flag[a] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[b] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())


Fixed submission:
# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)
    
    return sorted(ans)


def main():
    N = int(input())

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

    is_in_A_flag = [0] * (10**6+1)

    for a in A:
        is_in_A_flag[a] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        for b in B[i][:-1]:
            if is_in_A_flag[b] > 0:
                is_ans = False
                break
        
        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())


Fixed submission:
# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)
    
    return sorted(ans)


def main():
    N = int(input())

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

    is_in_A_flag = [0] * (10**6+1)

    for a in A:
        is_in_A_flag[a] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        for b in B[i][:-1]:
            if is_in_A_flag[b] > 0:
                is_ans = False
                break
        
        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())


Fixed submission:
# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())