Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Runtime Error

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
M = max(A)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <= 2*M+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Runtime Error

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
M = max(A)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <= M+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Runtime Error

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
while i < N:
    e = A[i]
    j=i+1
    if j < N:
        if A[j]==e:
            while A[j] == A[i] and j < N:
                j+=1
            i = j
        else:
            Cs[e] = 1
            i+=1
    else:
        Cs[e] = 1
        i+=1
#print(Cs[:30])
for e in A:
    i = 2
    while e*i < 10**6 +1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Runtime Error

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
while i < N:
    e = A[i]
    j=i+1
    if j < N and A[j]==e:
        while A[j] == A[i]:
            i+=1
        i = j
    else:
        Cs[e] = 1
        i+=1
#print(Cs[:30])
for e in A:
    i = 2
    while e*i < 10**6 +1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Runtime Error

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
while i < N:
    e = A[i]
    j=i+1
    if j < N and A[j]==e:
        while A[j] == A[i]:
            i+=1
        i = j
    else:
        Cs[e] = 1
        i+=1
#print(Cs[:30])
for e in A:
    i = 2
    while e*i < M+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
res = 0
Ab = [True] * N
cnt = 0
for i in range(N):
    if not Ab[i]:
        continue
    for j in range(i+1,N):
        if Ab[j] :
            if A[j] % A[i] == 0:
                 Ab[j] = False
                if A[i] == A[j]:
                    Ab[i] = False
print(Ab.count(True))

Submission status: Runtime Error

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

F=[0]*(10**6+11)

for a in A:
    if F[a]==2:
        F[a]=1
        continue
    elif F[a]==0:
        F[a]=2
    k=2*a
    while 1:
        F[k]=1
        k+=a
        if not k<=10**6+10:
            break
res=0
for a in A:
    if F[a]==2:res+=1
print(res)

Submission status: Runtime Error

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

sieve = [True] * 1000001

prev = 0

for i in range(N):
    if As[i] == prev:
        sieve[As[i]] = False
        continue
    else:
        prev = As[i]
        try:
            for j in range(2, 1000000 // prev + 1):
                sieve[prev * j] = False
        except:
            continue

count = 0
As = list(set(As))
for i in range(N):
    if sieve[As[i]] is True:
        count += 1
        
print(count)

Submission status: Runtime Error

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

sieve = [True] * 1000001

prev = 0

for i in range(N):
    if As[i] == prev:
        sieve[As[i]] = False
        continue
    else:
        prev = As[i]
        for j in range(2, 1000000 // prev + 1):
            sieve[prev * j] = False

count = 0
As = list(set(As))
for i in range(N):
    if sieve[As[i]] is True:
        count += 1
        
print(count)

Submission status: Runtime Error

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

sieve = [True] * 1000000

count = 1
prev = As[0]
for j in range(1000000 // prev + 1):
    sieve[prev * j - 1] = False


for i in range(N):
    if As[i] == prev:
        continue
    else:
        prev = As[i]
        if sieve[prev] is True:
            count += 1
        for j in range(1000000 // prev + 1):
            sieve[prev * j - 1] = False

print(count)

Submission status: Runtime Error

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

if As[0] == As[1]:
  count = 0
else:
  count = 1
  
for i in range(1, N):
  count_sub = 0
  for j in range(i):
    if As[i] % As[j] == 0:
      count_sub += 1
  if count_sub == 0:
    count += 1
    
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
# print(A)
multiple = [0]*(A[-1]+1)
for i in range(n):
    now = A[i]
    while(now <= A[-1]):
        multiple[now] += 1
        now += now
ans = 0
for i in range(N):
    if(multiple[A[i]] == 1):
        ans += 1
# print(multiple)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
# print(A)
ans = 0
for i in range(max(len(A)-1,1)):
    f = 1
    for j in range(i+1,len(A)):
        # print(A[i],A[j])
        if(A[i]%A[j] == 0):
            # print("__")
            f = 0
            break
    if(f == 0):
        ans += 1
if(A[-2] == A[-1]):
    ans += 1
print(n-ans)

Submission status: Runtime Error

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

A = max(a)

cnt = [0]*(A+1)
uq = []

for i in a:
    cnt[i] += 1

for i in range(A+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*((10**6)+1)
cnt1 = 0


a = list(set(a))



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


for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Runtime Error

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

A = max(a)

cnt = [0]*(A+1)
uq = []

for i in a:
    cnt[i] += 1

for i in range(A+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*((10**6)+1)
cnt1 = 0


a = list(set(a))



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


for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
INF = 10**6+1
lis = [1]*INF
exist = [0]*INF
for i in range(N):
    a = A[i]
    exist[a] += 1
    if lis[a]:
        for q in range(2, INF // a + 1):
            lis[a*q] = 0
cnt = 0
for a in A:
    if lis[a] and exist[a] == 1:
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

la = len(a)
if la == 1:
    print(0)
    exit()
l = [True] * la
for i in range(1, n):
    for j in range(i):
        if a[i] % a[j] == 0:
            l[i] = False
            break
print(l.count(True))

Submission status: Runtime Error

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

cnt = [0] * 40
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,40,x):
            cnt[i] += 1

ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
lst = list(map(int,input().split()))

lst.sort()

s = 1
while True:
  if len(lst) == 1:
    break
  a = deque([])
  if lst[0] == lst[1]:
    s -= 1
  for k in range(1,len(lst)):
    if lst[k] % lst[0] != 0:
      a.append(lst[k])
  lst = a    
  if a == []:
    break
  s += 1
  

print(s)

Submission status: Runtime Error

Solution code:
n = int(input())
lst = list(map(int,input().split()))
arr = np.array(lst)
lst.sort()

s = 1
while True:
  if len(lst) == 1:
    break
  a = []
  if lst[0] == lst[1]:
    s -= 1
  for k in range(1,len(lst)):
    if lst[k] % lst[0] != 0:
      a.append(lst[k])
  lst = a    
  if a == []:
    break
  s += 1
  print(lst)

print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
am=a[-1]
count=0
trush=set()
for i in range(len(a)):
    if a[i] in trush:
        continue
    if i>=1:
        if a[i-1]==a[i]:
            continue
    elif a[i]==a[i+1]:
        continue
    count+=1
    for j in range(a[i],am+1,a[i]):
        trush.add(j)
print(count)

Submission status: Runtime Error

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

D = [0] * (10**6 + 1)
A.sort()
for i in range(N):
    D[A[i]] += 1
    
ans = 0
for i in range(1, 10**6+1):
    if D[i]:
        if D[i]==1:
            ans += 1
        for j in range(i,m,i):
            D[j] = 0
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = max(a)
li = [0]*m 
for x in a:
    li[x] += 1
ans = 0
for i in range(1,m):
    if li[i]: 
        if li[i]==1: 
            ans += 1 
        for j in range(i,m,i): 
            li[j] = 0
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = max(a)
li = [0]*m 
for x in a:
    li[x] += 1
ans = 0
for i in range(1,m):
    if li[i]: 
        if li[i]==1: 
            ans += 1 
        for j in range(i,m,i): 
            li[j] = 0

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
l = [0]*(10**6)

for i in a:
  if l[i] == 0:
    l[i] = 1
    for j in range(i*2,max(a)+1,i):
      l[j] = -1
  else:
    l[i] = -1
print(l.count(1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
l = [0]*(10**6)

for i in a:
  if l[i] == 0:
    l[i] = 1
    for j in range(i*2,max(a)+1,i):
      l[j] = -1
  elif l[i] == 1:
    l[i] = -1
print(l.count(1))

Submission status: Runtime Error

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

A.sort()

dp=[False]*(10**6)
ans=0
for idx,i in enumerate(A):
  if dp[i]:continue
  tmp=i
  ans+=1
  while tmp<10**6:
    dp[tmp]=True
    tmp+=i
  if idx!=len(A)-1 and A[idx+1]==i:
    ans-=1
print(ans)

Submission status: Runtime Error

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

dp=[False]*(10**6)
ans=0
for i in A:
  if dp[i]:continue
  tmp=i
  ans+=1
  while tmp>10**6:
    dp[tmp]=True
    tmp+=i
print(ans)

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):
        Ai = A[i]
        is_divisible = False
        for j in range(i):
            Aj = A[j]
            if Aj**2 > Ai:
                break
            if Ai%Aj == 0:
                is_divisible = True
                break
        if not is_divisible:
            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()
now = 0
first_flag = 0
if A[0] == A[1]:
  first_flag = 1

while now < len(A):
  tmp = A[now]
  i = now + 1
  while i < len(A):
    if A[i] % tmp == 0:
      A.pop(i)
    else:
      i += 1
  now += 1

if first_flag == 1:
  print(len(A)-1)
else:
  print(len(A))

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
s = [0]*N
print(A)
for i in range(len(A)):
    if(s[i]==0):
        for j in range(i+1,len(A)):
            if(A[j]%A[i]==0):
                s[j] = 1
print(s)
ans = 0
for i in s:
    if(i == 0):
        ans += 1
if(A[0]==A[1]):
    ans -= 1
print(ans)

Submission status: Runtime Error

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

if N == 1:
  print(1)
  exit()

flag = [0]*(10**6+5)
for i in range(N):
  flag[A[i]] = 1

for i in range(N):
  if flag[A[i]] == 0:
    continue
  if i>0 and A[i]==A[i-1]:
    flag[A[i]] = 0
    continue
  for num in range(A[i]*2,A[-1]+A[i],A[i]):
    flag[num] = 0
  
print(sum(flag))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
l=[1]*n
a.sort()
if a[0]==a[1]:
    l[0]=0
for i in range(n-1):
    for j in range(i+1,n):
        if a[j]%a[i] == 0:
            l[j]=0
print(sum(l))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
data = [0 for _ in range(200001)]
for x in a:
    data[x] += 1

ans = 0
for i in range(1,200001):
    if not data[i]:continue
    if data[i] == 1:ans += 1
    j = i
    while j < 200001:
        data[j] = 0
        j += i

print(ans)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A) - 1]
valid = [True] * (maxA + 1)
for i in range(1, len(valid)):
    if valid[i] == False or not i in A:
        continue
    else:
        for j in range(2, maxA // i + 1):
            valid[j * i] = False
count = 0
for i in range(len(A)):
    if i == 0 and A[i] == A[i+1]:
        continue
    if i != 0 and A[i-1] == A[i]:
        continue
    if valid[A[i]]:
        count += 1
print(count)

Submission status: Runtime Error

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

a.sort()
#print(a)
flag = 0
if a[0] == a[1]:
    ans = 0
else:
    ans = 1
if a[0] == 1:
    print(ans)
    exit(0)

if 2 in a:
    flag = 1
    
dict = {a[0]:1}

for i in range(1,n):
    #print(str(i) + ":")
    for j in range(1,round(math.sqrt(a[i]))+1):
        if flag == 1 and a[i] % 2 == 0:
            break 
        if a[i] % j == 0:
            #print(j)
            if j in dict.keys():
                break
            if a[i] // j in dict.keys():
                break
        if j == round(math.sqrt(a[i])):
            ans += 1
            #print("ans:" + str(ans))
    dict[a[i]] = 1
    
print(ans)

Submission status: Runtime Error

Solution code:
# Not Divisible

N = int(input())
A = [int(n) for n in input().split()]

check = [0] * 1000000
A.sort()

ok = [-1]
p = 0
for a in A:
    if a == p:
        if ok[-1] == p:
            ok = ok[:-1]
        continue
    p = a
    if check[a] == 1:
        continue
    for i in range(a, 1000000, a):
        check[i] = 1
    ok.append(a)

print(len(ok) - 1)

Submission status: Runtime Error

Solution code:
# Not Divisible

N = int(input())
A = [int(n) for n in input().split()]

check = [0] * 1000000
A.sort()

ok = []
p = -1
for a in A:
    if a == p:
        continue
    p = a
    if check[a] == 1:
        continue
    for i in range(a, 1000000, a):
        check[i] = 1
    ok.append(a)

print(len(ok))

Submission status: Runtime Error

Solution code:
N = int(input())
data_A = input()

A = data_A.strip().split()
for i in range(0,N):
    A[i] = int(A[i])

count = 0

for i in range(0,N):
    for j in range(0,N):
        if j == i:
            pass
        else:
            check = False
            if A[i] < A[j]:
                pass
            elif A[i] % A[j] == 0:
                check = True
                break
    if check:
        pass
    else:
        count = count + 1


print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
data_A = input()

A = data_A.strip().split()
for i in range(0,N):
    A[i] = int(A[i])

count = 0

for i in range(0,N):
    for j in range(0,N):
        if j == i:
            pass
        else:
            check = False
            if A[i] % A[j] == 0:
                check = True
                break
    if check:
        pass
    else:
        count = count + 1


print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
data_A = input()

A = data_A.strip().split()
for i in range(0,N):
    A[i] = int(A[i])

count = 0

for i in range(0,N):
    for j in range(0,N):
        if j == i:
            pass
        else:
            check = False
            if A[i] % A[j] == 0:
                check = True
                if check:
                    break
    if check:
        pass
    else:
        count = count + 1


print(count)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
from copy import deepcopy
def main():
    n, *a = map(int, read().split())
    if n == 2:
        if a[0] == a[1]:
            print(0)
            sys.exit()
        elif max(a) % min(a) == 0:
            print(0)
            sys.exit()
        else:
            print(2)
            sys.exit()
    a.sort()
    notdiv = [True] * n
    for i1, ae in enumerate(a):
        if notdiv[i1]:
            for i2 in range(i1+1, n):
                if notdiv[i2]:
                    notdiv[i2] = a[i2] % ae != 0
    if a[0] == a[1]:
        notdiv[0] = False
    if a[-1] == a[-2]:
        notdiv[-1] = False
    for j1 in range(1, n - 1):
        if a[j1-1] == a[j1] or a[j1] == a[j1+1]:
            notdiv[j1] = False
    r = sum(notdiv)
    print(r)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
if len(A) == 1:
  print(0)
  exit()
  
def quicksort(a):
  if not a or len(set(a)) == 1:
    return a
  pivot = a[0]
  left = []
  center = []
  right = []
  for i in a:
    if i < pivot:
      left.append(i)
    elif i > pivot:
      right.append(i)
    else:
      center.append(i)
  left = quicksort(left)
  right = quicksort(right)
  left.extend(center)
  left.extend(right)
  return left

A = quicksort(A)

count = 0
remain = 1
while remain > 0:
  count += 1
  div = A.pop(0)
  temp = []
  for i in range(len(A)):
    if A[i] % div != 0:
      temp.append(A[i])
  temp.reverse()
  A = temp
  remain = len(A)
print(count)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
from copy import deepcopy
def main():
    n, *a = map(int, read().split())
    if n == 2:
        if a[0] == a[1]:
            print(0)
            sys.exit()
        elif max(a) % min(a) == 0:
            print(0)
            sys.exit()
        else:
            print(2)
            sys.exit()
    a.sort()
    notdiv = [True] * n
    for i1, ae in enumerate(a):
        if notdiv[i1]:
            for i2, ae2 in enumerate(a[i1+1:]):
                if notdiv[i1 + i2 + 1]:
                    notdiv[i1 + i2 + 1] = ae2 % ae != 0
    if a[0] == a[1]:
        notdiv[0] = False
    if a[-1] == a[-2]:
        notdiv[-1] = False
    for j1 in range(1, n - 1):
        if a[j1-1] == a[j1] or a[j1] == a[j1+1]:
            notdiv[j1] = False
    r = sum(notdiv)
    print(r)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())

    a.sort()
    notdiv = [True] * n
    if a[0] == a[1]:
        notdiv[0] = False
    if a[-1] == a[-2]:
        notdiv[-1] = False
    for j1 in range(1, n - 1):
        if a[j1-1] == a[j1] or a[j1] == a[j1+1]:
            notdiv[j1] = False
    for i1, ae in enumerate(a):
        if notdiv[i1]:
            for i2, ae2 in enumerate(a[i1+1:]):
                if notdiv[i1 + i2 + 1]:
                    notdiv[i1 + i2 + 1] = ae2 % ae != 0
    r = sum(notdiv)
    print(r)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#同じものが2つ以上含まれていた場合、それらを除外する
#最小値で割っていき、割り切れるものを除外する
#最小値を除外し、次の最小値で割っていき、割り切れるものを除外する
#最小値が最大値の半分より大きくなるところで探索終了

import numpy as np

N = int(input())

x = np.array(np.uint64(input().split()))
#print(x)

def hantei(list_1, length):
    u, counts = np.unique(list_1, return_counts=True)
    print(u)
    # [ 0 10 20 30]
    print(counts)
    # [2 2 1 1]
    print(u[counts == 1])
    # [20 30]


def hantei_2(list_1, length):
    list_2, counts = np.unique(list_1, return_counts=True)
    list_3 = list_2[counts == 1]
    print(list_3)
    list_4 = list_3
    count_list = []
    for k in range(N):
        min_1 = np.amin(list_4)
        max_1 = np.amax(list_4)
        if min_1 > max_1 / 2:
            count_1 = np.count_nonzero(list_4)
            print(count_1)
            break
        else:
            list_4 = list_4[list_4 % min_1 != 0]
            print(list_4)
            count_list.append(min_1)
            print(count_list)
    count_2 = len(count_list)
    print(count_2)
    count_3 = count_1 + count_2
    print(count_3)


def hantei_3(list_1, length):
    list_2, counts = np.unique(list_1, return_counts=True)
    list_3 = list_2[counts == 1]
    if np.count_nonzero(list_3) == 0:
        return 0
    else:
        #print(list_3)
        list_4 = list_3
        count_list = []
        for k in range(N):
            min_1 = np.amin(list_4)
            max_1 = np.amax(list_4)
            if min_1 > max_1 / 2:
                count_1 = np.count_nonzero(list_4)
                #print(count_1)
                break
            else:
                list_4 = list_4[list_4 % min_1 != 0]
                #print(list_4)
                count_list.append(min_1)
                #print(count_list)
        count_2 = len(count_list)
        #print(count_2)
        count_3 = count_1 + count_2
        return count_3

print(hantei_3(x, N))

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
A=np.sort(A)[::-1]
#print(A)

ans=0 if A[-1]==A[-2] else 1
for i in range(N-1):
    #print(A[i],A[i+1:])
    if np.all(A[i]%A[i+1:]!=0):
        ans+=1
        #print(A[i],A[i+1:])
        
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if a[i+1] == value:
            count -= 1
        count += 1
        j = 1
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1
    #if value ** 2 > aMax:
    #    break

print(count)

Submission status: Runtime Error

Solution code:
n = int(input())

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

aMax = a[-1]
l = len(a)
count = 0

while 1:
    aMin = a.pop(0)
    if aMin == a[0]:
        count -= 1
    count += 1
    l -= 1
    delList = []
    if l == 0:
        break
    for k in a:
        if k % aMin == 0:
            delList.append(k)
    for k in delList:
        a.remove(k)
        l -= 1
    if aMin ** 2 > aMax:
        count += l
        break

print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

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

array = [0 for i in range(2 * (10 ** 5)+1)]
for v in a:
  array[v] += 1
  
if array[1] != 0:
  print(0)
  sys.exit()
  
for i in range(1, len(array)):
  if array[i] == 0:
    continue
    
  for j in range(i*2, len(array), i):
    array[j] = 0
    
count = 0
for v in array:
  if v == 1:
    count += 1
    
print(count)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]==1:
            for item in range(rep,n+1,rep):
                ava[item] == 2

    print(ava.count(1))
    return

if __name__=='__main__':
    n = I()
    a = list(IL())
    a.sort()
    solve()

Submission status: Runtime Error

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

a_max = a[-1]
dp = [1]*a_max

for i in set(a):
    j = 2
    while i*j <= a_max:
        dp[i*j-1] = 0
        j += 1

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

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

a.sort()
tf = [True] * n

for j in range(n):
    if not tf[j]:
        pass
    else:
        for k in range(j+1, n):
            if tf[k] and a[k] % a[j] == 0:
                tf[k] = False
    #print(tf)

if a[0] % a[1] == 0:
    tf[0] = False

print(tf.count(True))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
alsit=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
alist=[0]*200001
for i in range(n):
  for j in range(a[i],200001,a[i]):
    alist[j]+=1
cnt=0
for i in range(n):
  if alist[a[i]]==1:
    cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

def check(a):
  if count[a] > 1:
    return 0

  if 1 in count:
    if a == 1 and count[1] == 1:
      return 1
    return 0

  #print(a)
  ok = True
  sqr_a = 1 + int(a**0.5)
  for s in itertools.chain([2], range(3, sqr_a, 2)):
    if a % s:
      continue
    c = s
    while c < sq_a:
      if a % c == 0 and (c in count or (a//c) in count):
        #print(a, c)
        ok = False
        break
      c *= 2
  return ok
  
ans = 0
for a in A:
  ans += check(a)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

  

def check(a):
  if count[a] > 1:
    return 0

  if 1 in count:
    if a == 1 and count[1] == 1:
      ans += 1
    return 0

  #print(a)
  ok = True
  sq_a = 1 + int(a**0.5)
  for s in itertools.chain([2], range(3, 1+int(a**0.5), 2)):
    c = s
    if a % c:
      continue
    while c < sq_a:
      if a % c == 0 and (c in count or (a//c) in count):
        #print(a, c)
        ok = False
        break
      c *= 2
  return ok
  
ans = 0
for a in A:
  ans += check(a)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort(reverse=True)
ans = 0
for i in range(n):
    not_divisible = True
    for j in range(i+1,n):
        if a_ls[i] % a_ls[j] == 0:
            not_divisible = False
            break
    if not_divisible:
        ans += 1
if a_ls[-2] == a_ls[-1]:
    ans -= 1
print(ans)

Submission status: Runtime Error

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

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

a.sort()

s = 0

for i in range(n):
    j = 0
    while j < i:
        if a[i] % a[j] == 0:
            #print(0, a[i], a[j])
            break
        elif a[j] ** 2 > a[i]:
            s += 1
            #print(1, a[i], a[j])
            break
        j += 1

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

print(s)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
a.sort()
m = a[-1]+1
ans = [0] * m

for i in a:
	ans[i] = 1
for i in set(a):
	for j in range(i*2,m-1,i)
		ans[j] = 0
print(ans.count(1))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
C = [x for x in set(A) if A.count(x) == 1]
A = list(set(A))

MAX_A = 1000000

dp = [0]*MAX_A

for i in A:
  if dp[i] != 1:
    c = i
    while c < MAX_A-i:
      c += i
      dp[c] = 1
  if i > 1000:
    break

c = 0
for i in C:
  c += dp[i]

print(len(C)-c)

Submission status: Runtime Error

Solution code:
M = 10**6
N = int(input())
A = list(map(int, input().split()))


def solve():
    memo = [0] * M
    for a in A:
        i = 1
        while i*a < M:
            memo[i*a] += 1
            i += 1

    count = 0
    for a in A:
        if memo[a] == 1:
            count += 1

    return count

if __name__ == "__main__":
    print(solve())

Submission status: Runtime Error

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


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

  not_divisible = [False]*(10**6)
  prev = 0
  for i in range(N):
    if prev == A[i]:
      not_divisible[A[i]] = False
    else:
      not_divisible[A[i]] = True
    prev = A[i]

  for i in range(N):
    if not_divisible[A[i]]:
      j = A[i] + A[i]
      while j <= A[-1]:
        not_divisible[j] = False
        j += A[i]

  cnt = 0
  for i in range(N):
    if not_divisible[A[i]]:
      cnt += 1

  print(cnt)


if(__name__ == '__main__'):
  main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def S(): return sys.stdin.readline().rstrip().split(' ')
def Ss(): return list(S())
def I(): return _I(Ss())
def Is(): return list(I())
def _I(ss): return map(int, ss) if len(ss) > 1 else int(ss[0])

_ = S()
l = Is()

def sanitize(score, l):
  if not l:
    return score
   
  x, ys = l[0], l[1:]
  s = 1 if not ys or x != ys[0] else 0
  return sanitize(score + s, [y for y in ys if y % x != 0])

print(sanitize(0, sorted(l)))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def S(): return sys.stdin.readline().rstrip().split(' ')
def Ss(): return list(S())
def I(): return _I(Ss())
def Is(): return list(I())
def _I(ss): return map(int, ss) if len(ss) > 1 else int(ss[0])

_ = S()
l = Is()

def sanitize(score, l):
  if not l:
    return score
   
  x, ys = l[0], l[1:]
  s = 1 if x not in ys else 0
  return sanitize(score + s, [y for y in ys if y % x != 0])

print(sanitize(0, sorted(l)))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def S(): return sys.stdin.readline().rstrip().split(' ')
def Ss(): return list(S())
def I(): return _I(Ss())
def Is(): return list(I())
def _I(ss): return map(int, ss) if len(ss) > 1 else int(ss[0])

_ = S()
l = Is()

ans = [0] * 200000
for i in sorted(l):
  x = i
  while x < len(ans):
    ans[x] += 1
    x += i

print(np.sum([1 if ans[i] == 1 else 0 for i in l]))

Submission status: Runtime Error

Solution code:
inf =  1000005
def main():
  N = int(input())
  a = list(map(int, input().split()))
  a.sort()
  flag = [True]*inf
  num = [0]*inf 
  for i in range(N):
    num[a[i]] += 1
    if flag[a[i]*2]:
      j = 2
      while (j*a[i] < inf):
        flag[j*a[i]] = False
        j += 1
  ans = 0
  for i in range(N):
    if flag[a[i]] and num[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()