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:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = []
ans = 0
while A:
    a = A.pop(0)
    f = 0
    for p in d:
        if a % p == 0:
            f = 1
            break
    if f == 0:
        d.append(a)
        if len(A) == 0:
            break
        if a == A[0]:
            while (A) & (a == A[0]):
                A.pop(0)
        else:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import sympy
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        if i < n-1 and a[i] == a[i+1]:
            dic[a[i]] = 1
            continue
        flag = 1
        for e in sympy.divisors(a[i]):
            if dic[e]:
                flag = 0
                break
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

A.sort()

if(A[0] == A[1]):
    count = 0
else:
    count = 1

for i in range(1, N):
    flag = True
    a = A[i]
    for j in range(0, min(i + 2, N)):
        if (i != j and a % A[j] == 0):
            flag = False
            break

    if (flag):
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
n, *a = map(int, open(0).read().split())
a.sort()
cnt = n
if a[1] == a[0]:
    cnt -= 1
for i in range(n):
    for j in range(i):
        if a[i] % a[j] == 0:
            cnt -= 1
            break
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = 2 * (10 ** 5) + 1
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1]:
            prime[A[i]] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
import numpy as np

l = np.array([0] * (10**6 + 10))
for i in range(1,N):
  if A[i-1]!=A[i]:
    l[A[i]] += 1
    
if A[0]!=A[1]:
  l[A[0]] += 1
  
ans = 0
length = len(l)
for i in range(length):
  if l[i]>=1:
    ans += 1
    l[i::i] = 0
    
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    exists = [False] * (2*10**5+1)
    for a in A:
        exists[a] = True
    for i,a in enumerate(A):
        j = 0
        while A[j] ** 2 <= a:
            if a % A[j] == 0:
                break
            j += 1
        else:
            # if i == 0:
            #     dbg(i,a)
            #     ans += 1
            #     continue
            j = i-1
            while j >= 0 and a**0.5 <= A[j]:
                if a % A[j] == 0:
                    break
                j -=1
            else:
                if A.count(a) == 1:
                    ans += 1
    print(ans)


    
main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define loopinc(i, a, b, inc) for(int i = a; i < (b); i += inc)
#define loop(i, a, b) for(int i = a; i < (b); i++)
#define rep(i, n) loop(i, 0, n)
#define rrep(i, n) for (int i = n-1; i >= 0; i--)
#define endl "\n"
#define all(c) (c).begin(),(c).end()
#define lloopinc(i, a, b, inc) for(ll i = a; i < (b); i += inc)
#define lloop(i, a, b) for(ll i = a; i < (b); i++)
#define lrep(i, n) lloop(i, 0, n)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tuple<int, int, int> tiii;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

constexpr int MAX = 1000001;
bitset<MAX> space;

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	vi arr(n);
	rep(i, n) cin >> arr[i];
	sort(all(arr));
	space.reset();

	int total = n;
	rep(i, n) {
		if (space[arr[i]]) {
			total--;
			if (i >= 0 and arr[i-1] == arr[i] and (i >= n or arr[i+1] != arr[i]))
				total --;
		} else
			for (int j = arr[i]; j < MAX; j += arr[i])
				space[j] = 1;
	}
	cout << total << endl;
}

Submission status: Runtime Error

Solution code:
import copy
import sympy
N = int(input())
a = list(map(int, input().split()))

count = 0
for x in a:
    check = a.copy()
    check.remove(x)
    yaku = sympy.divisors(x)
    count_flag = True
    for y in yaku:
        if y != 1 and y in check:
            count_flag = False
            break

    if count_flag:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    b = set(a)
    count = 0

    for i in range(len(b)):
        if i == 0 and a[0] not in a[1:]:
            count += 1

        for j in range(i):
            if b[i] % b[j] == 0:
                break
            if j == i - 1:
                count += 1
    print(count)

Submission status: Runtime Error

Solution code:
N=int(input())
A=set(map(int,input().split()))
A=list(A)
ans=0
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    if A[i]%A[j]==0:
      break
    else:
      continue
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

A.sort()

if(A[0] == A[1]):
    count = 0
else:
    count = 1

for i in range(1, N):
    flag = True
    a = A[i]
    for j in range(0, i + 2):
        if (i != j and a % A[j] == 0):
            flag = False
            break

    if (flag):
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
N = int(input())

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

As.sort()

sosus = set([As[0]])

for a in As[1:]:
    flag = True
    for sosu in sosus:
        if a % sosu == 0:
            flag = False
            break
    if flag:
        sosus.add(a)

if As[0] == As[1]:
    print(len(sosus) - 1)
else:
    print(len(sosus))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    ans = 0
    #print(A)
    for i in range(N):
        flag = True
        now = A[i]
        for j in range(0,i):
            if now/A[j] == now//A[j]:
                flag = False
                break
        if i == 0:
            if now == A[1]:
                flag = False
        if flag:
           ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
import numpy as np

l = np.array([0] * (2 * 10**5 + 10))
for i in range(1,N):
  if A[i-1]!=A[i]:
    l[A[i]] += 1
    
if A[0]!=A[1]:
  l[A[0]] += 1
  
ans = 0
length = len(l)
for i in range(length):
  if l[i]>=1:
    ans += 1
    l[i::i] -= 1
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    x, n= map(int, input().split())
    if n == 0:
        print(x)
        return
    P=[]
    P = list(map(int, input().split()))
    
    for i in range(100):
        a = x-i
        b = x+i
        if a not in P:
            print(a)
            return
        elif b not in P:
            print(b)
            return
    


main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(map(int, input().split()))
if A[0] == 1:
    print(1)
else:
    ans = 0
    MAX = 1000001
    C = [False] * MAX
    for i in range(N):
        if not C[A[i]]:
            if i != N - 1 and A[i] != A[i + 1]:
                ans += 1
            elif i == N - 1:
                ans += 1
            cur = 1
            while cur * A[i] <= MAX:
                C[cur * A[i]] = True
                cur += 1
    print(ans)

Submission status: Runtime Error

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

A = sorted(A, reverse=True)

ans = 0
for i in range(N-1):
    B = A[(i+1):]
    if all(A[i] % B[j] != 0 for j in range(len(B))):
        ans += 1

if A[-1] != A[-2]:
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A_array = list(map(int, input().split()))

A_array.sort()

use_array = [0] * A_array[-1]

ans = 0

for i in range(N):
    if i != 0:
        if A_array[i] == A_array[i - 1]:
            use_array[a - 1] = 1
            continue
    if i != N - 1:
        if A_array[i] == A_array[i + 1]:
            use_array[a - 1] = 1
            continue
    a = A_array[i]
    for j in range(1, int(math.sqrt(a)) + 1):
        if a % j == 0:
            if use_array[j - 1] == 1 or use_array[a // j - 1] == 1:
                break
    else:
        ans += 1
    use_array[a - 1] = 1

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
ans=n
if A[0]%A[1]==0:ans-=1
for i in range(n):
  num=A[i]
  for j in range(i):
    if num%A[j]==0:
      ans-=1
      break
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = 0
import collections
buf = collections.Counter(dat)
dat = []
for k in buf:
    if buf[k] == 1:
        dat.append(k)
dat.sort()
#print(dat)
res = 0
used = [False] * (1000100)

for i in range(len(dat)):
    ok = True

    if used[dat[i]]:
        ok = False
    c = 0
    v = -1
    while v <= 1000010:
        c += 1
        v = dat[i] * c
        used[v] = True


    used[dat[i]] = True
    if ok:
        res += 1
print(res)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
if a[0] != a[1]:
  ans+=1
for i in range(1,n):
  flg=0
  for j in range(i):
    if a[j]*2>a[i] and a[j]!=a[i]:
      pass
    else:
      if a[i]%a[j]==0:
        flg=1
        break
  if flg==0:
    ans+=1
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(N):
    if i == 0:
        if A[0] % A[1] == 0:
            ans += 1
    else:
        for j in range(i):
            if A[i] % A[j] == 0:
                ans += 1
                break
print(N - ans)

Submission status: Runtime Error

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(a[0] == a[1]):
    f[0] = True
for i in range(1,n):
    for j in range(0,i):
        if(a[i] % a[j] == 0):
            f[i] = True
            break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

Submission status: Runtime Error

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

C=[1 for i in range(220000)]
for i in range(N):
    if C[A[i]]==0:
        continue
    for j in range(2,220000//A[i]-1):
        C[A[i]*j]=0

ans=0
for i in range(N):
    if i!=N-1 and A[i]==A[i+1]:
        C[A[i]]=0
        continue
    if C[A[i]]==1:
        ans+=1
        C[A[i]]=0

print(ans)

Submission status: Runtime Error

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

A.sort()
A.append(-1)

dat={i:False for i in range(2*10**5+100)}

ans=0
for i in range(len(A)-1):
    if dat[A[i]]:
        pass
    else:
        if A[i]!=A[i+1]:
            ans+=1
        for i in range(A[i],2*10**5+100,A[i]):
            dat[i]=True

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
A.sort()
B=[1]*(10**6+1)
counter=0
for i in range(N):
  if 0<i<N-1 and (A[i]==A[i-1] or A[i]==A[i+1]):
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  elif i==0 and A[i]==A[i+1]:
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  elif i==N-1 and A[i-1]==A[i]:
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  
  if B[A[i]]==1:
    counter+=1
    j=2
    while A[i]*j<=10**6:
      B[A[i]*j]=0
      j+=1
print(counter)

Submission status: Runtime Error

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

A.sort()

if(A[0] == A[1]):
    count = 0
else:
    count = 1

for i in range(1, N):
    flag = True
    a = A[i]
    for j in range(0, i):
        if (a % A[j] == 0):
            flag = False
            break

    if (flag):
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
ans=0
for x in range(n-1):
    ch=0
    for y in range(x+1,n):
        if a[x]%a[y]==0:
            ch=1
            break
    if ch==0:
        ans+=1
if a[-1]%a[-2]!=0:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    A = LI()
    C = set()
    n = 10**6+1
    D = [False]*n
    ans = 0
    for a in A:
        if a in D:
            D[a] = False
            continue
        D[a] = True
        C.add(a)

    for a in C:
        for i in range(2,1+n//a):
            D[i*a] = False
    ans = sum(D)
    print(ans)
    return

def examE():
    N, Q = LI()
    V = [[]for _ in range(N)]

    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

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

A.sort()
A.append(-1)

dat={i:False for i in range(2*10**5+1)}

ans=0
for i in range(len(A)-1):
    if dat[A[i]]:
        pass
    else:
        if A[i]!=A[i+1]:
            ans+=1
        for i in range(A[i],2*10**5+1,A[i]):
            dat[i]=True

print(ans)

Submission status: Runtime Error

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

A.sort()
ans=0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
sosu={}
def bunkai(x):
    global b
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:
            b.append(i)
            b.append(x//i)
for i in range(n):
    if a[i] in sosu:
        sosu[a[i]]+=1
    else:
        sosu[a[i]]=1
#print(sosu)
ok=0
for i in range(n):
    b=[]
    bunkai(a[i])
    l=len(b)
    flag=True
    for i in range(l):
        if b[i] in sosu:
            flag=False
            break
    if sosu[a[i]]!=1:
        flag=False
    if(flag):
        ok+=1
print(ok)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
すべてのjで割れない場合、カウントする。
逆に言えば、一つでもiをjで割れるようなjが存在するならば、それはカウントしない。
一番小さい数が2つあればそれはカウントしないが、基本的に一番小さい数はほかのどの数字でも割れない
Aiの制約が10**6であることから、小さい数から数えていって、10**6までの倍数の場所にマークを付ける。
初めて出てくるような数字に関して、カウントを1足してやる。
一番小さい数のコーナーケースに注意
"""
n = int(readline())
lst1 = list(map(int,readline().split()))

lst1.sort()

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

if lst1[0] == lst1[1]:
    ans = -1
    if lst1[0] == 1:
        print(0)
        exit()
else:
    ans = 0
    if lst1[0] == 1:
        print(1)
        exit()
ans = 0
for i in lst1:
    if memo[i] == 0:
        ans += 1
        j = 1
        while i*j <= 10**6:
            memo[i*j] = 1
            j += 1
    else:
        continue

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
from numba import njit
import numpy

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


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]


def solve(A):
    ans = 0
    c = collections.Counter(A)
    # dupes = {k for k, v in c.items() if v > 1}
    dupes = set()
    for k, v in c.items():
        if v > 1:
            dupes.add(k)
    aset = set(A)
    for a in A:
        if a in dupes:
            continue
        for v in (set(make_divisors(a))):
            if a == v:
                continue
            if v in aset:
                break
        else:
            ans += 1
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve((A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()
A.sort()
C = Counter(A)
kaburi = []
for c in C:
  if C[c] > 1:
    kaburi.append(c)


def make_primes(N):
  seachList = A
  primeNum = []
  while seachList[0] <= seachList[-1]//2 :
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

print(len(set(make_primes(A[-1]))-set(kaburi)))

Submission status: Runtime Error

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

A = sorted(A)
ans = 0
for i in range(N):
    for j in range(i-1, -1, -1):
        if A[i] % A[j] == 0:
            break
    else:
        if i == 0 and A[i] == A[i+1]:
            continue
        ans += 1
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(n):
    cnt = 0
    if i > 0 and a[i] == a[i - 1]:
        continue
    for j in range(i):
        if a[j] > a[i] // 2:
            break
        if a[i] % a[j] == 0:
            cnt += 1
            break
    if cnt == 0:
        if i != 0:
            # print(i, a[i])
            ans += 1
        elif a[0] != a[1]:
            # i == 0
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
A.sort()
B=[1]*(10**6+1)
counter=0
for i in range(N):
  if 0<i<N-1 and (A[i]==A[i-1] or A[i]==A[i+1]):
    continue
  elif i==0 and A[i]==A[i+1]:
    continue
  elif i==N-1 and A[i-1]==A[i]:
    continue
  
  if B[A[i]]==1:
    counter+=1
    j=2
    while A[i]*j<=10**6:
      B[A[i]*j]=0
      j+=1
print(counter)

Submission status: Runtime Error

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

A.sort()
A.append(-1)

dat={i:False for i in range(2*10**5+1)}

ans=0
for i in range(len(A)-1):
    if dat[A[i]]:
        pass
    else:
        if A[i]!=A[i+1]:
            ans+=1
        for i in range(A[i],20**5+1,A[i]):
            dat[i]=True

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    A=lispin()
    B=sorted(A)
    #print(B)
    cnt=0
    ans=0
    if B[0]<B[1]:ans+=1
    for i in range(1,N):
        temp=B[i]
        cond=1
        for j in range(i):
            if temp%B[j]==0:
                cond=0
                break
                
            else:
                cnt+=1
        if cond==1:
            ans+=1
    print(ans)
        
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
#N, M = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]

cnt = [0] * (2 * 10 ** 5 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 2 * 10 ** 5 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 2 * 10 ** 5:
        cnt[i * k] = 0
        k += 1

print(answer)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

res = [0]*(100001)
for i in a: res[i] += 1


def check(N,P):
    if N == 1:
        if P[1]==1: return True
        else: return False
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    
    for i in res:
        if i!=N and P[i] >= 1: return False
        if i==N and P[i] >= 2: return False
    return True    

ans = 0
for N in a:
    if check(N,res): ans += 1

print(ans)