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):
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    i = 0
    for j in A:
        if i == j:
            d[i] = 1
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            if d[i] == 0:
                ans += 1
print(ans)

N = int(input())
A = list(input().split())
A.sort()
d = []
ans = 0
while A:
    a = A.pop(0)
    f = 0
    for p in d:
        if a % p == 0:
            f = 1
            break
        else:
            d.append(a)
    if f == 0:
        if a ==A[0]:
            while a == A[0]:
                A.pop(0)
        else:
            ans += 1
print(ans)

N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for j in A:
        if i == j:
            d[i] = 1
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            if d[i] == 0:
                ans += 1
print(ans)

N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in A:
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            if A.count(i) == 1:
                ans += 1
print(ans)

N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
            continue
        i = j
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Accepted