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=sorted(list(map(int,input().split())))

l=[0]*(100005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(100000//a[i]+1):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    n=ii()
    ar=li()
    hsh=[True]*n

    for i in range(n):
        if hsh[i]:
            for j in range(n):
                if j!=i and ar[j]%ar[i]==0:hsh[j]=False
    for i in range(1,n):
        if ar[0]%ar[i]==0:hsh[0]=False;break    
    ctr=0
    #print(hsh)
    for i in range(n):
        if hsh[i]:ctr+=1
    print(ctr,end='')
main()

Submission status: Runtime Error

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

l=[0]*(100005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(100000//a[i]):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np


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

A.sort()
e = np.zeros(10**6 + 1)
ans = 0
for i in range(N):
    if e[A[i]] == 0:
        e[::A[i]] = 1 # スライスで倍数indexを一気に変更できる。すごい。
        # 同じ値が重複していないか判定
        if A[i] != A[i+1]:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

new = [key for key, val in Counter(a).most_common() if val == 1]
dp = [0] * 100010

for i in new:
    temp = i
    while i <= 100000:
        dp[i] += 1
        i += temp

ans = 0
for i in new:
    if dp[i] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split())) + [10**7]

A.sort()
e = np.zeros(10**6 + 1)
ans = 0
for i in range(N):
    if e[A[i]] == 0:
        e[::A[i]] = 1 # スライスで倍数indexを一気に変更できる。すごい。
        # 同じ値が重複していないか判定
        if A[i] != A[i+1]:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

new = [key for key, val in Counter(a).most_common() if val == 1]
dp = [0] * 100010

for i in new:
    temp = i
    while i <= 100010:
        dp[i] += 1
        i += temp

ans = 0
for i in new:
    if dp[i] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

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

a_sorted = sorted(a)
divisible_list = [0] * 200010

for i in range(len(a)):
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Runtime Error

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

a_sorted = sorted(a)
divisible_list = [0] * 2 * 100010

for i in range(len(a)):
    # 過去にすでに同じ数字への加算があったら飛ばす
    if divisible_list[a[i]] > 2:
        continue
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Runtime Error

Solution code:
from collections import Counter

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

new = [key for key, val in Counter(a).most_common() if val == 1]
dp = [0] * 100010

for i in new:
    temp = i
    while i < 100010:
        dp[i] += 1
        i += temp

ans = 0
for i in new:
    if dp[i] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

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

a_sorted = sorted(a)
divisible_list = [0] * 2 * 100010

for i in range(len(a)):
    # 過去にすでに同じ数字への加算があったら飛ばす
    if divisible_list[a[i]] > 2:
        continue
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a_list(n);
    vector<int> kaburi(1e6+10),seen(1e6+10);
    for (int i = 0; i < n; i++ ) {
        cin >> a_list.at(i);
        kaburi.at(a_list.at(i))++;
    }
    sort(a_list.begin(),a_list.end());
    bool dp[int(1e6+10)] = {};
    for (int i = 0; i < int(1e6+10); i++) {
        dp[i] = 1;
    }

    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (kaburi.at(a_list.at(i)) >= 2) {
            if (seen.at(a_list.at(i)) == 1) continue;
            else {
                seen.at(a_list.at(i)) = 1;
            }
        }
        else {
            if (dp[a_list.at(i)] == 1){
                ans++;

            }
                
        } 
        for (int j = a_list.at(i); j < int(1e6+10); j += a_list.at(i)) {
            dp[j] = 0;   

        }
         
        
    }
cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
n = int(input())
ls = sorted(list(map(int, input().split())))
primes = [0] * (max(ls) + 1)
primes[0] == 1
primes[1] == 1
for i in range(round(n ** 0.5) + 1):
    if primes[ls[i]] == 0:
        for j in range(ls[i] * 2, max(ls) + 1, ls[i]):
            primes[j] = 1

count = 0
for i in ls:
    if primes[i] == 0:
        count += 1
print(count)

Submission status: Runtime Error

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

a_sorted = sorted(a)
divisible_list = [0] * 2 * 100010

for i in range(len(a)):
    # 過去にすでに同じ数字への加算があったら飛ばす
    if divisible_list[a[i]] > 2:
        continue
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Runtime Error

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

a_sorted = sorted(a)
divisible_list = [0] * 2 * 100010

for i in range(n):
    # 過去にすでに同じ数字への加算があったら飛ばす
    if divisible_list[a[i]] > 2:
        continue
    for j in range(0, len(divisible_list)+1, a[i]):
        divisible_list[j] += 1

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

Submission status: Runtime Error

Solution code:
from collections import Counter
import bisect

N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [False]*(10**6+1)
for i in range(N):
    if c[A[i]] == 1:
        ok = True
        l = bisect.bisect_left(A, int(A[i]**0.5)+1)
        for j in range(l+1):
            if A[i] % A[j] == 0 and (d[A[j]] or d[A[i]//A[j]]):
                ok = False
                break
        if ok:
            ans += 1
    d[A[i]] = True

print(ans)

Submission status: Runtime Error

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

a_sorted = sorted(a)
divisible_list = [0] * 2 * 100000

for i in range(n):
    # 過去にすでに同じ数字への加算があったら飛ばす
    if divisible_list[a[i]] > 1:
        continue
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Runtime Error

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

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

for i in range(N):
    tmp = A[i]
    if dp[tmp] != 0:
        dp[tmp] = 2
        continue
    else:
        for j in range(tmp, maxi, tmp):
            dp[j] += 1

ans = 0
for i in range(N):
    tmp = A[i]
    if dp[tmp] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
m = 1000000

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  else:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

Submission status: Runtime Error

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

A = sorted(A, key=lambda x: x[0])
maxi = 2*(10**5)+1
dp = [0] * maxi

for i in range(N):
    tmp = A[i]
    if dp[tmp] != 0:
        dp[tmp] = 2
        continue
    else:
        for j in range(tmp, maxi, tmp):
            dp[j] += 1

ans = 0
for i in range(N):
    tmp = A[i]
    if dp[tmp] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
ls = sorted(list(map(int, input().split())))
dead = []
for i in range(round(n ** 0.5) + 1):
    if ls[i] not in dead:
        for j in range(ls[i], ls[-1] + 1, ls[i]):
            if j in ls: 
                dead.append(j)

print(n - len(dead))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
m = 1000000

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  elif cnt[a[i]] == 1:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
m = 1000000

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m-1, a[i]):
      cnt[j] += 1
  elif cnt[a[i]] == 1:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
L = list(map(int,input().split()))
dp = [0]*(2*(10**5)+1000)
for i in range(n):
    dp[L[i]] +=1

one = []
for i in range(len(dp)):
    if dp[i] == 1:
        one.append(i)

dp = [0]*(2*(10**5)+1000)
a = list(set(L))
for i in L:
    for j in range(2*i,(2*(10**5)+1000),i):
        if not dp[j-1]:
            dp[j-1] = 1

ans = 0
for i in one:
    if dp[i-1] == 0:
        ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
L = list(map(int,input().split()))
dp = [0]*(2*(10**5)+1000)
for i in range(n):
    dp[L[i]] +=1

one = []
for i in range(len(dp)):
    if dp[i] == 1:
        one.append(i)

dp = [0]*(2*(10**5)+1000)
a = list(set(L))
for i in L:
    for j in range(2*i,max(L)+1,i):
        if not dp[j-1]:
            dp[j-1] = 1

ans = 0
for i in one:
    if dp[i-1] == 0:
        ans +=1
print(ans)

Submission status: Runtime Error

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

import sys

def main():
    numbers=[]
    counter=0
    n = int(input())
    numbers=list(map(int,input().split()))
    dp = [0]*max(numbers)
    dp.append(0)

    for i in range(1,max(numbers)+1):
	    for number in numbers:    
            if i % number ==0:
                dp[i]+=1
    for number in numbers:
        if dp[number]==1:
            counter+=1
    print(counter)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dp = [0]*(2*(10**5)+1000)
one = list(set(L))
for i in L:
    for j in range(2*i,max(L)+1,i):
        if not dp[j-1]:
            dp[j-1] = 1

ans = 0
for i in one:
    if dp[i-1] == 0:
        ans +=1
print(ans)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    max_a = max(mylist)
    exlude_list = set()
    tlist = [False] * (max_a+1)
    for a in mylist:
        if tlist[a]:
            exclude_set.add(a)
        else:
            tlist[a] = True
    ans = 0
    
    for i in range(1, max_a//2 + 1):
        if not tlist[i]:
            continue
        else:
            for j in range(2*i, max_a+1, i):
                tlist[j]=False
    for i in range(len(tlist)):
        if tlist[i] and not i in exclue_set:
            ans += 1
    print(ans)
                
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp = [0]*(2*(10**5)+1000)
one = []
for i in range(n):
    if L.count(L[i]) == 1:
        one.append(L[i])

for i in L:
    for j in range(2*i,max(L)+1,i):
        if not dp[j-1]:
            dp[j-1] = 1

ans = 0
for i in one:
    if dp[i-1] == 0:
        ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_np =np.array(A,dtype=np.int64)
A_set =set(A)
count =set()
for i in range(N):
    if np.count_nonzero(A[i] %A_np[:i] ==0) >=1:
            count.add(A[i])
ans =len(A_set - count)
print(ans)
"""

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int M = 1000005;

int main(){
    //要素数
    int n;
    cin >> n;

    //要素数分の配列を初期化
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> cnt(M);
    
    //インプットしたデータを一つのデータに格納していく
    for (int x : a){
        if (cnt[x] != 0){
            cnt[x] = 2;
            continue;
        }
        for (int i = x; i < M; i += x){
            cnt[i]++;
        }
    }

    //正解データが自分自身しかない条件の時
    int ans = 0;
    for(int x:a){
        if(cnt[x]==1) ans++;
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 10
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s <= LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    #input
    N=int(input())
    A=list(map(int,input().strip().split()))

    A.sort()

    l=[True for _ in range(A[-1]+1)]
    
    cnt=0
    for n in range(N):
        if l[A[n]]==True:
            cnt+=1
            l[A[n]]=False
            i=2
            while i*A[n]<=A[-1]:
                l[A[n]*i]=False
                i+=1
    if A[0]==A[1]:
        cnt-=1
    return cnt
if __name__=="__main__":
    print(main())

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s <= LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s <= LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        print(a)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    #input
    N=int(input())
    A=list(map(int,input().strip().split()))

    A.sort()

    l=[True for _ in range(A[-1])]
    
    cnt=0
    for n in range(N):
        if l[A[n]-1]==True:
            cnt+=1
            l[A[n]-1]=False
            i=1
            while i*A[n]-1<=len(l)-1:
                l[A[n]*i-1]=False
                i+=1
    if A[0]==A[1]:
        cnt-=1
    return cnt
if __name__=="__main__":
    print(main())

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(set(map(int, input().split())))
N = len(A)
cnt = N
dp = [0 for _ in range(N)]
A.sort()
A_max = A[-1]
p = A[0]
i = 0
while p**2 < A_max:
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if dp[j] < 2 and A[j]%p == 0:
                dp[j] += 1
                if dp[j] == 2:
                    cnt -= 1
    i += 1

for i in dp:
    if i >= 2:
        cnt -= 1
if len(A) == 1:
    print(0)
else:
    print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    for i in range(2,a[n-1],i):
        dp[i-1]=False
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(N)]
A.sort()
A_max = A[-1]
p = A[0]
i = 0
while p**2 < A_max:
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
    i += 1
cnt = 0
for i in range(N):
    if dp[i] == 1:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
for i in a:
    if lst[i] > 1:  # 配列中のカウントが2以上なら以降の処理を省略
        continue
    for j in range(a_max // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
        lst[i * j] += 1
    lst[1::i] += 1
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
for i in a:
    if lst[i] > 1:  # 配列中のカウントが2以上なら以降の処理を省略
        continue
    lst[1::i] += 1
    # for j in range(a_max // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
    #     lst[i * j] += 1
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

l=[0]*100005
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(100005//a[i]):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)

Submission status: Runtime Error

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

Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )
dp2 = np.zeros( (Amax+1,), dtype=np.bool8 )

for i in range(Amax+1):
    if i in num_list:
        for j in range(i+i, Amax+1, i):
            dp[j] = False

for n in num_list:
    dp2[n] = dp[n]

print( sum(dp2) )

Submission status: Runtime Error

Solution code:
n = int(input())
cnt = [0]*100000
ans = 0
a = list(map(int,input().split()))
a.sort()

for i in range(n):
    j = a[i]
    while j<100000:
        if cnt[j]<2:
            cnt[j]+=1
            j+=a[i]
        else:
            break
for i in range(n):
    if cnt[a[i]]<2: ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
cnt = [0]*100001
ans = 0
a = list(map(int,input().split()))
a.sort()

for i in range(n):
    j = a[i]
    while j<100001:
        if cnt[j]<2:
            cnt[j]+=1
            j+=a[i]
        else:
            break
for i in range(n):
    if cnt[a[i]]<2: ans+=1
print(ans)

Submission status: Runtime Error

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

Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )

for i in range(Amax+1):
    if dp[i]:
        if i in num_list:
            for j in range(i+i, Amax+1, i):
                dp[j] = False

print( sum(dp[np.asarray(num_list)])  )

Submission status: Runtime Error

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

Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )

for i in range(Amax+1):
    if dp[i]:
        if i in num_list:
            for j in range(i+i, Amax+1, i):
                dp[j] = False

print( sum(dp[np.asarray(num_list)])  )

Submission status: Runtime Error

Solution code:
num_list = [24, 11, 8, 3, 16]

N = len(num_list)
Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )

for i in range(Amax+1):
    if dp[i]:
        if i in num_list:
            for j in range(i+i, Amax+1, i):
                dp[j] = False

print( sum(dp[np.asarray(num_list)])  )

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
if 1 in A:
    print(0)
else:
    c = Counter(A)
    lst = []
    for k,v in c.items():
        if v==1:
            lst.append(k)
    lst.sort()
    mx = max(lst)
    ans = 0
    err = [False] + [True]*(mx)
    for l in lst:
        if err[l]:
            ans += 1
            i = 0
            while True:
                err[l*i] = False
                i += 1
                if l*i > mx:
                    break
    print(ans)

Submission status: Runtime Error

Solution code:
import collections


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

    A.sort()

    sames = 0
    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += 1

    a_max = A[-1]
    dp = [True] * a_max
    A = set(A)

    if dp[a - 1]:
         tmp_a = a * 2
         while tmp_a < a_max + 1:
             dp[tmp_a - 1] = False
             tmp_a += a

    r = 0
    for a in A:
        if dp[a - 1]:
            r += 1

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main()
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[0]*M
  for i in A:
    B[i]+=1
    if B[i]==1:
      for j in range(i*2,M,i):
        B[j]=2
  print(B.count(1))
main()

Submission status: Runtime Error

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

max_a = a[-1]
ans = [0]*(max_a+1)

for i in a:
	ans[i]+=1
for i in set(a):
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

print(ans.count(1))

Submission status: Runtime Error

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts().sort()

max_a = a[-1]
ans = [0]*(max_a+1)

for i in a:
	ans[i]+=1
for i in set(a):
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

print(ans.count(1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(10 ** 6)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 10 ** 6, a[i]):
            table[j] = False
        if i + 1 < n - 1:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n - 1:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(10 ** 6)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 10 ** 6, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def m()
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[0]*M
  for i in A:
    B[i]+=1
    if B[i]==1:
      for j in range(i*2,M,i):
        B[j]=2
  print(B.count(1))
m()

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=sorted(list(map(int,input().split())))
# すべてTrueのbool配列dp
dp=np.ones(len(A),dtype=int)
for i in range(N):
	for j in range(i+1,N):
		if dp[j] == 0:
			continue
		if A[j]%A[i]==0:
			dp[j]=0
if A[0]==A[1]:
	dp[0]=0
print(sum(dp))

Submission status: Runtime Error

Solution code:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

a.sort()

if 1 in a:
  if a[1] != 1:
  # if a.count(1) == 1:
    print(1)
  else:
    print(0)
  
  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

a = [k for k, v in collections.Counter(a).items() if v == 1]

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Runtime Error

Solution code:
from numba import njit


def main(N, a):
    a.sort()
    if a[0] == 1:
        if len(a) > 1:
            if a[1] == 1:
                return 0
        return 1
    i = 0
    while True:
        num = a[0]
        if 2 > len(a):
            return len(a)+i
        while True:
            if num == a[1]:
                a = [i for i in a if i != num]
                if 2 > len(a):
                    return len(a)+i
                num = a[0]
            else:
                break
        if num*2 > a[len(a)-1]:
            a = [i for i in a if i % num != 0]
            return len(a)+i+1
        a = [i for i in a if i % num != 0]
        i = i+1


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[:],i8[::1])')(main)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import main
    N = int(input())
    a = list(map(int, input().split()))
    print(main(N, a))