Problem: Given is a number sequence A of length N.  Find the number of integers i \left(1 \leq i \leq N\right) with the following property:    * For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Submission attempts (in order):
from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    for a, v in A.items():
        if v > 1:
            continue
        if 1 in A:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

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

print(main())


from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    for a, v in A.items():
        if v > 1:
            continue
        if a > 1 and 1 in A:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

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

print(main())



from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    if 1 in A:
        if A[1] == 1:
            return 1
        return 0
    for a, v in A.items():
        if v > 1:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

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

print(main())



from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    if 1 in A:
        if A[1] == 1:
            return 1
        return 0
    for a, v in A.items():
        if v > 1:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

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

print(main())



from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    if 1 in A:
        if A[1] == 1:
            return 1
        return 0
    for a, v in A.items():
        if v > 1:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

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

print(main())



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    dp = [False] * (A[-1] + 1)
    r = 0

    for i, a in enumerate(A):
        if dp[a]:
            continue
        dp[a::a] = [True] * len(dp[a::a])
        if i < N - 1 and A[i + 1] == a:
            continue
        r += 1
    return r


print(main())


Verdicts: Wrong Answer

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted