Problem:


Score : 400 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
A = []
for a in C:
    if C[a]==1:
        A.append(a)
if len(A)==0:
    print(0)
else:
    A = sorted(A)
    N = len(A)
    amax = A[-1]
    P = [0 for _ in range(amax+1)]
    for i in range(N):
        P[A[i]] = 1
    for i in range(N):
        a = A[i]
        for j in range(a*2,amax+1,a):
            P[j] = 0
    print(sum(P))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
amax = A[-1]
P = [0 for _ in range(amax+1)]
for i in range(N):
    P[A[i]] = 1
for i in range(N):
    a = A[i]
    for j in range(a*2,amax+1,a):
        P[j] = 0
print(sum(P))

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
a.sort()
k=max(a)
dp=[1]*(k+1)
ans=0
for i in range(N):
  if dp[a[i]]==1:
    ans+=1
    for j in range(a[i],k+1,a[i]):
      dp[j]=0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]+1
dp = [0]*(m*2)
ans = 0

#print(A)
#print(A[-1])
#print(m)
#print(dp)

total = 0
for i in range(N):
#    print('i === ' ,i, A[i])
    chk = -1
    for j in range(i):
        if int(A[i]) / 2 < int(A[j]):
            break
                            
#        print('j =', j, A[j])
        if int(A[i]) % int(A[j]) == 0:
            chk = 1
            break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
n = int(input(()))
a = list(map(int,input().split()))

dp = [0]*(10**6 + 1)
ans = 0

for i in a:
    if dp[i] == 0:
        for j in range(1,10**6+1):
            if i * j > 10**6:
                break
            dp[i*j] += 1
    elif dp[i] == 1:
        dp[i] += 1

for i in a:
    if dp[i] == 1:
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))

ng_numbers = []
max_number = 10 ** 6
counter = 0
prev = 0
for ai in A:
    if ai == prev:
        counter -= 1
        prev = 0
    if ai not in ng_numbers:
        counter += 1
        prev = ai
    ng_numbers.extend(range(ai, max_number, ai))
print(counter)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_s = sorted(list(set(a)))
    if len(a_s) == 1:
        print(0)
        exit()
    max_a = a_s[-1]
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a_s:
        if b[i]:
            sived(i)
    ans = 0
    for i in range(len(a)-1):
        if a[i] != a[i+1]:
            if b[a[i]]:
                ans += 1
    if b[max_a]:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_s = sorted(list(set(a)))
    if len(a_s) == 1:
        print(0)
        exit()
    max_a = a_s[-1]
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a_s:
        if b[i]:
            sived(i)
    ans = 0
    for i in range(len(a)-1):
        if a[i] != a[i+1]:
            if b[a[i]]:
                ans += 1
    if a[-1] != a[-2]:
        if b[a[-1]]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==True:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
            if a<=math.sqrt(Amax):
                m=1
                while (a*m)<=Amax:
                    dp[a*m-1]=False
                    m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==True:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
        if a<=math.sqrt(Amax):
            m=1
            while (a*m)<=Amax:
                dp[a*m-1]=False
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []
    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    for k in del_list:
        del c[k]
    a = sorted(c.keys())
    if len(a) == 0:
        print(0)
        exit()
    max_a = a[-1]
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []

    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    for k in del_list:
        del c[k]
    a = sorted(c.keys())
    if len(a) == 0:
        print(0)
        exit()
    max_a = max(a)
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a+1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []

    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    for k in del_list:
        del c[k]
    a = c.keys()
    if len(a) == 0:
        print(0)
        exit()
    max_a = max(a)
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a+1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
counter = 0
Amax = A[-1]
A.append(0)
dp = [True for i in range(Amax)]

for i in range(len(A)-1):
    p = A[i]
    if dp[p-1]:
        for j in range(Amax//p):
            if dp[p*(j+1)-1]:
                dp[p*(j+1)-1] = False
            else:
                break
        if p != A[i+1]:
            counter += 1
    else:
        continue

print(counter)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int, input().split()))
P.sort()

ans_list=[]
for i in range(N):
    ans_list.append(P.pop(0))
    for j in range(len(P)-1,-1,-1):
        if P[j]%ans_list[-1]==0:
            P.pop(j)
    if len(P)==0:
        break

print(len(ans_list))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []
    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    for k in del_list:
        del c[k]
    a = c.keys()
    if len(a) == 0:
        print(0)
        exit()
    max_a = max(a)
    b = [True] * (max_a + 1)
    c = Counter(a)


    def sived(x):
        for not_ans in range(x+x, max_a+1, x):
            b[not_ans] = False
    b[0] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1

    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]

N = int(input())
A = list(map(int, input().split()))
A_sorted = count_sort(A)

divisible = False
if N != 1 and A_sorted[0] == A_sorted[1]:
  ans = 0
else:
  ans = 1

for i in range(N-1, 0, -1):
  for j in range(0, i):
    if A_sorted[i]%A_sorted[j] == 0:
      divisible = True
      break
  if not divisible:
    ans += 1
  divisible = False

print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

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

A.sort()

count = 0

dp = [True for i in range(max(A))]

for i in range(len(A)):
    if i != 0:
        if A[i] == A[i-1]:
            dp[A[i]-1] = False
            continue
    if dp[A[i]-1]:
        for j in range(2,max(A)):
            try:
                if dp[A[i]*j-1]:
                    dp[A[i]*j-1] = False
                else:
                    break
            except:
                break
    else:
        continue

counter = 0

for i in A:
    if dp[i-1]:
        counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
a_max=max(a)

check = [0]*(a_max+1)

for i in a:
    if check[i] == 1:
        check[i] = 0
        continue
    if check[i] == 0:
        check[i] = 1
        for j in range(1,a_max//i):
            check[(j+1)*i] = 2

print(check.count(1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(list(set(a)))
    if len(a) == 1:
        print(0)
        exit()
    b = [True] * (a[-1] + 1)
    c = Counter(a)


    def sived(x):
        for not_ans in range(x+x, a[-1]+1, x):
            b[not_ans] = False
    b[0] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += c[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math


def int1(x): return int(x) - 1
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def mi1(): return map(int1, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def lli(rows_number): return [li() for _ in range(rows_number)]


if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(list(set(a)))
    if len(a) == 1:
        print(0)
        exit()
    b = [True] * (a[-1] + 1)


    def sived(x):
        for not_ans in range(x+x, a[-1]+1, x):
            b[not_ans] = False
    b[0] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(b)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

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

A.sort()

count = 0

dp = [True for i in range(max(A))]

for i in range(len(A)):
    if i != 0:
        if A[i] == A[i-1]:
            dp[A[i]-1] = False
            continue
    if dp[A[i]-1]:
        for j in range(2,math.floor(max(A)/A[i]+1)):
            if dp[A[i]*j-1] and A[i]*j <= max(A):
                dp[A[i]*j-1] = False
            else:
                break
    else:
        continue

counter = 0

for i in A:
    if dp[i-1]:
        counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
sum_num = 0
same = 0

a_list_sorted = sorted(a_list, reverse=True)
for i in range(n):
    # 末尾判定
    if i+1 == n:
        # 同じのあるか
        if a_list_sorted[i-1] == a_list_sorted[i]:
            # print('a')
            break
        # ないなら＋１
        else:
            # print('b')
            sum_num += 1
            break
    # 次の要素と同じならcontinue
    if a_list_sorted[i] == a_list_sorted[i+1]:
        # print('c')
        continue

    a_i = a_list_sorted[i]
    # 後ろから判定して同じところくるまでに割れなければ＋１
    for j in reversed(range(i, n)):
        # print('i:{}, j:{}'.format(a_list_sorted[i], a_list_sorted[j]))
        # ループ回りきったら+1
        if i == j:
            # print('e')
            # print('a_i:{}, a_j:{}'.format(a_i, a_list_sorted[i]))
            sum_num += 1

        # 割れたらbreak
        if a_i % a_list_sorted[j] == 0:
            # print('d')
            break
        

print(sum_num)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

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

A.sort()

count = 0

dp = [0 for i in range(max(A))]

for i in A:
    if dp[i-1] == 0:
        for j in range(2,math.floor(max(A)/i+1)):
            if dp[i*j-1] == 0 and i*j <= max(A):
                dp[i*j-1] = 1
            else:
                break
    else:
        continue

counter = 0

for i in A:
    if dp[i-1] == 0:
        counter += 1
        dp[i-1] = 2
    elif dp[i-1] == 2:
        counter -= 1
        dp[i-1] = 1

print(counter)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))

M=max(A)
check=[0]*(M+1)
for i in range(N):
    a=A[i]
    if check[a]>0:
        continue
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,K,i):
      Flag[j] = 0
s = set(List)
res += len(s)- len(List)
print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()
A = sorted(A)

kasanari = []
count = [0]*(10**6+1)
for a in A:
    count[a] += 1
    if (count[a] > 1):
        kasanari.append(a)

erasut = np.ones(A[-1]+1)
for a in set(A):
    if(a*2 < A[-1]+1):
        erasut[a*2::a] = 0
print(int(sum(erasut[list(set(A))])) - len(set(kasanari)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()
A = sorted(A)
count = [0]*(10**6+1)
kasanari = []
for a in A:
    count[a] += 1
    if (count[a] > 1):
        kasanari.append(a)

ok_lis = []
for a in set(A):
    is_ok = True
    for ok in ok_lis:
        if (a % ok == 0):
            is_ok = False
            break
    if (is_ok):
        ok_lis.append(a)
ans = set(ok_lis) - set(kasanari)
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()

sortList = sorted(AList)
Amax = max(sortList)
dp = [0] * (Amax+1)

idx = 0
for n in sortList:
  dp[n] += 1
  if dp[n] == 1:
    for j in range(n*2, Amax+1, n):
      dp[j] += 2
print(dp.count(1))

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()
  
sortList = list(sorted(set(AList)))
Amax = max(sortList)
dp = [True] * (Amax+1)

idx = 0
for n in sortList:
  if dp[n] == True:
    for j in range(n*2, Amax, n):
      dp[j] = False
ansCount = 0
for n in sortList:
  if dp[n] == True:
    ansCount += 1
print(ansCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()
  
sortList = list(sorted(set(AList)))
Amax = max(sortList)
dp = [True] * (Amax+1)

idx = 0
for n in sortList:
  if dp[n] == False:
    continue
  for j in range(2, Amax//n+1):
    dp[n*j] = False
ansCount = 0
for n in sortList:
  if dp[n] == True:
    ansCount += 1
print(ansCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()
  
sortList = list(sorted(set(AList)))
Amax = max(sortList)
dp = [True] * Amax

idx = 0
for n in sortList:
  if dp[n-1] == False:
    continue
  j = 2
  while j*n <= Amax:
    dp[n*j -1] = False
    j += 1
ansCount = 0
for n in sortList:
  if dp[n-1] == True:
    ansCount += 1

print(ansCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()
  
sortList = list(sorted(set(AList)))
Amax = max(sortList)
dp = [True] * Amax

idx = 0
for n in sortList:
  if dp[n-1] == False:
    continue
  j = 2
  while j*n < Amax:
    dp[n*j -1] = False
    j += 1
ansCount = 0
for n in sortList:
  if dp[n-1] == True:
    ansCount += 1

print(ansCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()

Amax = max(AList)
dp = [True] * Amax

sortList = sorted(AList)
idx = 0
for n in sortList:
  if dp[n-1] == False:
    continue
  for j in range(2, Amax//n+1):
    dp[n*j -1] = False
ansCount = 0
for n in set(AList):
  if dp[n-1] == True:
    ansCount += 1

print(ansCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()

Amax = max(AList)
dp = [True] * Amax

sortList = sorted(AList)
idx = 0
for n in sortList:
  if dp[n-1] == False:
    continue
  for j in range(2, Amax//n+1):
    dp[n*j -1] = False
ansCount = 0
for n in AList:
  if dp[n-1] == True:
    ansCount += 1

print(ansCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

O = A.copy()

for i in A:
    for j in A:
        if i != j:
            if (i%j == 0):
                if i in O:
                    O.remove(i)
        if i == j:
            if i in O:
                O.remove(i)

ans = len(O)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
C = Counter(A)
cnt = 0
for c in C.values():
    if c >= 2:
        cnt -= 1

def eratos(s):
    primes = set([s])
    for i in range(1,N):
        flag = True
        for p in primes:
            if A[i]%p == 0:
                flag = False
        if flag:
            primes.add(A[i])
    return primes

ans = eratos(A[0])
print(len(ans) + cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
C = Counter(A)
cnt = 0
for c in C.values():
    if c >= 2:
        cnt -= 1

def eratos(s):
    primes = [s]
    for i in range(1,N):
        flag = True
        for p in primes:
            if A[i]%p == 0:
                flag = False
        if flag:
            primes.append(A[i])
    return primes
ans = eratos(A[0])
print(len(ans) + cnt)

Submission status: Wrong Answer

Solution code:
length=int(input())
list=list(map(int,input().split()))
max=max(list)
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        for i in range(max//num+1):
            dp[num*i]=False
        if list.count(num)==1:
            ret=ret+1
print(ret)

Submission status: Wrong Answer

Solution code:
length=int(input())
list=list(map(int,input().split()))
list.sort()
max=list[-1]
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        if list.count(num)!=1:
            dp[num]=False
        else:
            ret=ret+1
            i=2
            num2=num*i
            while num2<max+1:
                if num2 in list:
                    dp[num2]=False
                i=i+1
                num2=num*i
print(ret)

Submission status: Wrong Answer

Solution code:
length=int(input())
list=list(map(int,input().split()))
list.sort()
max=list[-1]
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        if list.count(num)!=1:
            dp[num]=False
        else:
            ret=ret+1
            i=2
            num2=num*i
            while num2<max+1:
                if num2 in list:
                    dp[num2]=False
                i=i+1
                num2=num*i
print(ret)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	refd = [0 for i in range(1000000 + 1)]
	for i,val in enumerate(A):
		for j in range(val,1000000 + 1,val):
			if refd[j] >= 2:
				break
			refd[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if refd[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a = list(map(int, input().split()))
ans = 0
check = 0

a.sort()

if len(a) == 1:
    print(1)
    sys.exit()

for i in range(n):
    if i == 0 :
        if a[i] % a[1] != 0:
                ans += 1
    if i>=1 and a[i] != a[i-1]:
        for j in range(i):
            if a[i] % a[j] == 0:
                check += 1
                break
        if check == 0:
            ans += 1
        check = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A_ = [int(i) for i in input().split(None,n)[:n]]
A = sorted(A_)

cand = set()
dup = set()

for a in A:
  if a in cand:
    dup.add(a)
  for c in cand:
    if a % c != 0:
      cand.add(a)
cand -= dup
print(len(cand))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
check = 0

a.sort()


for i in range(n):
    if i==0 or (i>=1 and a[i] != a[i-1]):
        for j in range(i+1):
            if a[i] % a[j] == 0:
                check += 1
            if check > 2:
                break
        if check == 1:
            ans += 1
        check = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

def func(n,a):
  counter=0
  check=False
  for i in range(n):
    if(check):
      counter+=1
    for j in range(n):
      if(i!=j):
        if(a[i]!=a[j] and a[i]%a[j]!=0):
          check=True
        else:
          check=False
          break
  print(counter)
  
  
func(n,a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

counter=0
check=False
for i in range(n):
  if(check):
    counter+=1
  for j in range(n):
    if(i!=j and a[i]!=a[j] and a[i]%a[j]!=0):
      check=True
    else:
      check=False
      break
          
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

counter=0
check=False
for i in range(n):
  if(check):
    counter+=1
  for j in range(i+1,n):
    if(a[i]!=a[j]):
      if(a[i]%a[j]!=0):
        check=True
      else:
        check=False
        break
    else:
      check=False
      break
          
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

counter=0
check=False
for i in range(n):
  if(check):
    counter+=1
  for j in range(n):
    if(i!=j):
      if(a[i]!=a[j]):
        if(a[i]%a[j]!=0):
          check=True
        else:
          check=False
          break
      else:
        check=False
        break
          
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

counter=0
check=False
for i in range(n):
  if(check):
    counter+=1
  for j in range(n):
    if(i!=j):
      if(a[i]!=a[j]):    
        if(a[i]%a[j]!=0):
          check=True
        else:
          check=False
          break
          
print(counter)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
t=[True]*(10**6)
a.sort()
s=set(a)
for i in a:
    if t[i-1] == False:
        continue
    for j in range(2*i,10**6,i):
        t[j-1] = False
ans = 0
for k in a:
    if t[k-1] == True:
        ans += 1
if len(s)!=len(a):
    ans = ans - (len(a)-len(s)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
def f(n, a):
    mx = max(a)
    x = [0] * (mx + 1) # len(x)
    for i in a:
        x[i] += 1
    if x[1] > 0:
        print(0)
        return
    for i in range(1, mx + 1):
        if x[i] > 1:
            x[i] = 0
        if x[i] != 0:
            upper = mx // i
            # print(f"i = {i}  mx = {mx}  x[i] = {x[i]}  upper = {upper}")
            for j in range(2, upper+1):
                # print(f"j = {j}  i = {i}  j * i = {j * i}")
                x[j * i] = 0
    print(sum(x)) # 31401

n = int(input())
a = list(map(int, input().split()))
f(n, a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
mx = max(a)
x = [0] * (mx + 1) # len(x)
for i in a:
    x[i] += 1
for i in range(1, mx + 1):
    if x[i] > 1:
        x[i] = 0
    if x[i] != 0:
        upper = mx // i
        # print(f"i = {i}  mx = {mx}  x[i] = {x[i]}  upper = {upper}")
        for j in range(2, upper+1, x[i]):
            # print(f"j = {j}  i = {i}  j * i = {j * i}")
            x[j * i] = 0
print(sum(x))

Submission status: Wrong Answer

Solution code:
n = int(input())
n = int(n)

num_list = list(map(int, input().split()))
num_list.sort()

length = int(len(num_list))

check_list = [True]*length

for i in range(0, length):
    if check_list[i] == True:
        for j in range(i+1, length):
            if num_list[j] % num_list[i] == 0:
                check_list[j] = False

            if num_list[i] % num_list[j] == 0:
                check_list[i] = False

print(check_list.count(True))
print(check_list)

Submission status: Wrong Answer

Solution code:
x = [0] * 2 * 10**5

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(map(int,input().split()),reverse=True)
t=[False]*1000001
for i in a:
    t[i]=True
    for j in range(i*2,1000001,i):
        t[j]=False
print(t.count(True))

Submission status: Wrong Answer

Solution code:
pt=[True]*1000001
for i in range(2,1000001):
    if pt[i]==True:
        for j in range(i*2,1000001,i):
            pt[j]=False

n=int(input())
a=sorted(map(int,input().split()))
t={}
for i in a:
    if i in t:
        t[i]=2
    else:
        t[i]=1
a=[i[0] for i in t.items() if i[1]==1]
n=len(a)

count=0
for i in range(n):
    b=a[i]
    c=True
    if not pt[b]:
        for j in range(n):
            if a[j]>b:
                break
            if b%a[j]==0 and i!=j:
                c=False
                break
    if c:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
res = []

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        elif (A[i] % A[j]) == 0:
            res.append(A[j])
            break
        
    else:
        if len(res) == 0:
            count += 1
        else:
            res.clear()

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
res = []

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        elif (A[i] % A[j]) == 0:
            res.append(A[j])
            break
        else:
            continue
        
    else:
        if len(res) == 0:
            count += 1
        else:
            res.clear()

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
d = {}
for x in arr:
  d[x] = d.get(x,0)+1

mxN = 10**6 + 1
rp = [True]*mxN


for i in range(2,len(rp)):
  if i not in d or not rp[i]:continue
  for j in range(i+i,mxN,i):
    if j in d: rp[j] = False

#reason for tle



for k,v in d.items():
  if v > 1:rp[k] = False

ans = sum([(1 if rp[x] else 0) for x in arr])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]

cset = set(arr)

mxN = 10**6 + 1
rp = [True]*mxN


for i in range(2,len(rp)):
  if i not in cset or not rp[i]:continue
  for j in range(i+i,mxN,i):
    if j in cset: rp[j] = False

for x in cset:
  arr.remove(x)

for x in arr:rp[x] = False

ans = sum([(1 if rp[x] else 0) for x in cset])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]

cset = set(arr)

mxN = 10**6 + 1
rp = [True]*mxN


oarr = set()
for x in arr:
  if x in oarr:
    oarr.remove(x)
    rp[x] = False
  else:
    oarr.add(x)


for i in range(2,len(rp)):
  if i not in cset or not rp[i]:continue
  for j in range(i+i,mxN,i):
    if j in arr: rp[j] = False

for x in cset:
  if x not in oarr:rp[x] = False

ans = sum([(1 if rp[x] else 0) for x in arr])
print(ans)