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: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
seq=LI()
c=Counter(seq)
seq=list(set(seq))
seq.sort()
lis=[seq[0]]
for i in range(1,len(seq)):
    count=0
    for x in lis:
        if seq[i]%x!=0:
            count+=1
    if count==len(lis):
        lis.append(seq[i])
#print(lis)
ans=len(lis)
for x in lis:
    if c[x]>1:
        ans-=1
print(ans)

Submission status: Time Limit Exceeded

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

iter = 0

for i in a:
  lst = [i%j for j in a]

  if lst.count(0) == 1:
    iter = iter + 1

print(iter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = []
count = 0
for i in range(N):
  C = [(A[i] % A[j]) for j in range(N)]
  B.append(C)
for i in range(N):
  cnt = B[i].count(0)
  if cnt == 1:
    count +=1
  
print(count)

Submission status: Time Limit Exceeded

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


X=set()
d=set()
for i in A:
    if i in X:
        d.add(i)
    X.add(i)

ans = 0

for a in A:

    exist = False 
    X.remove(a)

    for i in range(1, int(-(-a**0.5//1))+1):
        if a%i == 0:
            if i in d or i in X:
                exist = True
                break
            if a//i in d or a//i in X:
                exist = True
                break

    if not exist:
        ans += 1
    X.add(a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    input()
    integars = sorted(int(x) for x in input().split())
    ans = 0
    for i, x in enumerate(integars):
        chosen = True
        for j, y in enumerate(integars):
            if i == j:
                continue
            elif x % y == 0:
                chosen = False
                break
            elif i < j:
                break
        if chosen:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
asor = sorted(a)
numlist = []
cnt = 0
while True:
    if asor == []:
        break
    if len(asor) ==1:
        cnt +=1
        break
    cnt +=1
    num = asor[0]
    numlist = []
    if asor[1] == num:
        cnt-=1
    for i in range (len(asor)):
        if asor[i]%num == 0:
            numlist.append(asor[i])
    asor = list(filter(lambda x: x not in numlist, asor))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
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]
n = int(input())
a=list(map(int,input().split()))
a=sorted(a)
c=Counter(a)
x=set()
for i in range(n):
    x.add(a[i])
ans = 0
for i in x:
    if c[i]>1:
        continue
    l=make_divisors(i)
    x.remove(i)
    f=1
    for r in l:
        if r in x:
            f=0
            break
    if f:
        ans += 1
    x.add(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
count = 0
han = [0]*N
for i in range(N):
    for j in range(i+1,N):
        if A[i] == A[j]:
            han[i]+=1
        if han[j] == 0:
            if A[j]%A[i] == 0:
                han[j]+=1

for i in han:
    if i == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=0
for i in range(len(a)):
  for j in range(len(a)):
    d=0
    if i==n-1-j:
      continue
    elif a[i]%a[n-1-j]==0:
      d+=1
      break
  if d==0:
     c+=1
print(c)

Submission status: Time Limit Exceeded

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

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

a.sort()

b = []
ans = 0

for i in range(n):
  if a[i] == a[i-1]:
    continue
  j = 0
  flag = True
  while j < len(b) and b[j] * 2 <= a[i]:
    if a[i] % b[j] == 0:
      flag = False
      break
    else:
      j += 1
  if flag:
    b.append(a[i])
    if i == n-1 or a[i] != a[i+1]:
      ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    score = 0
    for j in range(n):
        if i != j:
            if a[i]%a[j] == 0: #divisible 
                break;
            else: # not divisible
                score += 1
    if score == n-1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve(i,j,a):
    k=False
    sc=0
    pl=[]
    for v in [2,3,5,7,11,13,17,19]:
        if j%v==0:
            break
    v=j//v
    if a.count(j)>=2:
        k=True
    else:
        for c in a:
            if c>v:
                break
            elif c==j:
                sc+=1
                if sc>=2:
                    k=True
                    break
            else:
                if j%c==0:
                    k=True
                    break
    return k

n=int(input())
a=sorted(list(map(int,input().split())))
ans=0
for i,j in enumerate(a):
    if solve(i,j,a):
        continue
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

    A.sort()
    ans = 0
    temp = 0
    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

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

        temp = A[i]

        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue

        for j in range(N):
            if A[j] <= temp/2 and A[i]%A[j] == 0:
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print(main())

Submission status: Time Limit Exceeded

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

a.sort()

ans = 0

for x in a[:]:
  if a.count(x) == 1:
    ans += 1
  for y in a[:]:
    if y%x == 0:
      a.remove(y)

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
while a:
    st = 0
    if len(a)>1 and a[0] == a[1]:
        st = 1
    else:
        st = 0
        ans += 1
    a = [a[i] for i in range(st, len(a)) if a[i] % a[0] > 0]
print(ans)

Submission status: Time Limit Exceeded

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

res = 0
for i in range(n):
    for j in range(n):
        if  i == j:
           pass
        elif (a[i] == a[j]) or (a[i]%a[j] == 0):
            break
    else:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
  
ans = 0
for a in A:
  d_list = divisor(a)
  tmp = copy.copy(A)
  tmp.remove(a)
  if len(set(d_list) & set(tmp)) == 0:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        continue
    for j in range(i+1,n):
        if done[j] != 1:
            if li[j]==li[i]:
                done[i]=1
                done[j]=1
                dp[i]=0
                dp[j]=0
            elif li[j]%li[i]==0:
                done[j]=1
                dp[j]=0
 
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
seq=LI()
c=Counter(seq)
seq=list(set(seq))
seq.sort()
lis=[seq[0]]
for i in range(1,len(seq)):
    count=0
    for x in lis:
        if seq[i]%x!=0:
            count+=1
    if count==len(lis):
        lis.append(seq[i])
#print(lis)
ans=len(lis)
for x in lis:
    if c[x]>1:
        ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3
# coding: utf-8
n = int(input())
ha = input()
kita = ha.split(" ")
count = 0
for i in range(n):
    ifC = True
    for j in range(n):
        if(i != j):
            a = int(kita[i])
            b = int(kita[j])
            if(a%b == 0):
                ifC = False
    if(ifC):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
_n = int(input())
_a = list(map(int, input().split(" ")))
_a.sort()
_counter = 0

for _i in range(_n):
  for _j in range(_n):
    if _i != _j and _a[_i] % _a[_j] == 0:
      break
    elif _j == _n - 1:
      _counter += 1
print(_counter)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    #rootA=math.sqrt(ListA[i])

    for j in range(i):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>ListA[i]/2):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

nums=[int(s) for s in input().split()]

nums.sort()

for i,n in enumerate(nums):
  ls=[]
  for j in range(len(nums)-i-1):
    if nums[i+j+1] % nums[i]==0:
      ls.append(i+j+1)
  ls.reverse()
  c=0
  for s in ls:
    if nums[s]==nums[i]:
      c+=1
      break
  if c==0:
    for j in ls:
      del nums[j]
  else:
    for j in ls:
      del nums[j]
    del nums[i]
print(len(nums))

Submission status: Time Limit Exceeded

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

flag=[0]*n

for i in range(len(l)):
    for j in range(len(l)):
        if i==j:
            continue
        elif flag[i]==1:
            continue
        elif l[i]%l[j]==0:
            flag[i]=1
            break
print(flag.count(0))

Submission status: Time Limit Exceeded

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=[]

icnt=0
while True:
    aa.append(a[0])
    a2=[]
    for i in range(1,len(a)):
        if a[i]%a[0]!=0:
            a2.append(a[i])
    a=a2.copy()
#    print(aa,a)     
    if len(a2)==0:
        break
    icnt+=1
#    if icnt>10:break

aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0

out = set()
for i in range(N):
    if A[i] in out:
        continue
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            out.add(A[i])
            break

for a in A:
    if a not in out:
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

for i in range (0,N):
  res=0
  for j in range(0,N):
    if(i!=j and list[i] % list[j]==0):
      res+=1
      break
  if(res!=0):
    ans+=1

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    import numpy as np
    N = int(input())
    A = np.array(list(map(int, input().split())))

    #output
    answer = 0
    for a in A:
        if N - np.count_nonzero(a % A) > 1:
            answer += 1
    answer = N - answer
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans_set=set(a)

i=0
while(i<len(a)):
    if(a[i] in ans_set):
        j=i+1
        while(j<len(a)):
            if(a[j] in ans_set and a[j]%a[i]==0):
                ans_set.remove(a[j])
                del a[j]
                j-=1
            j+=1
    i+=1
#print(ans_set)
print(len(ans_set))

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
@jit(cache=True)
def kkk(al):
	k=0
	for i in range(n):
		f=0
		for j in range(n):
			if i!=j and al[i]%al[j]==0:
				f=1
				break
		if f==0:
			k=k+1
	return(k)
        
n=int(input())
a=input()
a0=a.split()
al=list(map(int,a0))

print(kkk(al))

Submission status: Time Limit Exceeded

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

als = sorted(al)
m = als[-1]

from collections import Counter
c = Counter(als)


res = 0
kouho =[]
for i in range(n):
    flg = 0
    j = als[i]
    if c[j] >1:
        kouho.append(j)
        pass
    else:
        for k in kouho:
            if j % k ==0:
                flg = 1
                break
        if flg != 1:
            res += 1
            kouho.append(j)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    a2=set(a)
    a2=list(sorted(a2))
    if a2[0]==1:
        if a.count(1)==1:
            ans=1
        else:
            ans=0
    else:
        def c1(num1):
            return a.count(num1)
        for i in range(len(a2)):
            num=0
            if c1(a2[i])==1:
                for j in range(i):
                    if a2[i]%a2[j]==0:
                        num=1
                        break
                    if a2[i]/2+1<a2[j]:
                        break
                if num==0:
                    ans+=1
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
def LI():
    return list(map(int, input().split()))

n = int(input())
a = LI()

a.sort()
cnt = 0
for i in range(n):
    for j in range(i):
        if a[i] % a[j] == 0:
            break
    else:
        if i == n-1 or a[i+1] != a[i]:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    yn = [0]*(10**6+1)
    for i in a:
        yn[i] += 1

    def yakusu(n):
        if n == 1:
            return []
        ys = [1]
        ni = 2
        while ni**2 <= n:
            if n%ni == 0:
                ys.append(ni)
                ys.append(n//ni)
            ni += 1
        return ys
    ans = 0
    for i in a:
        f = True
        if yn[i] != 1:
            continue
        for j in yakusu(i):
            if yn[j]:
                f = False
                break
        if f:
            ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [int(s) for s in input().rstrip().split()]

count = 0

def explore(i):
  n_i = nums[i]
  for j in range(N):
    if j != i:
      n_j = nums[j]
      if n_j == n_i:
        return 0
      if n_j <= n_i // 2:
        if n_i % n_j == 0:
          return 0
  return 1

for i in range(N):
  count += explore(i)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
if len(A) == 1:
    print(1)
else:
    lst = []
    ans = 0
    for i in range(len(s)):
        # m = int(s[i]**0.5)+1
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            # elif m < p:
            #     break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.5))
    J = min(idx+1,i)
    J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
if N==1:
    print(1)
    exit()
 
A.sort()
ans=0
 
if A[0]!=A[1]:
    ans=1
 
if A[0]==1 and A[1]==1:
    print(0)
    exit()
 
elif A[0]==1 and A[1]!=1:
    print(1)
    exit()
 
for i in range(1,N):
    now = A[i]
    if now==A[i-1] or ((i!=N-1) and (now==A[i+1])):            
        continue
    for j in range(i):
        comp=A[j]
        if now%comp==0:
            break
        elif j==i-1 or now<comp*2:
            ans+=1
            break
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


def main():
    ans = 0
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        b = 0
        for j in range(n):
            if j == i:
                b += 1
            else:
                if a[i] % a[j] == 0:
                    break
                else:
                    b += 1
        if b == n:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
n = int(input())
As = np.array([int(i) for i in input().split()])
As.sort()
# print(As)

# As に1があったら、1だけ
# if As[0] == 1:
#     if 1 in As[1:]
#     print(1)
#     sys.exit()

index = -1
while index + 1 < len(As): #リストの最後までループ
    index += 1# As[index] が割り切れなかったやつ
    As_index = As[index]
    # print(As_index)
    delete_list = []

    #自分自身があれば、削除
    self_deleted = False
    if index + 1 <  len(As):
        if As_index == As[index + 1]:
            # print(As)
            delete_list.append(index)
            self_deleted = True
            

    for i in range(len(As)): # As[index] で割り切れたやつを削除
        if i == index : #　同じならとばす
            continue

        if As[i] % As_index == 0:
            delete_list.append(i)
    # print(As)
    As = np.delete(As, delete_list)

    if self_deleted:
        index -= 1

# print(As)
print(len(As))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [True] * len(A)

for i in range(len(A)-1):
    a = A[i]
    if A[i+1] == a:
        B[i] = False
    for j in range(i+1, len(A)):
        if B[j] == True:
            if A[j] % a == 0:
                B[j] = False

print(sum(B))

Submission status: Time Limit Exceeded

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

cnt=0

for k in range(n):
    for i in range(1,n):
        
        if a[k]%a[k+i]==0:
            if a[k] in A:
                
                A.remove(a[k])
            
        
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(y) for y in input().split()]
a.sort()

cnt = 0

while N > 0:
    flag = True
    b = []
    res = a[0]

    for i in range(1, N):
        if a[i] == res and flag:
            cnt -= 1
            flag = False
        if a[i] % res != 0:
            b.append(a[i])
    
    a = b
    N = len(a)
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

if n == 1:
  print(1)
else:
  i = 0
  ans = 0
  for _ in range(n):
    count = 1
    for j in range(i):
      if a_list[i] % a_list[j] == 0:
        del a_list[i]
        i -= 1
        count = 0
        break
    if count == 1:
      if i == len(a_list)-1:
        ans += 1
      elif a_list[i] != a_list[i+1]:
        ans += 1
    i += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split(' ')]
# print(A)

count = 0

for j in range(len(A)):
    a = A.pop(j)
    # print(a)
    # print(A)
    
    for i in A:
        if a % i == 0:
            break
    else:
        count += 1
        # print("count:", count)
    A.insert(j, a)
    # print(A)
    # print("=" * 20)
print(count)

Submission status: Time Limit Exceeded

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    one_cnt = 0
    need_check = True
    for i in range(n):
        i_value = a_list[i]

        if need_check:
            if i_value == 1:
                one_cnt += 1
                if 2 <= one_cnt:
                    print(0)
                    return
            elif one_cnt == 1:
                print(1)
                return
            else:
                need_check = False

        fail = False
        for j in range(0, min(i + 2, n)):
            if i == j:
                continue
            j_value = a_list[j]
            mod = i_value % j_value
            if mod == 0:
                fail = True
                break
        if not fail:
            count += 1

    print(count)


if __name__ == "__main__":
    n_a = int(input())
    a_list_a = list(map(int, input().split()))
    _main(n_a, a_list_a)

Submission status: Time Limit Exceeded

Solution code:
# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for i in range(N):
    tmp = set()
    if count[A[i]] >= 2:
        ans += 1
        happend.add(A[i])
        continue
    for j in range(1, int(A[i]**(1/2))+2):
        if A[i] % j == 0:
            tmp.add(j)
            tmp.add(A[i]//j)

    if len(tmp.intersection(happend)) >= 1 or count[A[i]] >= 2:
        ans += 1
    happend.add(A[i])

print(N-ans)

Submission status: Time Limit Exceeded

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

alist.sort()

i = 0
count = 0

while i < len(alist):
  a = alist[i]
  j = i + 1

  if alist.count(alist[i]) >= 2:
    count += 1
    
  while j < len(alist):
    if alist[j] % a == 0:
      del alist[j]
    else:
      j += 1
   
  i += 1
  
print(len(alist) - count)

Submission status: Time Limit Exceeded

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

count = 0
for i,Ai in enumerate(A):
  for j,Aj in enumerate(A):
    if i == j:
      pass
    elif Ai%Aj==0:
      count+=1
      break
print (N-count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

if __name__ == '__main__':
    n = int(input().strip())
    a = np.array(input().strip().split()).astype(int)
    bool_mat = []
    ans = 0

    for i in a:
        bool_mat.append(a % i == np.zeros(n))

    np.sum(bool_mat)
    for i in np.sum(bool_mat, axis=0):
        if i == 1:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted(map(int, input().split()), reverse=True)
b = 0
#print(A)
for i in range(n):
  if i != 0:
    if A[i] == A[i-1]:
      continue
#  j = i+1
  if i == n-1:
    b += 1
    continue
  j = n-1
  while j > i:
    if A[i]%A[j] == 0:
      break
    if j == i+1:
      b += 1
    j -= 1
print(b)

Submission status: Time Limit Exceeded

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

A.sort()
cnt = 0
flag = -1
for i in range(N):
    flag = -1
    for j in range(N):
        if i != (N-j-1):
            if A[i] % A[N-j-1] == 0:
                flag = 0
                break
    if flag == -1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
from math import gcd
from collections import Counter,defaultdict
n = int(input())
a = list(map(int,input().split()))
s = Counter(a)
a = sorted(s)
if s[1]==2:
    ans = 0
elif s[1]==1:
    ans = 1
else:
    ans = 0
    for i in range(len(a)):
        if s[a[i]]>1:
            continue
        for j in range(i):
            if a[i]%a[j]==0:
                break
        else:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            break
    else:
        if A.count(A[i]) <= 1:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = sorted([int(i) for i in input().split()])
A = np.array(A)

ans = 0
while len(A) > 0:
    if len(A) == 1:
        ans += 1
    elif A[0] != A[1]:
        ans += 1
    n = A[0]
    A = A[np.where(A % n != 0)[0]]
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
for i in li:
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
i = 0
ans = 0  
while i <= n-1:
    for j in range(n):
        if i != j and A[i] % A[j] == 0:
            break
        elif j == n - 1:
            ans = ans + 1
    i = i + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit


n = int(input())
a = np.array(list(map(int, input().split())))
ans = 0

@njit
def check(ans):
  for i in range(n):
    temp = a[i]
    count = np.count_nonzero(temp%a==0)
    if count == 1:
      ans += 1
  return ans

ans = check(ans)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
a.sort()
max_a=a[n-1]
#a_table=[True for i in range(n)]
while len(a) > 0:
    min_a=a[0]
    if a.count(min_a)==1:
        cnt+=1
    for k in range(1,max_a//min_a+1):
        a=[ele for ele in a if ele != min_a*k]
    #print(a)
print(cnt)