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:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
int mod = 998244353;
// int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b % mod; if (a >= mod) a -= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(11);
  int T;
  T = 1;
  while (T--) solve();
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;

  const int N = 1000005;
  vector<int> b(N);

  for (int x : a) {
    if (b[x] == 0) {
      for (int y = 2 * x; y < N; y += x) b[y]++;
    }
    b[x]++;
  }
  int ans = 0;
  for (int x : a) if (b[x] == 1) ans++;
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import math
from collections import defaultdict

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

d = defaultdict(int)
for x in a:
    d[x] += 1

for x in d:
    for j in list(range(2, N)):
        if x * j >= N || b[x * j] == 1: #debuged
            break
        else:
            b[x * j] = 1

ans = 0
for x in a:
    if b[x] == 1:
        continue
    else:
        if d[x] >= 2:
            continue
        else:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
y=set(a)
acc=0
if a[0]==1 and a[1]!=1:acc+=1
dp=[True]*(a[-1]+1)
for i in range(2,a[-1]+1):
  if i in y:
    if dp[i]==True:
      idx=bisect(a,i)
      if a[idx-1]==a[idx-2]:
        dp[i]=False
      else:acc+=1
    dp[2*i::i]=[False]*len(dp[2*i::i])
print(acc)

Submission status: Runtime Error

Solution code:

n=int(input())
m=list(map(int,input().split()))
k=10**6
p=[0]*k
m.sort()
for i in range(1,n):
    if m[i]==m[i-1]:
        p[m[i]]=1
res=0
for i in range(n):
    if p[m[i]]==0:
        res+=1
    
    for j in range(m[i]*2,k,m[i]):
        p[j]=1
print(res)

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict

d=defaultdict(int)
m=10**6
sieve=[-1]*10**6
n=IN()
a=LI()
for i in range(n):
    d[a[i]]+=1
    for j in range(2*a[i],m,a[i]):
        sieve[j]=1
ans=0
for i in a:
    if sieve[i]==-1 and d[i]==1:
        ans+=1
print(ans)

Submission status: Runtime Error

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

a.sort()

table=[True]*1000001
count=0
if n==1:
  count=1
else:
  for i in range(0,n):
    pp=a[i]
    if table[pp]==True:
      if i==0:
        if a[i]!=a[i+1]:
          count+=1
          for j in range(pp,1000002,pp):
            table[j]=False
      elif i==n-1:
        if a[i]!=a[i-1]:
          count+=1
          for j in range(pp,1000002,pp):
            table[j]=False
      else:
        if a[i]!=a[i+1] and a[i]!=a[i-1]:
          count+=1
          for j in range(pp,1000002,pp):
            table[j]=False
      
print(count)

Submission status: Runtime Error

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

a.sort()

table=[True]*1000001
count=0
for i in range(0,n):
  pp=a[i]
  if table[pp]==True:
    if i==0:
      if a[i]!=a[i+1]:
        count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
    elif i==n-1:
      if a[i]!=a[i-1]:
        count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
    else:
      if a[i]!=a[i+1] and a[i]!=a[i-1]:
        count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
      
print(count)

Submission status: Runtime Error

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

a.sort()

table=[]
for i in range(1000001):
  table.append([True,0])
count=0
for i in range(0,n):
  pp=a[i]
  if table[pp][0]==True:
    if i==0:
      if a[i]!=a[i+1]:
        count+=1
    elif i==n-1:
      if a[i]!=a[i-1]:
        count+=1
    else:
      if a[i]!=a[i+1] and a[i]!=a[i-1]:
        count+=1
  if table[pp][1]==0:
    table[pp][1]=1
    for j in range(pp,1000001,pp):
      table[j][0]=False
      
print(count)

Submission status: Runtime Error

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

a.sort()

table=[]
for i in range(1000001):
  table.append([True,0])
count=0
for i in range(0,n):
  if table[a[i]][0]==True:
    count+=1
  if table[a[i]][1]==0:
    table[a[i]][1]=1
    for j in range(a[i],1000002,a[i]):
      table[j][0]=False
  elif table[a[i]][1]==1:
    count-=1
    table[a[i]][1]=2
      
print(count)

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
max = 10**6+1
index = []
for i in range(max):
  index.append(0)
for i in range(N):
  for j in range(max):
    if(A[i]*j>max):break
    index[A[i]*j] += 1
count = 0
for i in range(N):
  if(index[A[i]]==1):count+=1


print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(stdins) for stdins in input().split()]

a.sort()

ans = n
divisibles = []
for i in range(n):
    divisible = False
    for j in range(n):
        if i == j:
            continue
        elif a[i] < a[j]:
            break
        elif divisibles[j]:
            continue
        elif a[i] % a[j] == 0:
            ans -= 1
            divisible = True
            break
    divisibles.append(divisible)

print(ans)

Submission status: Runtime Error

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

if 1 in a:
    print(0)
    exit()
elif 

print(a)
count = 0
count_a = 0
for i in range(1,n):
    for j in range(i):
        print(a[i],a[j])
        if a[i]%a[j] == 0:
            print("divided")
            break
        else:
            count_a += 1
            print(count_a,"count_a")
        
    if count_a == i:
        count += 1
        print("count +1しました")
        count_a =0
    else:
        print("countしませんでした")
        count_a =0



print(count)

Submission status: Runtime Error

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

a_max = a[-1]
ans_list = [0] * a_max

ans = 0

for i in range(n):

    p = a[i]
    
    if ans_list[p-1] == 0:
        for q in range(1, (a_max//p)+1):
            ans_list[p*q-1] = 1
        
        if a[i] != a[i+1]:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[-1]
count = 0
cnt_list = [1] * ((10 ** 5) * 2 + 1)
for i in range(len(A_list)-1):
    if cnt_list[A_list[i]] == 1:
        for j in range(A_max // A_list[i]):
            cnt_list[A_list[i] * j] = 0
        if A_list[i] != A_list[i+1]:
            count += 1
if cnt_list[A_list[-1]] == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[-1]
count = 0
cnt_list = [1] * ((10 ** 5) * 2 + 1)
for i in range(len(A_list)-1):
    if cnt_list[A_list[i]] == 1:
        for j in range((A_max // A_list[i]) + 1):
            cnt_list[A_list[i] * j] = 0
        if A_list[i] != A_list[i+1]:
            count += 1
if cnt_list[A_list[-1]] == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
ans = 1
flag = 0
#第1項が割り切れる場合答えは0。割り切れるとしたら次の項で可能。
if A[0] % A[1] == 0:
  print(0)
  exit()
#第二項以降を考える。
for i in range(1,N):
  for j in range(i-1):
    if A[i] % A[j] == 0:
      flag += 1
  if flag == 0:
    ans += 1
  else:
    flag = 0
    
print(ans)

Submission status: Runtime Error

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

C = {a:0 for a in A}

for a in A:
    C[a] = C[a]+1

maxA = max(A)

D = {a:0 for a in A}

for a in A:
    t = 2
    while a*t <= maxA:
        D[a*t] += 1
        t = t+1

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter = counter+1
        
print(counter)

Submission status: Runtime Error

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

C = {a:0 for a in A}

for a in A:
    C[a] = C[a]+1

maxA = max(A)

D = {a:0 for a in A}

for a in A:
    t = 2
    while a*t <= maxA:
        D[a*t] = D[a*t]+1
        t = t+1

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter = counter+1
        
print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
*A, = map(int, input().split())
# n = 10
# A = [33, 18, 33, 28, 8, 19, 89, 86, 2, 4]

C = {a:0 for a in A}

for a in A:
    C[a] = C[a]+1

maxA = max(A)

D = {a:0 for a in A}

for a in A:
    t = 2
    while a*t <= maxA:
        D[a*t] += D[a*t]+1
        t = t+1

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter = counter+1
        
print(counter)

Submission status: Runtime Error

Solution code:
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    s = set()
    cnt = collections.Counter(arr)
    for i in ragne(n):
        if arr[i] in s:
            continue
        elif cnt[arr[i]] >= 2:
            s.add(arr[i])
        for j in range(2, 10**6//arr[i]+1):
            s.add(arr[i]*j)
    ans = 0
    for i in arr:
        if i in s == False:
            ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

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

for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a
print(len(S))

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
count = 0
lis = [0 for i in range((10**6)+10)]
for i in range(a[0],(10**6)+5,a[0]):
    lis[i+1] += 1
for i in range(a[1],(10**6)+5,a[1]):
    lis[i+1] += 1
for i in range(2,n):
    if a[i] == a[i-1] and a[i-1] == a[i-2]:
        continue
    else:
        for j in range(a[i],(10**6)+5,a[i]):
            lis[j+1] += 1
for i in range(n):
    if lis[a[i]+1] <= 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
count = 0
lis = [0 for i in range((10**6)+10)]
for i in range(a[0],(10**6)+5,a[0]):
    lis[i+1] += 1
for i in range(a[1],(10**6)+5,a[1]):
    lis[i+1] += 1
for i in range(2,n):
    if a[i] == a[i-1] and a[i-1] == a[i-2]:
        continue
    else:
        for j in range(a[i],(10**6)+5,a[i]):
            lis[j+1] += 1
for i in range(n):
    if lis[a[i]+1] == 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
count = 0
lis = [0 for i in range(2*(10**6))]
for i in range(a[0],(10**6)+5,a[0]):
    lis[i+1] += 1
for i in range(a[1],(10**6)+5,a[1]):
    lis[i+1] += 1
for i in range(2,n):
    if a[i] == a[i-1] and a[i-1] == a[i-2]:
        continue
    else:
        for j in range(a[i],(10**6)+5,a[i]):
            lis[j+1] += 1
for i in range(n):
    if lis[a[i]+1] == 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
count = 0
lis = [0 for i in range(2*(10**6))]
for i in range(a[0],(10**6)+1,a[0]):
    lis[i+1] += 1
for i in range(a[1],(10**6)+1,a[1]):
    lis[i+1] += 1
for i in range(2,n):
    if a[i] == a[i-1] and a[i-1] == a[i-2]:
        continue
    else:
        for j in range(a[i],(10**6)+1,a[i]):
            lis[j+1] += 1
for i in range(n):
    if lis[a[i]+1] == 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
count = 0
lis = [0 for i in range(3*(10**5))]
for i in range(a[0],2*(10**5)+5,a[0]):
    lis[i+1] += 1
for i in range(a[1],2*(10**5)+5,a[1]):
    lis[i+1] += 1
for i in range(2,n):
    if a[i] == a[i-1] and a[i-1] == a[i-2]:
        continue
    else:
        for j in range(a[i],2*(10**5)+5,a[i]):
            lis[j+1] += 1
for i in range(n):
    if lis[a[i]+1] == 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
count = 0
lis = [0 for i in range(3*(10**5))]
for i in range(a[0],2*(10**5)+1,a[0]):
    lis[i+1] += 1
for i in range(a[1],2*(10**5)+1,a[1]):
    lis[i+1] += 1
for i in range(2,n):
    if a[i] == a[i-1] and a[i-1] == a[i-2]:
        continue
    else:
        for j in range(a[i],2*(10**5)+1,a[i]):
            lis[j+1] += 1
for i in range(n):
    if lis[a[i]+1] == 1:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())

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

cntList = [1] * (intList[-1] + 1)

i = 0
j = 1
ans = 0

while i < (N - 1):
  base = intList[i]
  j = 1
  num = base
  if cntList[num] == 1:
    while num < intList[-1]:
      if cntList[num] == 1:
        cntList[num] = 0
      j += 1
      num = base * j
    if intList[i] != intList[i+1]:
      ans += 1
  i += 1

if cntList[intList[-2]] == 1:
  ans += 1
  
print(ans)

Submission status: Runtime Error

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i  <a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    #r+=1
  print(r)
main()

Submission status: Runtime Error

Solution code:
import sympy
n = int(input())
a = [int(k) for k in input().split()]
c = 0
for i in range(n):
    l = sympy.divisors(a[i])
    l.remove(1)
    for j in range(n):
        if i == j:
            continue
        if a[j] in l:
            break
    else:
        # print(a[i])
        c += 1
print(c)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)
    dup = 0

    for i in a:
        if table[i-1]:
            if i not in res:
                res.append(i)
            else:
                dup += 1  
                continue
        else:
            continue
        for j in range(i *2, amax, i):
            table[j-1] = False
    print(len(res) - dup)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

cnt = [0] * 200001

for i in A:
  if cnt[i] == 1:
    continue 
  if cnt[i] == 2:
    cnt[i] = 1
    continue
  cnt[i] = 2
  for j in range( (i+i),200001,i):
    cnt[j] = 1
#
ans = 0
for i in range(200001):
  if cnt[i] == 2:
    ans += 1
#
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.unit64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      d[a::a] += 1
    else:
      d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
print(main())

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.unit64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
        d[a::a] += 1
      else:
        d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.unit64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      if a != a1:
        d[a::a] += 1
      else:
        d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.unit64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      if a != a1:
        d[a::a] += 1
      else:
        d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
print(main())

Submission status: Runtime Error

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

a.sort()

b=[]


while True:    
    i = a.pop(0)
    if i in a:
        a = [x for x in a if x != i]
        continue
    a = [x for x in a if x%i != 0]
    b.append(i)
    if len(a) == 0:
        break

print(len(b))

Submission status: Runtime Error

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

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

for a in A:
    dp[a] += 1

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))

Submission status: Runtime Error

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

dp = [0] * (2*(10**5))

for a in A:
    dp[a] += 1

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
N = int(input())
As = list(map(int,input().split()))
ct = Counter(As)
As =sorted(As)
max_dp = As[-1] +1
dp = [True] * max_dp
for key,count in ct.items():
	if count > 1:
		dp[key] = False
for A in As:
	if dp[A] == True:
		i = 2
		while A*i <= max_dp:
			dp[A*i] = False
			i+=1

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

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
N = int(input())
As = map(int,input().split())

As = sorted(As)
max_dp = As[-1] +1
dp = [True] * max_dp

for A in As:
	if dp[A] == True:
		i = 2
		while A*i <= max_dp:
			dp[A*i] = False
			i+=1

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

Submission status: Runtime Error

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

for i in range(len(A)-1):
  p=A[i]
  if dp[i]==1:
    for q in range(ma//p+1):
      dp[p*q]=0
    if A[i]!=A[i+1]:
      ans+=1
if dp[ma]==1:
  ans+=1
print(ans)

Submission status: Runtime Error

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

for i in range(len(A)-1):
  p=A[i]
  if dp[i]==1:
    for q in range(ma//p+1):
      dp[p*q]=0
    if dp[i]!=dp[i+1]:
      ans+=1
if dp[ma]==1:
  ans+=1
print(ans)

Submission status: Runtime Error

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

for i in range(N-1):
  p=dp[i]
  if dp[i]==1:
    for q in range(ma//p+1):
      dp[p*q]=0
    if dp[i]!=dp[i+1]:
      ans+=1
if dp[ma]==1:
  ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_nd = np.array(a)
sorted_a = np.sort(a_nd)
array = []
for _ in range(n):
  array.append(True)
  
for i in range(n):
  if (array[i]):
    if i < n-1 and sorted_a[i] == sorted_a[i+1]:
      array[i] = False
      array[i+1] = False
      num = i+2
      while(sorted_a[i] == sorted_a[num]):
        array[num] = False
        num += 1
      
    else:
      for j in range(i):
        if (array[j] and sorted_a[i] % sorted_a[j] == 0):
          array[i] = False
          break
print(array.count(True))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
A = list(set(A))
Amax = A[-1]              #最大値
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る
ans = 0
# print(A)
if len(A)!=1:
    for i in range(len(A)):
      p = A[i]
      if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
        
        for q in range(Amax//p+1):
          dp[p*q] = 0         #A[i]の倍数をすべて0にする
        # print(dp)
      else:
          ans+=1
        #   print(A[i])
    #     if A[i] != A[i+1]: 
    #       ans += 1            #A[i]が重複していなければカウント
    #     print(ans)
    # if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
    #   ans += 1
    print(len(A)-ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
import collections
 
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
 
for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1
 
print(ans)
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)

for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np


def solve(sequence):

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[::1])')(solve)
    cc.compile()
    exit()


from my_module import solve


def main():
    _ = input()
    sequence = np.array(input().split(), np.int64)
    print(solve(sequence))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np


def solve(sequence):

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[::1])')(solve)
    cc.compile()
    exit()


from my_module import solve


def main():
    sequence = np.array(input().split(), np.int64)
    print(solve(sequence))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a_lst = list(map(int, input().split()))
index_lst = [0]*(a_max + 1)

for ai in a_lst:
    for multi in range(ai, a_max+1, ai):
        index_lst[multi] += 1

ans = 0
for ai in a_lst:
    if index_lst[ai] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:]))
def main(A, B):
    ans = 0

    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

    for a in A:
        if B[a] == 1:
            ans += 1

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A), np.array(B))
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+10)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6+10:
        checker[a[i]*x] = 0
        x += 1
print(result)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6+1:
        checker[a[i]*x] = 0
        x += 1
print(result)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

M = 10**6 + 1

table = [1] * M

B = Counter(a)
Key = list(B.keys())

count = 0
for x in Key:
    if B[x] == 1 and table[x] == 1:
        count += 1

    for i in range(M):
        if i * x > M:
            break
        else:
            table[i * x] = 0

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
idx = np.argsort(A)
A = np.sort(A)
Z = np.zeros(N)

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        for j in range(i):
            if Z[j] != 0:
                continue
            d, m = divmod(A[i], A[j])
            if m == 0:
                flag = False
                Z[i] = 1
                break
        if flag:
            result += 1
    return result

print(get_result())

Submission status: Runtime Error

Solution code:
from collections import Counter
import bisect
n = int(input()) #リストの要素数
a = list(map(int, input().split())) #リストの要素
cnt = Counter(a) #aの要素数についての辞書
a.sort()#aを小さい順にソート
ans = 0
mx = 10 ** 6
p = [0] * (mx + 1)
for i in a:
    if p[a] == 0:
        for j in range(mx + 1):
            x = i * j
            if x > mx:
                break
            p[x] = 1 #pの中でaの要素iの倍数として表現できるものに１
        if cnt[a] == 1:
            ans += 1 #pの中で任意のiの倍数として表現できず、かつ１つのみ存在するものをカウント
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
B = set(A)
C= N-len(B)
count = 0
for i in range(N):
    for j in range(i + C):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
cnt_d = [0] * (max(a) + 1)
cnt_nd = 0
for ai in a:
    if cnt_d[ai] >= 1:
        continue
    else:
        cnt_d[ai] += 1
        cnt_nd += 1
    multi = 2
    while ai*multi <= max_a:
        cnt_d[ai*multi] += 1
        multi += 1
print(cnt_nd)

Submission status: Runtime Error

Solution code:
n=int(input())
p=sorted(list(map(int,input().split())))
s=[]
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
flag = True
for x in p:
    if prev == x:
        if flag and s[-1] == x:
            s.pop()
            flag = False
        continue
    if a[x]:
        s.append(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x
    flag = True

print(len(s))

Submission status: Runtime Error

Solution code:
n=int(input())
p=sorted(list(map(int,input().split())))
s=[]
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
flag = True
for x in p:
    if prev == x:
        if flag:
            s.pop()
            flag = False
        continue
    if a[x]:
        s.append(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x
    flag = True

print(len(s))

Submission status: Runtime Error

Solution code:
n=int(input())
p=sorted(list(map(int,input().split())))
s=[]
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
flag = True
for x in p:
    if prev == x and flag:
        s.pop()
        flag = False
        continue
    if a[x]:
        s.append(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x
    flag = True

print(len(s))

Submission status: Runtime Error

Solution code:
_, *a = map(int, open("/Users/rikuo/Downloads/03-LargeRandom-23 (1)").read().split())
a.sort()
m = -~a[-1]
c = [0] * m
for i in a:
    c[i] += 1
    if c[i] > 1:
        continue
    for j in range(i * 2, m, i):
        c[j] = 2
print(sum(c[i]for i in a))

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
count=[]
for i in range(n):
  	flag=0
  	for j in range(n):
    	if i!=j:
      		if a[j]%a[i]==0:
        		flag=1
	if flag==0:
    	count.apend(i) 
    
print(len(count))

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
count=[]
for i in range(n):
  	flag=0
	for j in range(n):
    	if i!=j:
    		if a[j]%a[i]==0:
		 		flag=1
	if flag==0:
      count.apend(i) 
    
print(len(count))