Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    A.sort()
    ret = 0
    used = [False] * N
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    counts = {}
    for a in A:
        if not a in counts:
            counts[a] = 0
        counts[a] += 1

    M = max(A)
    s = set(A)
    ret = 0
    used = [False] * (M + 1)
    for i in range(1, M + 1):
        if used[i]:
            continue
        if not i in s:
            continue
        if counts[i] == 1:
            ret += 1
        j = 1
        while i * j <= M:
            used[i * j] = True
            j += 1
    print(ret)


def _hoge(N, A):
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    A.sort()
    s = set(A)
    ret = 0
    found_1 = False
    for idx, v in enumerate(A):
        ok = found_1 or (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        if not ok:
            for i in range(2, 1001):
                if v == i:
                    continue
                if v % i == 0 and (i in s or v // i in s):
                    ok = True
                    break
        if not ok:
            ret += 1
        found_1 = found_1 or v == 1
    print(ret)

def solve_(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set(A)
    tmp2 = []
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if ok or p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        #print(v, ok)
        if not ok:
            for t in A:
                if t == v:
                    continue
                #if ok or t * t > v:
                #    break
                if v % t == 0:
                    ok = True
                    break
        if ok:
            pass
        else:
            #tmp.add(v)
            #tmp2.append(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    counts = {}
    for a in A:
        if not a in counts:
            counts[a] = 0
        counts[a] += 1

    M = max(A)
    s = set(A)
    ret = 0
    used = [False] * (M + 1)
    for i in range(1, M + 1):
        if used[i]:
            continue
        if not i in s:
            continue
        if counts[i] == 1:
            ret += 1
        j = 1
        while i * j <= M:
            used[i * j] = True
            j += 1
    print(ret)


def _hoge(N, A):
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set(A)
    tmp2 = []
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if ok or p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        #print(v, ok)
        if not ok:
            for t in A:
                if t == v:
                    continue
                #if ok or t * t > v:
                #    break
                if v % t == 0:
                    ok = True
                    break
        if ok:
            pass
        else:
            #tmp.add(v)
            #tmp2.append(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    counts = {}
    for a in A:
        if not a in counts:
            counts[a] = 0
        counts[a] += 1

    M = max(A)
    s = set(A)
    ret = 0
    used = [False] * (M + 1)
    for i in range(1, M + 1):
        if used[i]:
            continue
        if not i in s:
            continue
        if counts[i] == 1:
            ret += 1
        j = 1
        while i * j <= M:
            used[i * j] = True
            j += 1
    print(ret)


def _hoge(N, A):
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()