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:
import numpy as np

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

a = list(set(a))

count = 0
for i in range(n):
    ans = a[i] % np.array(a)
    if np.count_nonzero(ans == 0) == 1:
        count += 1

print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter

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

cnt = Counter(A) 

A = list(set(A))
A.sort()


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

for a in A:
    if cnt[a] == 1 and C[a] == 0:
        ans += 1

    i = 1
    while True:
        if a*i > 10**6+1:
            break
        C[a*i] = 1
        i += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [True for i in range(a[-1])]
ans = n
for k in range(n):
    if p[a[k]-1]:
        if a[k] != a[k+1] or k == n-1:
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break
        else:
            ans -= 1
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break  
    else:
        ans -= 1        
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
a=collections.Counter(a)
b,c=[],[]
for t in a:
  if a[t]==1:
    b.append(t)
  else:
    c.append(t)
if len(b) == 0:
  print(0)
  exit()
b.sort()
bm = b[-1]
ok = [True]*(bm+1)

for t in c:
  if ok[t] == False: continue
  i = 1
  while i*t<=bm:
    ok[i*t]=False
    i+=1
for t in b:
  if ok[t] == False: continue
  i = 2
  while i*t<=bm:
    ok[i*t]=False
    i+=1
ans = 0
for t in b:
  if ok[t]:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [True for i in range(a[-1])]
ans = n
for k in range(n):
    if p[a[k]-1]:
        if a[k] != a[k+1]:
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break
        else:
            ans -= 1
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break  
    else:
        ans -= 1        

    

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

cou = Counter(A) 

A = list(set(A))
A.sort()


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

for a in A:
    if C[a] == 0 and C[a] == 0:
        ans += 1

    i = 1
    while True:
        if a*i > 10**6+1:
            break
        C[a*i] = 1
        i += 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

cou = Counter(A) 

A = list(set(A))
A.sort()

C = [0]*(10**6+1)
for a in A:
    if C[a] == 0 and C[a] == 0:
        ans += 1

    i = 1
    while True:
        if a*i > 10**6+1:
            break
        C[a*i] = 1
        i += 1

print(ans)

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
A = list(set(A))
# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(n):
    #ll += 1
    #print(i)
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
for i in A:
    dic[i] += 1
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
A = set(A)
# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(n):
    #ll += 1
    #print(i)
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
for i in A:
    dic[i] += 1
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

count = 0
k = 0
p = A2[k]
while(p <= math.sqrt(A2[len(A2)-1])):
  free=[]
  for i in range(k+1,len(A2)):
    if(A2[i]%p == 0):
      free.append(A2[i])
  for i in range(len(free)):
    A2.remove(free[i])
  k += 1
  p = A2[k]

count = 0
for i in range(len(A2)):
  if(A.count(A2[i])==1):
    count += 1

print(count)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
size=N
M=max(A)**0.5//1
i=0
while A[i]<M:
  j=i+1
  if not (i!=0 and A[i]!=A[i-1]):
    while size>j:
      if A[j]%A[i]==0:
        A.remove(A[j])
        size-=1      
      else:j+=1
  i+=1
print(size)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = [False]*n
if a[0]==a[1]:
    l[0]=True

a.sort()
#print(a)
for i in range(n-1):
    for j in range(i+1,n):
        if l[j]:
            continue
        if a[j]%a[i]==0:
            l[j]=True
    #print(l)
print(l.count(False))

Submission status: Runtime Error

Solution code:
# MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis.sort()
MAX = lis[-1]
lis2 = [0]*MAX
# lis.sort()
# m = max(lis)
ans = 0

for num in lis:
    for i in range(num, MAX, num):
            lis2[i] += 1

for j in set(lis):
    if lis2[j] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

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

p_all = set(range(0, 102)) - set(p)
# print(p_all)

mi = float('inf')
ans = 0
for i in p_all:
    if abs(x - i) < mi:
        mi = abs(x - i)
        ans = i

print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 1)
    c = Counter(A)

    for a in c.keys():
        tmp = a * 2
        if p[tmp] == 1:
            continue
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;

bool f(int index, int n, int a_s[n]);
int n;

int main()
{
	cin >> n;
	int a_s[n];

	for (int i = 0; i<n; i++){
		cin>> a_s[i];
	}
	
	int count=0;
	for (int i= 0; i<n; i++) {
		if (f(i,n, a_s)) {
			count++;
		}
	
	}
	cout << count;
}

bool f(int index, int n, int a_s[n]) {
	int A= a_s[index];
	for (int index2=0; index2<n; index2++) {
		if (index2 != index) {
			if (A % a_s[index2] == 0) {
				return false;
			}
		}
	}
	return true;
}

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
an = np.array([int(a) for a in input().split()], dtype=np.int64)
validate = np.ones(n, dtype="bool")
res = 0
for i in range(n):
    validate[:] = True
    validate[i] = False
    an_slice = an[validate]
    diveded = an[i] % an_slice
    if diveded[diveded != 0].size == an_slice.size:
        res+=1
# print(timeit.timeit("loop(n, an, validate, res)", globals=globals()))

print(res)

Submission status: Runtime Error

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

As = sorted(A)

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0
while(i < len(As)):
    if As[i] > 1000:
        break
#     print('i:{}'.format(i))
#     print('As:{}'.format(As))
    # As[i]で、A[i+1]～A[len(As)]で割り切れるものを探し、消す。
    j = i+1
    poplist = []
    while(j < len(As)):
#         print('j:{}'.format(j))
#         print('As[i]:{}'.format(As[i]))
#         print('As[j]:{}'.format(As[j]))
        if As[j]%As[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
            # A[i]とA[j]が同じ数字なら、最後にA[i]も消す必要があるので、
            # A[i]を削除リストに入れる
            if As[i]  == As[j]:
                dellist.append(A[i])
                
        j += 1
        
    # poplistにあるAs[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        As.pop(k)
    # As[i]で割り切れるものは探しきって、次のAs[i+1]は割り切れないもの。
    # 次はAs[i+1]について考える
    i += 1

# remove は、指定した要素がlistに含まれていないとエラーを吐くみたいなので、
# 重複を排除する
dellist = list(set(dellist))
    
for i in dellist:
    As.remove(i)

# print(As)
print(len(As))
# print(dellist)

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
if len(set(A)) == 1:
    print(0)
    exit()

from collections import Counter
c = Counter(A)

NMAX = 2 * 10 ** 5 + 10
dp = [True] * (NMAX + 1)
for k, v in c.items():
    for i in range(k * 2, NMAX + 1, k):
        dp[i] = False

count = 0
for k, v in c.items():
    if v > 1: continue
    if dp[k]: count += 1

print(count)

Submission status: Runtime Error

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    max=a[-1]
    check=[0 for i in range(max+10)]
    sum=0
    if len(a)==1:
        print(1)
        exit()
    tmp=a[1]
    for i in range(n):
        if tmp==a[i]:
            continue
        tmp=a[i]
        if check[a[i]]==0:
            sum+=1
            j=1
            x=a[i]*j
            while x<max+1:
                x=a[i]*j
                check[x]=1
                j+=1
        else:
            continue
    print(sum)
        
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

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

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in x:
        if x.count(i) > 1:
            continue
        if is_prime[i] == True:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Runtime Error

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう

kouho = [x for x in set(A) if A.count(x) == 1]
#target = kouho[:]
maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN):
        buf = A[i]*n
        if buf in kouho:
            kouho.remove(buf)
            #print(A[i]*n)
#target = kouho[:]

print(len(kouho))

Submission status: Runtime Error

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    max=a[-1]
    check=[0 for i in range(max+10)]
    sum=0
    tmp=a[1]
    for i in range(n):
        if tmp==a[i]:
            continue
        tmp=a[i]
        if check[a[i]]==0:
            sum+=1
            j=1
            x=a[i]*j
            while x<max+1:
                x=a[i]*j
                check[x]=1
                j+=1
        else:
            continue
    print(sum)
        
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Submission status: Runtime Error

Solution code:
import copy 

N=int(input())
A=list(map(int,(input().split())))
new_A=list(set(A))
new_A.sort()
tmp_A = copy.copy(new_A)
count=0
try:
  for i in new_A[:]:
    tmp_A.remove(i)
    for j in tmp_A[:]:
      print(i)
      print(new_A)
      if(i%j==0):
        new_A.remove(i)
    tmp_A=copy.copy(new_A)

  if(len(new_A)==1):
    print(0)
  else:
    print(len(new_A))
except:
  print(len(new_A))

Submission status: Runtime Error

Solution code:
import sys
import copy
from collections import deque
stdin = sys.stdin
 
mod = 10**9+7
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
 
n = ni()
a = na()
a.sort()
a_max = max(a)

c = [0 for _ in range(1000000)]
for aa in a:
    c[aa] += 1

dp = [False for _ in range(1000000)]
cnt = 0
for ai in set(a):
    if dp[ai]:
        continue
    if c[ai]==1:
        cnt += 1
    for j in range(ai+ai, a_max+1, ai):
        dp[j] = True

print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(_) for _ in input().split()]
lim=10**6+7
a.sort()
dp=[True for i in range(lim)]
ans=0
for i in range(n):
    if dp[a[i]]:
        if i==n-1 or a[i]!=a[i+1]:
            ans+=1
        for j in range(lim//a[i]+1):
            dp[j*a[i]]=False

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    x = Counter(a)

    y = [k for k, v in x.items() if v == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

    if x.get(1) > 1:
        print(0)
        exit()
    if x.get(1) == 1:
        print(1)
        exit()

    l = z[-1]
    m = [0] * (l + 1)
    for i in z:
        if m[i] == 0:
            m[i] = 1
        j = l // i
        for k in range(2, j + 1):
            m[i * k] = -1

    ans = m.count(1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=N
rem=[]
for i in range(N-1):
  if A[i]==A[i+1]:
    ans-=1
    rem+=A[i]
  if i!=0 and A[i]==A[i-1] and A[i]!=A[i+1]:
    ans-=1
if A[N-1]==A[N-2]:
  ans-=1
mult=[]
for i in range(N):
  B=list(range(A[i]*2,10**6+1,A[i]))
  mult+=B
mult=set(mult)
rem=set(rem)
for i in range(N):
  if A[i] in mult and A[i] not in rem:
    ans-=1
print(ans)

Submission status: Runtime Error

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

def main(n,a):
    maxa=2*10**5
    isprime=[True]*(maxa+1)
    sa=sorted(a)

    prevx=0
    for x in sa:
        if isprime[x]==False:
            continue
        if prevx==x:
            isprime[x]=False
            continue

        i=x*2
        while(i<=maxa):
            isprime[i]=False
            i+=x
        prevx=x
    
    count=0
    for x in sa:
        if isprime[x]==True:
            count+=1
    return count

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
A = collections.Counter(A)
B = []
C = []
for i in A:
    if A[i] == 1:
        B.append(i)
    else:
        C.append(i)
B = sorted(B)
if len(B) == 0:
    print(0)
    exit()
mb = B[-1]
ok = [True] * (mb+1)

if len(C) > 0:
    C = sorted(C)
    for c in C:
        if not ok[c]:
            continue
        k = 2
        while k*c <= mb:
            ok[k*c] = False
            k += 1

for b in B:
    if not ok[b]:
        continue
    k = 2
    while k*b <= mb:
        ok[k*b] = False
        k += 1

ans = 0
for b in B:
    if ok[b]:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()])
b=[0 for i in range(max(a)+1)]

ans=0
for i in a:
    if b[i]==0:
        if b[i]!=c:
            ans+=1
        c=i
        while i<max(a)+1:
            b[i]=c
            i+=c
        
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
if A[0] == 1:
    print(0)
else:
    ans = 0
    d = [0]*(10**6+1)
    for i in range(N):
        if d[A[i]] == 0:
            if c[A[i]] == 1:
                ans += 1
            j = A[i]
            while j <= (10**6):
                d[j] += 1
                j += A[i]
print(ans)

Submission status: Runtime Error

Solution code:
MAX = int(2e5)+2


n = int(input())
lis = list(map(int,input().split()))
lis2 = [0]*MAX
# lis.sort()
# m = max(lis)
ans = 0
for num in lis:
    lis2[num] += 1

for num in lis:
    for i in range(num*2, MAX, num):
        if lis2[i] > 0:
            lis2[i] += 1

print(len([i for i in lis if lis2[i] == 1]))

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
A = collections.Counter(A)
B = []
C = []
for i in A:
    if A[i] == 1:
        B.append(i)
    else:
        C.append(i)
B = sorted(B)
if len(B) == 0:
    print(0)
    exit()
mb = B[-1]
ok = [True] * (mb+1)

C = sorted(C)
for c in C:
    if not ok[c]:
        continue
    k = 2
    while k*c <= mb:
        ok[k*c] = False
        k += 1

for b in B:
    if not ok[b]:
        continue
    k = 2
    while k*b <= mb:
        ok[k*b] = False
        k += 1

ans = 0
for b in B:
    if ok[b]:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
MAX = int(2e5)+1


n = int(input())
lis = list(map(int,input().split()))
lis2 = [0]*MAX
# lis.sort()
# m = max(lis)
ans = 0
for num in lis:
    lis2[num] += 1

for num in lis:
    for i in range(num*2, MAX, num):
        if lis2[i] > 0:
            lis2[i] += 1

print(len([i for i in lis if lis2[i] == 1]))

Submission status: Runtime Error

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = 0
a = [True] * array[N-1]
i = 0
before = 0
for i in array:
    j = 2*i
    if i == before:
        array[i] == False
    while j < array[N-1]:
        array[j] == False
        j += i
    before = i
for i in array:
    if array[i] == True:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 2*100000 + 9
dp = [True] * MAX
for num in a:
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import collections

n = int(input())

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

a.sort()

for i in range(len(a)):
    if dp[i] == True:
        for j, x in enumerate(a[i+1:], 1):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False

num_dict = dict(collections.Counter(a))

result = [x for x, y in zip(a, dp) if (y == True) and (num_dict[x] == 1)]

print(len(result))

Submission status: Runtime Error

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = 0
a = [True] * array{N}
i = 0
before = 0
for i in array:
    j = 2*i
    if i == before:
        array[i] == False
    while j < array[N]:
        array[j] == False
        j += i
    before = i
for i in array:
    if array[i] == True:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 2*100000 + 9
dp = [True] * MAX
for num in a.keys():
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 10)
    c = Counter(A)

    for a in A:
        tmp = a * 2
        if p[tmp] == 1:
            continue
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

MAXN = max(A)
B = [False]*(MAXN+1)
for c in C:
    B[c[0]] = True
ans = 0
for i in range(MAXN + 1):
    if B[i]:
        if C[i]==1:
            ans += 1
        B[i::i] = [False]*(MAXN//i)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True1
for i in a:
    if a.count(i)>1:
        dp[i]=True
cnt=0
for i in a:
    if dp[i]:
        cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    n, *A = map(int, f.read().split())
    A.sort()
    n = A[-1]
    isPrime = [True] * (n + 1)
    prep = 0
    for i in A:
        if prep == i:
            isPrime[prep] = False
            continue
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
        prep = i

    prep = res = 0
    for i in A:
        if prep == i:
            continue
        if isPrime[i]:
            res += 1
        prep = i
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
onaji = 0

#数列Aを昇順に並べ替えた後、AjがAiの倍数になっていた時Ajをリストから削除する方針です。
for i in range(len(A)):
    if i >= len(A)-1:   #数列が小さくなって行くので当初のループ量は必要ないので。
        break
    for j in range(len(A)-1,i,-1):　#大きい数字から順番にみていく。
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1:　#同じ数字があった時Aiも削除。
        del A[i]
        onaji = 0

print(len(A))

Submission status: Runtime Error

Solution code:
import copy 

N=int(input())
A=list(map(int,(input().split())))
new_A=list(set(A))
new_A.sort()
tmp_A = copy.copy(new_A)
count=0

for i in new_A[:]:
  tmp_A.remove(i)
  for j in tmp_A[:]:
    if(i%j==0):
      new_A.remove(i)
  tmp_A=copy.copy(new_A)
print(len(new_A))

Submission status: Runtime Error

Solution code:
import bisect

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

if A[0] != A[1]:
  ans += 1

for i in range(N - 1,-1,-1):
  sup = A[i] // 2 + 1
  ind = bisect.bisect(A,sup)
  ind = max(ind,1)
  for j in range(0,ind):
    if A[i] % A[j] == 0:
      ans -= 1
      break

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
prime = []
limit = int(max(A)/2 +2)
if A[0] == 1:
    print(1)
else:
    while True:
        p = A[0]
        if limit <= p:
            break
        if len(A) >1:
            if A[0] != A[1]:
                prime.append(p)
        A = [e for e in A if e % p != 0]
        print(A)


    print(len(prime))

Submission status: Runtime Error

Solution code:
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 1)
    c = Counter(A)

    for a in A:
        tmp = a * 2
        if p[tmp] == 1:
            continue
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
MAX = int(2e5)+1


n = int(input())
lis = list(map(int,input().split()))
lis2 = [0]*MAX
# lis.sort()
# m = max(lis)
ans = 0
for num in lis:
    lis2[num] += 1

for num in lis:
    for i in range(num*2, MAX+1, num):
        if lis2[i] > 0:
            lis2[i] += 1

print(len([i for i in lis if lis2[i] == 1]))

Submission status: Runtime Error

Solution code:

    n = int(input())
    A = list(map(int, input().split()))
    max_a = max(A)
    m = set()
    checked = set()
    duplicated = set()

    for a in A:
        if a in checked:
            duplicated.add(a)
            continue

        i = 2
        while a*i <= max_a:
            m.add(a*i)
            i += 1

        checked.add(a)

    ans = 0
    for a in A:
        if a in duplicated: continue

        if a not in m:
            ans += 1
    
    print(ans)
 
resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
 
A_list = [int(n) for n in input().split()]
 
import numpy as np
 
A_array = np.array(A_list)
sort_A = np.sort(A_array)
 
XX = list()
 
for n in range(len(sort_A) - 1):
    
    r_list = list()
    
    for m in range(n+1):
        r_list.append(sort_A[n + 1] % sort_A[m] == 0)
       
    XX.append(np.array(r_list).sum() == 0)
    
XX_array = np.array(XX)        

if sort_A[0] == sort_A[1]:
    print(XX_array.sum())
    
else:
    print(XX_array.sum()+1)

Submission status: Runtime Error

Solution code:
import sys
import math 
N = int(input())
A = list(map(int, input().split()) )
A_uni = list(set(A))
A_sort = sorted(A_uni)
A_max = max(A_uni)
A_dup = [a for a in set(A) if A.count(a) > 1]

prime = []
limit = math.sqrt(A_max)
data = A_sort

while True:
    p = data[0]
    if limit <= p:
        B = prime + data
        print( len( list( set(B) - set(A_dup))))
        sys.exit()
    prime.append(p)
    data = [e for e in data if e % p != 0]

Submission status: Runtime Error

Solution code:
X,N=list(map(int,input().split()))
if N>0:p=list(map(int,input().split()))
else:p=[]
memo=[False for i in range(105)]
for i in range(N):memo[p[i]]=True

riget,left=X+1,X-1
ans_r,ans_l=0,0

while(True):
    if memo[left]==False:
        ans_l=left
        break
    if memo[riget]==False:
        ans_r=riget
        break
    left-=1
    riget+=1

if N==0 or memo[X]==False:print(X)
elif abs(X-ans_r)>=abs(X-ans_l):print(ans_l)
else:print(ans_r)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1]*2)
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[num] = False
        continue
    for j in range(2, a[-1]//num+2):
        flag[j*num] = False
counter = 0
for i in a:
    if flag[i]:
        counter += 1
print(counter)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
A = sorted([int(i) for i in input().split()])
a = collections.Counter(A)
A = np.array([i[0] for i in a.items() if i[1] == 1])

if len(A) == 0:
    print(0)
else:
    dp = np.array([True for i in range(A[-1])])
    dp[:A[0]-1] = False
    ans = 0
    for i in range(A[-1]):
        if i+1 in A and dp[i] == True:
            n = i+1
            dp[A[np.where(A % n == 0)[0]]-1] = False
            dp[i] = True
        else:
            dp[i] = False
    print(np.sum(dp))

Submission status: Runtime Error

Solution code:
from sys import stdin
n = int(input())
a = list(map(int, stdin.readline().split()))
amax = max(a)
e = [0]*(amax+1)
ans = 0

for i in range(n):
    e[a[i]] += 1
    if e[a[i]] == 1:
        for j in range(2*a[i], amax, a[i]):
            e[i] += 2

print(e.count(i))

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    ans = [1]*(10**6 +1)
    count = [False]*(10**6 +1)
    limit = len(ans)
    for t in a:
        if ans[t] == 0:
            count[t] = False
            continue
        count[t] = True
        for j in range(1, limit):
            x = t*j
            if x > limit:
                break
            ans[x] = 0
    print(count.count(True))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
if len(set(A)) == 1:
    print(0)
    exit()

from collections import Counter
c = Counter(A)

count = 0
NMAX = 2 * 10 ** 5 + 10
L = [True] * (NMAX + 1)
for k, v in c.items():
    if L[k]:
        for i in range(k * 2, NMAX + 1, k):
            L[i] = False

for k, v in c.items():
    if v > 1: continue
    if L[k] == True:
        count += 1

print(count)

Submission status: Runtime Error

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

if N == 1:
    print(1)
    exit()
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        check_list[tmp] += 1
        if tmp > 10**6:
            break
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
dp=[True]*a[-1]
for i in a:
  for j in range(i,a[-1]):
    if j%i==0:
      dp=False
cnt=0
for i in a:
  if dp[i]:
    cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
As = list(map(int, input()))

cnt = 0
l = [False]*max(As)
for A in As:
  l[A-1] = True
for i in range(N):
  if l[i-1]:
    cnt += 1
    for j in range(i, max(As), i):
      l[i-1] = False
print(cnt)