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: Runtime Error

Solution code:
inf =  210000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for i in range(N):
    detect[a[i]] += 1
    j = 2
    while (a[i]*j < inf):
      if detect[a[i]*j] >= 2:
        break
      else:
        detect[a[i]*j] += 2
        j+=1
  ans = 0
  for i in range(N):
    if detect[a[i]]<2:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
N=int(input())
data=list(map(int,input().split()))
count=0
data.sort()
for i in range(N):
    for j in range(i+2):
        if j != i:
            if data[i]%data[j] == 0:
                break
    else:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    a = [0] * 100005
    A_max = A[-1]

    for i in A:
        for j in range(1, A_max//i + 1):
            a[i * j] += 1

    ans = 0
    for i in A:
        if a[i] == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    a = [0] * 10005
    A_max = A[-1]

    for i in A:
        for j in range(1, A_max//i + 1):
            a[i * j] += 1

    ans = 0
    for i in A:
        if a[i] == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1
for i in A:
    if i != nt:
        dp[i] = True
    else:
        dp[i] = False
    nt = i

ans = 0
mx = A[N-1]
for i in A:
    if dp[i]:
        ans += 1
        j = i
        while j <= 1001001:
            dp[j] = False
            j += i
print(ans)

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Runtime Error

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

xs = [0] * (2 * (10 ** 5) + 1)

for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Submission status: Runtime Error

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

xs = [0] * (2 * (10 ** 5) + 1)
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Submission status: Runtime Error

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

xs = [0] * (2 * 10 ** 5 + 1)
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Submission status: Runtime Error

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

A.sort()
count = 0
A1 = []

for i in range(n):
  for j in range(i + 1):
    if A[j] in A1:
      continue
    if j != i and A[i] % A[j] == 0:
      count += 1
      A1.append(A[i])
      break

if A[0] % A[1] == 0:
  count += 1

ans = n - count
print(ans)

Submission status: Runtime Error

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

A.sort()
count = 0

for i in range(n):
  for j in range(i + 1):
    if j != i and A[i] % A[j] == 0:
      count += 1
      break

if A[0] % A[1] == 0:
  count += 1

ans = n - count
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input()))

A.sort()
count = 0

for i in range(n):
  for j in range(i + 1):
    if j != i:
      if A[i] % A[j] == 0:
        count += 1
        break

ans = n - count
print(ans)

Submission status: Runtime Error

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

A.reversed()
count = 0

for i in range(n):
  for j in range(i+1):
    if j != i:
      if A[j] % A[i] == 0:
        count += 1
        break

ans = n - count
print(ans)

Submission status: Runtime Error

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

m=max(A)

X=[True]*(m+1)

A.sort()

for i in range(n):
    for j in range(A[i]*2,m+1,A[i]):
        X[j]=False

if A[0]==A[1]:
    ans=0
else:
    ans=1

for i in range(1,n):
    if A[i-1]==A[i]:
        continue
    if X[A[i]]==True:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

a = [int(x) for x in input().split()]

a.sort()
if a[0]==a[1]:
	ans=0
else:
	ans=1

for i in range(0,len(a)):
	for j in range(len(a)):
		if a[i]%a[j]==0:
			break
		if j==i-1:
			ans+=1
			break

print(ans)

Submission status: Runtime Error

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

li = [1]*(max(A)+1)
for j in range(N):
    for i in range(A[j]*2,A[-1]+1,A[j]):
        li[i] = 0
    if j == 0:
        if A[j] == A[j+1]:
            li[A[j]]= 0
    elif j == N-1:
        if A[j] == A[j-1]:
             li[A[j]]= 0
    else:
        if A[j] == A[j+1] or A[j] == A[j-1]:
             li[A[j]]= 0
sA = sum([li[i] for i in A])
print(sA)

Submission status: Runtime Error

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

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

if a[-1] != a[-2]:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
ln = set()
for i in range(N):
    tmp = A[i]
    if i == 0 and A[i] == A[i+1]:
        cnt = 0
        ln = ln | set(range(A[i],A[-1]+1,A[i]))
    elif i == 0 and A[i] != A[i+1]:
        cnt +=1
        ln = ln | set(range(A[i],A[-1]+1,A[i]))
    else:
        if A[i] not in ln:
            cnt +=1
    ln = ln | set(range(A[i],A[-1]+1,A[i]))
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
for i in range(N):
    tmp = A[i]
    if i == 0:
        if A[0]==A[1]:
            continue
    elif i == N-1:
        if A[-1]==A[-2]:
            continue
    else:
        if A[i-1]== A[i] or A[i] == A[i+1]:
            continue
    flag = 0
    for j in range(i):
        if A[j]*2 > A[i]:
            break
        else:
            #print(A[j],A[i])
            if A[i]%A[j]== 0:
                flag = 1
                break
            else:
                continue
    #print(A[i],flag)
    if flag == 0:
        #print(A[i])
        cnt +=1
print(cnt)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_4
# CreatedDate:  2020-07-20 00:18:24 +0900
# LastModified: 2020-07-20 00:26:33 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = sorted(map(int, input().split()))
    ans = [1]*n
    for i, a in enumerate(A):
        if ans[i] == 0:
            continue
        for j in range(i+1, n):
            if A[j]%a == 0:
                ans[j] = 0
    if A[0] == A[1]:
        ans[0] = 0
    print(sum(ans))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

nall = list(range(n))


cnt = n
for i in nall:
	if a.count(a[i]) > 1:
		break
	for j in nall:
		if i <= j:
			break
		if a[i] % a[j] == 0:
			cnt -= 1
			break

print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
b=list(map(int,input().split()))
ans=0
w=max(b)
a=[0]*w
for i in b:
  x=i
  while x<w:
    a[x]=1
    x+=i
for i in b:
  if a[i]==0:
    ans+=1

Submission status: Runtime Error

Solution code:
from collections import Counter

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

C=Counter(A)

A=set(A)

MAX_A=10**6

X=[0]*(MAX_A+1)

for a in A:
    for i in range(a,MAX_A+1,a):
        X[i]+=1

ans=len([a for a in A if (X[1]==1) and (C[a]==1)])

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

n = int(input())
aa = np.array(list(map(int,input().split())))

a=[i for i in aa if np.count_nonzero(aa==i)<2]
a=np.unique(a)
ah=[1]*len(a)

if len(ah) ==0:
    print(0)
    sys.exit()
for i in range(n-1):
    if ah[i]==1:
        for j in range(i+1,n):
            wk0=a[j]%a[i]
            if wk0==0:
                ah[j]=0

print(sum(ah))

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
num=[True for i in range(a[-1]+1)]
for i in range(n):
  if num[i]:
    for j in range(a[-1]//a[i]):
      if j<2:
        continue
      num[a[i]*j]=False
    if i!=n-1 and a[i]==a[i+1]:
      num[a[i]]=False
  else:
    pass
ans=0
for i in range(n):
  if num[a[i]]:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a.sort()
p=0
a=np.array(a)
ans=0
while True:
  i=0
  if len(a)>1:
    while a[i]==a[i+1]:
      i+=1
      if i==n-1:
        break
    first=a[i]
    ans+=1
    a=a[i:]
  elif len(a)==1:
    ans+=1
    break
  else:
    break
  b=a.copy()
  if len(b)==0:
    break
  b%=first
  a=a[b!=0]
print(ans)

Submission status: Runtime Error

Solution code:
input()
li = list(map(int,input().split()))	
li.sort()
hyo = [1] * 10 ** 6
for i in li:
  if hyo[i] == 0:
    continue
  for j in range(i * 2, 10 ** 6, i):
    hyo[j] = 0
count = 0
for i in li:
  if hyo[i] == 1 and li.count(i) == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
input()
li = list(map(int,input().split()))	
li.sort()
hyo = [1] * 10 ** 6
for i in li:
  if hyo[j] == 0:
    continue
  for j in range(i * 2, 10 ** 6, i):
    hyo[j] = 0
count = 0
for i in li:
  if hyo[i] == 1 and li.count(i) == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
input()
li = list(map(int,input().split()))	
li.sort()
hyo = [1] * 10 ** 6
for i in li:
  for j in range(i * 2, 10 ** 6, i):
    hyo[j] = 0
count = 0
for i in li:
  if hyo[i] == 1 and li.count(i) == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
count = Counter(A)

data = [True]*N
A = list(set(A))

for i in range(N):
    if data[i]:
        for j in range(i+1,N):
            # print(i,j)
            if A[j]%A[i]==0:
                data[j]=False

ans = len([i for i in range(N) if data[i] and count[A[i]]==1])
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n=int(input())
alist=list(map(int,input().split()))
a_sort=sorted(alist)
p=10**6+1
anslist=[0 for i in range(1,p)]
cnt=0
for i in a_sort:
  for j in range(1,int(p/i)):
    if anslist[i*j]<2:
      anslist[i*j]+=1
    else:
      break
kosuu=0
for i in a_sort:
  if anslist[i]==1:
    kosuu+=1
print(kosuu)

Submission status: Runtime Error

Solution code:
#import time

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

    As.sort()
    amax = max(As) + 1
    lis = [True] * amax
    ans = 0

    for i in range(N-1):
        if lis[As[i]]:
            for j in range(As[i], amax, As[i]):
                lis[j] = False
            if a[i] < a[i+1]:
                ans += 1
    if lis[-1]:
        ans += 1

    return ans

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Runtime Error

Solution code:
n = int(input())
aas = list(set(sorted(list(map(int, input().split())))))
if len(aas) == 1:
    print(0)
    exit()
#aas_max = aas[-1]
i = 0
while i != len(aas):
    j = i + 1
    while j != len(aas):
        if aas[j]%aas[i] == 0:
            del aas[j]
        else:
            j += 1
    i += 1
print(len(aas))

Submission status: Runtime Error

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    a = sorted(a)
    ans = [a[0]]
    for _a in a[1:]:
        for b in ans:
            if _a % b == 0:
                break
        else:
            ans.append(_a)
    return str(len(ans) - (a[0] == a[1]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in range(1, n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
      db[a[i]-1] = 1
  if n == 1 or a[0] != a[1]:
    db[a[0]] = 1
  if n > 1 and a[-1] != a[-2]:
    db[-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in range(1, n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
      db[a[i]-1] = 1
  if a[0] != a[1]:
    db[a[0]] = 1
  if n > 1 and a[-1] != a[-2]:
    db[-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros(2*(10**5)+1, dtype=int)

for a in aa:
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
factor = []
set_factor = set()
counter = 0

if a[0] != a[1]:
    counter += 1

set_factor.add(a[0])
factor.append(a[0])

for i in range(1, n - 1):
    back = a[i - 1]
    forward = a[i + 1]
    if a[i] not in set_factor:
        for j in factor:
            if a[i] % j == 0:
                break
        else:
            if a[i] != forward and a[i] != back:
                counter += 1
            set_factor.add(a[i])
            factor.append(a[i])
        
if a[n - 1] != a[n - 2] :
    for i in factor:
        if a[n - 1] % i == 0:
            break
    else:
        counter += 1

print(counter)

Submission status: Runtime Error

Solution code:


def q4():
    _ = input()
    A = [int(i) for i in input().split(" ")]

    primes = get_prime_numbers(1000)

    values = set()
    duplicates = set()
    values_dict = {}
    for i in range(len(A)):
        a = A[i]
        if a in values:
            duplicates.add(values_dict[a])
            duplicates.add(i)
        values_dict[a] = i
        values.add(a)

    ans_count = 0
    for i in range(len(A)):
        a = A[i]
        if a in duplicates:
            continue
        if a in primes:
            ans_count += 1
            continue
        ok = True
        for p in primes:
            if p in values and a % p == 0:
                ok = False
                break
            if a / p in values:
                ok = False
                break
        if ok:
            ans_count += 1

    print(ans_count)


q4()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import collections
import math
import copy

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

max_num = max(A)
data = get_sieve_of_eratosthenes(max_num)
select_prime = list(set(data) & set(A))
remove_prime = sorted(list(set(A).difference(set(data))))

if len(remove_prime)==0:
    print(0)
else:
    for min_num in remove_prime:
        divisor = make_divisors(min_num) 
        remove_max = sorted(divisor)[:-1] 
        if (list(set(remove_prime)&set(remove_max))==[])&(list(set(select_prime)&set(remove_max))==[]):
            select_prime.append(min_num)
    print(len(select_prime))

Submission status: Runtime Error

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
lista.sort()
listtf=[]
s=0
for i in range(lista[n-1]):
    listtf+=[True]
for i in range(n):
    if(listtf[i]):
        if(i<n-1 and lista[i]==lista[i+1]):
            s-=1
        s+=1
        t=1
        while(t*lista[i]<lista[n-1]):
            listtf[lista[i]*t]=False
            t+=1
print(s)

Submission status: Runtime Error

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=set()
for i in range(n-1):
    if(lista[i]==lista[i+1]):
        listde.add(lista[i])
t=0
for i in range(n):
    t=0
    for k in listde:
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        listde.ad(lista[i])
print(s)

Submission status: Runtime Error

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
for i in range(n-1):
    for k in range(i+1):
        if(lista[i+1]%lista[k]==0):
            break
        else:
            if(k==i):
                s+=1
if(lista[0]!=lista[1]):
    s+=1
print(s)
                
        
        
        
    
5

Submission status: Runtime Error

Solution code:
from collections import Counter
inp = list(map(int,input().split()))
c=Counter(inp)
inp=[]
for item in c.keys():
  if c[item]==1:
    inp.append(item)
arr=[1]*len(inp)
inp.sort()
ans=0
for i in range(len(inp)):
  if arr[i]==0:
    continue
  else:
    ans+=1
   	for j in range(i+1,len(inp)):
      if inp[j]%inp[i]==0:
        arr[j]=0
print (ans)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[i] and i!=n-1 and a != A[i+1]:
            g.append(a)
            for j in range(A_max//a):
                table[a*j] = False
    print(len(g))
main()

Submission status: Runtime Error

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i == 0:
            if A[i] != A[i + 1]:
                Sum += 1
        elif i < N - 1:
            if A[i] != A[i + 1] and A[i] != A[i - 1]:
                Sum += 1
        
print(Sum)

Submission status: Runtime Error

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i == 0:
            if A[i] != A[i + 1]:
                Sum += 1
        elif i < N - 1:
            if A[i] != A[i + 1] and A[i] != A[i - 1]:
                Sum += 1
        else:
            if A[i] != A[i - 1]:
                Sum += 1
print(Sum)

Submission status: Runtime Error

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i == 0:
            if A[i] != A[i + 1]:
                Sum += 1



print(Sum)

Submission status: Runtime Error

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i == 0:
            if A[i] != A[i + 1]:
                Sum += 1
        elif i == N - 1:
            if A[i] != A[i - 1]:
                Sum += 1


print(Sum)

Submission status: Runtime Error

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i == 0:
            if A[i] != A[i + 1]:
                Sum += 1
        elif i == N - 1:
            if A[i] != A[i - 1]:
                Sum += 1
        else:
            if A[i] != A[i + 1] and A[i] != A[i - 1]:
                Sum += 1

print(Sum)

Submission status: Runtime Error

Solution code:
from numba import njit


@njit(cache=True)
def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(" "))))
m = max(A)
ans = 0
dp = [True]*m
for i in range(N-1):
  x = A[i]-1
  if dp[x] == True:
    for j in range(1,m//x+1):
      dp[j*x-1] = False
    if A[i] != A[i+1]:
      ans +=1
if dp[-1]:
  ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
if n != 1:
  arr = np.asarray([[int(x) for x in input().split()]])
  arrT = arr.T
  eye = np.eye(n)
  ans = np.count_nonzero(arrT % arr + eye == 0, axis=1)
  ans = np.count_nonzero(ans == 0)
  print(ans)
else:
  print(input())

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
arr = np.asarray([[int(x) for x in input().split()]])
arrT = arr.T
eye = np.eye(n)
ans = np.count_nonzero(arrT % arr + eye == 0, axis=1)
ans = np.count_nonzero(ans == 0)
print(ans)

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False

def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2])
    right_array = merge_sort(array[len(array) // 2:])
    sorted_array = []
    while left_array and right_array:
        #print(left_array, right_array)
        if left_array[0] < right_array[0]:
            sorted_array.append(left_array.pop(0))
        else:
            sorted_array.append(right_array.pop(0))
    sorted_array.extend(right_array)
    sorted_array.extend(left_array)
    return sorted_array


def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    a = merge_sort(a)
    #print(a)
    a_max = a[n-1]
    is_prime = [True] * (2 * 10**5 +1)
    is_prime[0] = False
    #is_prime[1] = False
    count = [0] * (2 * 10**5 +1)
    
    a_pre = 0
    for i in range(n):
        if a[i]==a_pre:
            count[a[i]-1] = 0
            a_pre = a[i]
            continue
        if is_prime[a[i]-1]:
            count[a[i]-1] = 1
            for j in range(a[i]*2, a_max+1, a[i]):
                is_prime[j-1] = False
        a_pre = a[i]
    
    print(sum(count))
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

c = Counter(a)
a = list(set(a))
dp = [0] * (10+1)

for x in a:
  t = x * 2
  while t <= 10:
    dp[t] = 1
    t += x

ans = 0
for x in a:
  if (c[x] == 1) & (dp[x] == 0):
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

dp = [1 for _ in range(n)]

def div(k):
  global dp
  for i in range(k):
    if a[k]%a[i] == 0:
      dp[k] = 0
      if a[k] == a[i]:dp[i] = 0
      break
  if k < n-1:div(k+1)

div(1)
print(sum(dp))

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

dp = [1 for _ in range(n)]

def div(k):
  global dp
  if dp[k] != 0:
    for i in range(k):
      if a[k]%a[i] == 0:
        dp[k] = 0
        if a[k] == a[i]:dp[i] = 0
        break
  if k < n-1:div(k+1)

div(1)
print(sum(dp))

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(n)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

dp = [1] * n +[0]

def div(k):
  global dp
  if dp[k] != 0:
    for i in range(k):
      if a[k]%a[i] == 0:
        dp[k] = 0
        if a[k] == a[i]:dp[i] = 0
        break
  if k < n-1:div(k+1)

div(1)
print(sum(dp))

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(n)
  exit()

a.sort()
dp = [1] * n

def div(k):
  global dp
  if k < n-1:div(k+1)

div(1)
print(sum(dp))

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(n)
  exit()

a.sort()
dp = [1] * n

def div(k):
  global dp
  if dp[k] != 0:
    for i in range(k):
      if a[k]%a[i] == 0:
        dp[k] = 0
        if a[k] == a[i]:dp[i] = 0
        break
  if k < n-1:div(k+1)

div(1)
print(sum(dp))

Submission status: Runtime Error

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

a.sort()
dp = [1] * n

def div(k):
  global dp
  if dp[k] != 0:
    for i in range(k):
      if a[k]%a[i] == 0:
        dp[k] = 0
        if a[k] == a[i]:dp[i] = 0
        break
    if k < n-1:div(k+1)

div(1)

Submission status: Runtime Error

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

a.sort()
dp = [1] * len(a)

def div(k):
  global dp
  if dp[k] != 0:
    for i in range(k):
      if a[k]%a[i] == 0:
        dp[k] = 0
        break
    if k < n-1:div(k+1)

div(1)
print(sum(dp))

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int, input().split(' '))))
A_max = A[-1]
dp = [True]*(A_max+1)
ans = 0
for i in range(N-1):
    p = A[i]
    if dp[i] == True:
        for q in range(A_max//p+1):
            dp[p*q] = False
        if A[i] != A[i+1]:
            ans += 1
if dp[-1] != True:
    ans += 1 
print(ans)

Submission status: Runtime Error

Solution code:
for i in range(1e6):
  i**2

Submission status: Runtime Error

Solution code:
# ABC170

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

a.sort()
a_max = max(a)
dp = [True for _ in range(a_max+1)]

ans = 0
for i in range(n):
    if dp[a[i]]:
        for j in range(0, a_max+1, a[i]):
            dp[j] = False
        if (a[i] != a[i-1]) and (a[i] != a[i+1]):
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

dp = ['True'] * 1000000
seen = set()

A.sort()

for i in range(len(A)):
	if i in seen:
		continue
	else:
		seen.add(i)
	x = A[i]
	if dp[x]:
		for y in range(x + x, len(dp), x):
			dp[y] = False

c = defaultdict(int)
for elem in A:
	c[elem] += 1

A = [x for x in A if c[x] == 1]

ans = 0
for elem in A:
	if dp[elem]:
		ans += 1
print(ans)

Submission status: Runtime Error

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

A=[]
array=sorted(array)
for i in array:
    A.append(i)

dp=[True for i in range(N)]

if A[0]==A[1]:
    dp[0]=False
for i in range(N):
    if dp[i] == False:
        continue
    for j in range(i+1,N):
        if A[j]%A[i]==0:
            dp[j]=False

num=0
for i in range(N):
    if dp[i] == True:
        num+=1

print(num)

Submission status: Runtime Error

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

A=[]
array=sorted(array)
for i in array:
    A.append(i)

dp=[True for i in range(N)]

if A[0]==A[1]:
    dp[0]=False
for i in range(N):
    for j in range(i+1,N):
        if A[j]%A[i]==0:
            dp[j]=False

num=0
for i in range(N):
    if dp[i] is True:
        num+=1

print(num)