Problem p02642 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


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

    # 愚直に行うとO(N^2)となる
    # 各要素、約数を列挙(sqrt(N))
    # 約数がこれまでに存在したかをチェックO(1)*約数の個数
    # 存在すれば1を加える

    # print(A)
    ans = 0
    history = [False]*N
    for i in range(N):
        if history[i]:
            continue
        # A[i]を乗じていくとどうか
        k = i
        for j in range(2, A[-1]//A[i] + 1):
            k = bisect_left(A, A[i]*j, lo=k)
            # print(A[i], A[i]*j, k, A[k])
            if A[k] % A[i] == 0:
                history[k] = True
        #
        k = bisect_left(A, A[i])
        if k < i:
            history[i] = True
        if i+1 < N and A[i] == A[i+1]:
            history[i] = True
    print(N-sum(history))

    return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


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

    # 愚直に行うとO(N^2)となる
    # エラトステネスの篩を真似ると、NlogNで済む
    # 同じ数字が存在している場合は、注意する

    table = [False]*(A[-1]+1)
    ans = 0
    for i in range(N):
        # すでに何かの倍数ならば、考える必要なし
        if table[A[i]]:
            continue
        # 最大値まで見ていく
        for j in range(2, A[-1]//A[i]+1):
            table[A[i]*j] = True

    ans = 0
    for i in range(N):
        if table[A[i]] is False:
            ans += 1
            if i == 0:
                if A[0] == A[1]:
                    ans -= 1
            elif i == N-1:
                if A[N-1] == A[N-2]:
                    ans -= 1
            else:
                if A[i] == A[i-1] or A[i] == A[i+1]:
                    ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


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

    # 愚直に行うとO(N^2)となる
    # エラトステネスの篩を真似ると、NlogNで済む
    # 同じ数字が存在している場合は、注意する

    table = [False]*(A[-1]+1)
    ans = 0
    for i in range(N):
        # すでに何かの倍数ならば、考える必要なし
        if table[A[i]]:
            continue
        # 最大値まで見ていく
        for j in range(2, A[-1]//A[i]+1):
            table[A[i]*j] = True

    ans = 0
    for i in range(N):
        if table[A[i]] is False:
            ans += 1
            if i == 0 and A[0] == A[1]:
                ans -= 1
            elif A[i] == A[i-1]:
                ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


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

    # 愚直に行うとO(N^2)となる
    # 各要素、約数を列挙(sqrt(N))
    # 約数がこれまでに存在したかをチェックO(1)
    # 存在すれば1を加える

    ans = 0
    past = set()
    for i in range(len(A)):
        flag = False
        for d in divisors(A[i]):
            if d in past:
                flag = True
                break
        if flag:
            ans += 1
        past.add(A[i])

    if A[0] != A[1]:
        print(N-ans)
    else:
        print(N-ans-1)

    return


if __name__ == '__main__':
    main()