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: Wrong Answer

Solution code:
def abc170d_not_divisible():
    n = int(input())
    cnt = 0
    a = sorted(list(map(int, input().split())))
    flgs = [True] * (a[-1]+1)
    if n == 1:
        print(0)
        return
    for i in range(n):
        if i != n - 1 and a[i] == a[i + 1]:
            flgs[a[i]] = False
            continue
        for j in range(a[i] * 2, a[-1] + 1, a[i]):
            flgs[j] = False
        if flgs[a[i]]:
            cnt += 1
    print(cnt)


abc170d_not_divisible()

Submission status: Wrong Answer

Solution code:
def abc170d_not_divisible():
    n = int(input())
    cnt = 0
    a = sorted(list(map(int, input().split())), reverse=True)
    if n == 1:
        print(0)
        return
    for i in range(n - 1):
        for j in range(i + 1, n):
            if a[i] % a[j] == 0:
                cnt += 1
                break
    if a[-1] == a[-2]:
        cnt += 1
    print(n - cnt)


abc170d_not_divisible()

Submission status: Wrong Answer

Solution code:
def main():

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

    A = sorted(A)
    Amax = A[-1]
    count = [0 for _ in range(Amax+1)]

    for a in A:
        for i in range(1, Amax//a+1):
            count[i*a] += 1

    ans = 0
    for i in range(N):
        a = A[i]
        if count[a] == 1:
            print(i)
            ans += 1
#    print(count)                                                                                                                                                
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
from bisect import bisect_left


def bisectsearch_left(L,a):
    i=bisect_left(L,a)
    return(i)

N=int(input())
A=list(map(int, input().split()))
S=Counter(A)
T=set(S)
# print(S)
# print(T)
# 篩？
ct=0
L=list(S.keys())
L.sort()
# print(L)

for i in range(len(L)):
    a=L[i]
    if a not in T:
        continue
    T.remove(a)
    if S.get(a)==1:
        ct+=1
    if len(T)==0:
        continue
    tmp=T.copy()
    T=list(T)
    T.sort()
    k=bisectsearch_left(T,a**2-1)
    for j in range(k,len(T)):
        n=T[j]
        if n%a==0:
            tmp.difference_update({n,})
    T=tmp
print(ct)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=list(map(int, input().split()))
S=Counter(A)
T=set(S)
# print(S)
# print(T)
# 篩？
ct=0
L=list(S.keys())
L.sort()
# print(L)

for i in range(len(L)):
    a=L[i]
    if a not in T:
        continue
    T.remove(a)
    if S.get(a)>1:
        continue
    ct+=1
    tmp=T.copy()
    # print(tmp)
    for n in T:
        if n%a==0:
            tmp.remove(n)
    T=tmp
print(ct)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int,input().split()))
i = 0
while True:
    if A[0]==A[-1] and N == len(A):
        A.clear()
        break
    num = A[i]
    j = i+1
    while True:
        if j==len(A):
            break
        print(i,j)
        
        if A[j]%num == 0:
            del A[j]
            j -= 1
        j += 1
        
    i += 1
    if i == len(A):
        break
print(len(A))

Submission status: Wrong Answer

Solution code:
def main():

    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: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
k = a[0]
num = 1
if max(a) == min(a):
    print(0)
else:
    for i in range(1,n):
        if k != a[i]:
            l = 0
            for j in a[:i]:
                if a[i]%j != 0:
                    l += 1
            if l == len(a[:i]):
                num += 1
        j = a[i]
    print(num)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a,reverse=True)
ans=0
for i in range(n-1):
    flag=0
    for j in range(i+1,n):
        if b[i]%b[j]==0:
            flag=1
            break
    if flag==0:
        ans += 1

if b[0]>b[n-1]:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a,reverse=True)
ans=0
for i in range(n-1):
    flag=0
    for j in range(i+1,n):
        if b[i]%b[j]==0:
            flag=1
            break
    if flag==0:
        ans += 1
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = sorted(list(map(int,input().split())))
d = deque([A[0]])

for i in range(len(A)):
    app = 1
    for j in d:
        if(A[i]%j==0):
            app = 0
            break
    if(app == 1):
        d.append(A[i])
        
ans = len(d)
if(N > 1):
    if(A[0]==A[1]):
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
s = [0]*N

for i in range(len(A)):
    if(s[i]==0):
        for j in range(i+1,len(A)):
            if(s[j]==0):
                if(A[j]%A[i]==0):
                    s[j] = 1

ans = 0
for i in s:
    if(i == 0):
        ans += 1
if(N > 1):
    if(A[0]==A[1]):
        ans -= 1
print(ans)

Submission status: Wrong Answer

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

A = A[::-1]
a = A.copy()

ans_list = list()
A_len =len(A)

while A_len != 0:
    for i in range(A_len-1):
        if A[i+1] % A[0]==0:
            a.remove(A[i+1])
    ans_list.append(A[0])
    a.remove(A[0])
    A = a.copy()
    A_len = len(A)
ans = len(ans_list)
print(ans-1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

flag=set(range(N))
for i in range(N-1):
  if i not in flag:continue
  flag2 = list(flag)
  for j in flag2:
    if j<= i: continue
    if j==i+1 and A[j]==A[i]:
      flag.remove(i)
    if A[j]%A[i] == 0:
      flag.remove(j)
      
print(len(flag))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

flag=[1]*(N+1)
flag[0] = 0
for i in range(N-1):
  if flag[i]==0:continue
  for j in range(i+1,N):
    if flag[j]==0:continue
    if A[j]%A[i] == 0:
      flag[j] = 0
      
print(sum(flag))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
m=A[-1]
dp=[True]*m
ans,p,q=0,0,False
for a in A:
  if p==a and q:
    ans-=1
    q=False
  if dp[a-1]:
    q=True
    ans+=1
  aa=a
  while m>=aa:
    dp[aa-1]=False
    aa+=a
  p=a
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
m=A[-1]
dp=[True]*m
ans,p,q=0,0,False
for a in A:
  if p==a and q:
    ans-=1
    q=False
  if dp[a-1]:
    q=True
    ans+=1
    aa=a
    while m>=aa:
      dp[aa-1]=False
      aa+=a
  p=a
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=sorted(list(map(int,input().split())))
m=A[-1]
dp=[True]*m
ans,p=0,0
for a in A:
  if p==a and q:
    ans-=1
    q=False
  if dp[a-1]:
    q=True
    ans+=1
    aa=a
    while m>=aa:
      dp[aa-1]=False
      aa+=a
  p=a
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=sorted(list(map(int,input().split())))
m=A[-1]
dp=[True]*m
ans,p=0,0
for a in A:
  if p==a:
    ans-=1
  if dp[a-1]:
    ans+=1
    aa=a
    while m>=aa:
      dp[aa-1]=False
      aa+=a
    p=a
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=sorted(list(map(int,input().split())))
m=A[-1]
dp=[True]*m
ans=0
for a in A:
  if dp[a-1]:
    ans+=1
    aa=a
    while m>=aa:
      dp[aa-1]=False
      aa+=a
print(ans)

Submission status: Wrong Answer

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

A.sort()

s = {A[0]}

for i in range(1, n):
    Ai = A[i]
    check = True
    for item in s:
        if Ai % item == 0:
            check =False
            break
    if check:
        s.add(Ai)

print(len(s))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
newA = sorted(A)
ans = 0
for k in range(1,N):
  for m in range(k):
    if newA[k] % newA[m] == 0 and newA[k] != newA[m]:
      ans += 1
      break
    else:
      continue
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
newA = sorted(A)
ans = 0
for k in range(1,N):
  for m in range(k):
    if newA[k] % newA[m] != 0:
      continue
    else:
      ans += 1
      break
print(ans)

Submission status: Wrong Answer

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

x=[0]+[True]*10**6

for i in range(len(a)):
  cnt=a[i]
  if x[a[i]]==True and (i==0 or a[i]!=a[i-1]) and (i==(n-1) or a[i]!=a[i+1]):
        ans+=1
        while cnt<=10**6:
          x[cnt]=False
          cnt+=a[i]
          
  elif x[a[i]]==True and (i!=0 and a[i]==a[i-1]) and (i!=(n-1) and a[i]==a[i+1]):
        while cnt<=10**6:
          x[cnt]=False
          cnt+=a[i]
print(ans)

Submission status: Wrong Answer

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

x=[0]+[True]*10**6

for i in range(len(a)):
  cnt=a[i]
  if x[a[i]]==True and (i==0 or a[i]!=a[i-1]) and (i==(n-1) or a[i]!=a[i+1]):
        ans+=1
        while cnt<=10**6:
          x[cnt]=False
          cnt+=a[i]
      
print(ans)

Submission status: Wrong Answer

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

x=[0]+[True]*10**6

for i in range(len(a)):
  cnt=i
  if x[a[i]]==True and (i!=len(a)-1 and a[i+1]!=a[i]) and (i!=0 and a[i]!=a[i-1]):
    ans+=1
    while cnt>10**6:
      x[cnt]=False
      cnt+=i
      
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors #+ upper_divisors[::-1]
print(make_divisors(10000))

Submission status: Wrong Answer

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

#篩
M = 10**6+ 10
c = [0] * M
for i in range(N):
    if c[A[i]] >= 1:
        c[A[i]] = c[A[i]] + 1
    else:
        for j in range(1, M//A[i]):
            c[A[i]*j] += 1

#チェック
ans = 0
for i in range(N):
    if c[A[i]] <= 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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 A:
    if valid[i] == False:
        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-1] == A[i]:
        if i == 1 or A[i-2] != A[i-1]:
            count -= 1
        continue
    if valid[A[i]]:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
#print(A)
s = 0
t = -1

for i in range(N):
    f = 0
    for j in range(i):
        if A[i] % A[j] == 0:
            f = 1
            break
    if f == 0:
        s += 1
        #print(i)
    if A[0] != A[i]:
        t = 0
        
print(s+t)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
nums = []
count = 0

for a in A:
    divided = False
    for num in nums:
        if a % num == 0:
            divided = True
            break
    if not divided:
        nums.append(a)
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
cnt=[0]*(a[-1]+1)
while a:
  m=a.pop(0)
  cnt[m]+=1
  i=0
  while i<len(a):
    if a[i]%m==0:
      a.pop(i)
      continue
    i+=1
ans=0
for ci in cnt:
  ans+=(1 if ci==1 else 0)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
maxA = max(A)
dp = {}
for i in range(1, maxA+1):
    dp[i] = True
for i in range(N):
    if dp[A[i]]:
        tmp = 2 * A[i]
        while maxA >= tmp:
            if dp[tmp]:
                dp[tmp] = False
            tmp += A[i]
counter = 0
for i in range(N):
    if dp[A[i]]:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
each = Counter(A)
A = [x for x in A if each[x] == 1]
A.sort()
for d in A:
    A  = [x for x in A if (x == d or x % d != 0)]

print(len(A))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

each = Counter(A)
A = [x for x in A if each[x] == 1]

for d in A:
    A  = [x for x in A if (x == d or x % d != 0)]

print(len(A))

Submission status: Wrong Answer

Solution code:
def sieve(INF=10**6+1):
  p=[-1]*INF
  for i in a:
    if p[i]==-1:
      p[i]=1
      for j in range(2*i,INF,i):p[j]=0
    elif p[i]==1:
      p[i]=0
  p[0],p[1]=0,0
  return p
n=int(input())
a=sorted(list(map(int,input().split())))
p=sieve()
ans=0
for i in a:
  ans+=p[i]
print(ans)

Submission status: Wrong Answer

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

a.sort()
#print(a)
flag = 0
if a[0] == 1:
    print(1)
    exit(0)
if 2 in a:
    flag = 1
dict = {a[0]:1}
ans = 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: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 1000005
cnt = [0]*M
for a in A:
    if cnt[a]!=0:
        cnt[a]+=1
        continue
        
    for i in range(a, M, a):
        cnt[a]+=1
        
ans = 0
for a in  A:
    if cnt[a] == 1:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

for i1 in range(n):
  for i2 in range(i1, n):
    if i1 != i2 and a[i1] % a[i2] == 0:
      break
    if i2 == len(a) - 1:
      cnt += 1
      
print(cnt)

Submission status: Wrong Answer

Solution code:
# Not Divisible

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

ok = []
A.sort()

while 0 < len(A):
    a0 = A[0]
    if a0 in A[1:]:
        A = list(filter(lambda n: n != a0, A))
        continue
    A = list(filter(lambda n: n % a0 != 0, A))
    ok.append(a0)

print(len(ok))

Submission status: Wrong Answer

Solution code:
# Not Divisible

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

ok = []
A.sort()

while 0 < len(A):
    a0 = A[0]
    if a0 in A[1:]:
        A = list(filter(lambda n: n != a0, A))
        continue
    A = list(filter(lambda n: n % a0 != 0, A))
    ok.append(a0)

print(ok)

Submission status: Wrong Answer

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
A.sort(reverse=True)
for i in range(0,N-1):
    for j in range(N-1,i+1,-1):
        check = False
        if A[i] % A[j] == 0:
            check = True
            break
    if check:
        pass
    else:
        count = count + 1

if A[N-1] == A[N-2]:
    pass
else :
    count = count + 1

print(count)

Submission status: Wrong Answer

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
A.sort(reverse=True)
for i in range(0,N-1):
    for j in range(i+1,N):
        check = False
        if A[i] % A[j] == 0:
            check = True
            break
    if check:
        pass
    else:
        count = count + 1

if A[N-1] == A[N-2]:
    pass
else :
    count = count + 1

print(count)

Submission status: Wrong Answer

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

if a[0] == a[n - 1]: ans = 0
else: ans = 1

for i in range(1, n):
    for j in range(i):
        if a[i] % a[j] == 0:
            break
        if j == i - 1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        a1 = a[i1]
        if TorF[a1]:
            m = a1 // a[-1] + 1
            for i2 in range(2, m):
                TorF[a1 * i2] = 0
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

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

    TorF = [0] * (max(a) + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        if TorF[a[i1]]:
            t = a[i1] * 2
            while t <= max(a):
                TorF[t] = 0
                t += a[i1]
        if a[i1+ 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    TorF = [0] * (max(a) + 1)
    for ae in a:
        TorF[ae] = 1
    for ae in a:
        if TorF[ae]:
            t = ae * 2
            while t <= max(a):
                TorF[t] = 0
                t += ae
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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])
  A = temp
  remain = len(A)
print(count)

Submission status: Wrong Answer

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

    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
    daburi = sum([i for i in Counter(a).values() if i >= 2])
    r = sum(notdiv) - daburi
    r = max(r, 0)
    print(r)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
    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) - (n - len(set(a)))
    r = max(r, 0)
    print(r)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# Not Divisible

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

A.sort()
ok = []

while 0 < len(A):
    div = True
    for i in range(1, len(A)):
        if A[0] == A[i]:
            break
        elif A[i] % A[0] == 0:
            A[i] = 0
    else:
        ok.append(A[0])
    A[0] = 0
    A = list(filter(lambda a: 0 < a, A))

print(len(ok))

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

x = np.array(np.int64(input().split()))
print(x)

def hantei_5(length, list_1):
    list_2 = np.array([True for i in np.arange(N) if np.count_nonzero(
        list_1[i] % list_1 == 0) == 1])
    #print(list_2)
    count = np.count_nonzero(list_2)
    return count

print(hantei_5(N,x))

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

x = np.array(tuple(map(int, input().split())))


def hantei_2(length, list_1):
    count = 0
    list_2 = list_1
    for i in list_1:
        if np.all((i % list_2 != 0) | (i == list_2)):
            count += 1
    return count


print(hantei_2(N,x))

Submission status: Wrong Answer

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

A.sort()

B=[0]*( A[N-1] +1 )

for i in A:
  if(B[i]==0):
    for j in A:
      if(i!=j and j%i==0):
        B[j] += 1


count=0
for i in A:
  if(B[i]==0):
    count +=1


print(count)

Submission status: Wrong Answer

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

A.sort()

B=[0]*( A[N-1] +1 )

for i in A:
  j=2
  if(B[i]==0):
    while( j*i <= max(A) ):
      B[j*i]=1
      j += 1

count=0
for i in A:
  if(B[i]==0):
    count +=1


print(count)

Submission status: Wrong Answer

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
for i in range(N):
    #print(A[i],A[i+1:])
    if np.any([i]%A[i+1:]==0):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = 0
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != 1)
print(1 if n == 1 else cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = 0
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != i)
print(0 if n == 1 else cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = 0
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != 1)
print(0 if n == 1 else cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = n == 1
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != i)
print(cnt)