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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and ((nm < n-2 and a[nm+2] != i) or nm == n-2):
    ans += 1
  s.add(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = sorted([ int(i) for i in input().strip().split(' ')])
n = [ i for i in range(N) ]
B = [0] * N

for i in range(N):
    if B[i] != 0:
        continue
    n.remove(i)
    for j in copy.copy(n):
        if A[i] == A[j]:
            B[i] = 1
            B[j] = 1
            n.remove(j)
        elif A[j] % A[i] == 0:
            B[j] = 1
            n.remove(j)

print(N - sum(B))

Submission status: Time Limit Exceeded

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

A.sort()
prime = []

while A:
  p = A[0]
  if p > max(A)//2:
    break
  if len(A) >= 2 and A[0] == A[1]:
    A = [e for e in A if e % p != 0]
  else:
    prime.append(p)
    A = [e for e in A if e % p != 0]

de = []
for i in range(len(A)-1):
  if A[i] == A[i+1]:
    de.append(A[i])
de = de + list(set(de))
for j in de:
  A.remove(j)


print(len(prime)+len(A))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=sorted([int(x) for x in input().split()])

cnt=0
check=0
for i in range(10**9):
    cnt+=1
    l=len(A)
    if l>=1:
        if l>=2:
            if A[0]==A[1]:
                check+=1
        A=[A[i] for i in range(len(A)) if not A[i] % A[0] == 0]
    elif l==0:
        print(cnt-check-1)
        exit()

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):
  a = 0
  if i<N-1:
    if A[i] == A[i+1]:
      a = 1
    else:
      for j in range(i):
        if A[i] % A[j] == 0:
          a = 1
  else:
    for j in range(i):
      if A[i] % A[j] == 0:
        a = 1
  if a == 0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a_cnt = Counter(a)

a = sorted(list(set(a)))
n = len(a)

ans = 0
memo = set()
for i in range(n):
    flg = True
    if a_cnt[a[i]] == 1:
        for x in range(1, int(a[i] ** 0.5) + 1):
            if a[i] % x == 0:
                if x in memo:
                    flg = False
                    break

                if a[i] // x in memo:
                    flg = False
                    break
        
        if flg:
            ans += 1
    memo.add(a[i])
print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for Ai in A:
  flag = 0
  double = 0
  for Aj in sortedA:
    if Aj > Ai:
      break
    if Ai == Aj:
      double += 1
      continue
    if (Ai % Aj) == 0:
      flag = 1
      break
  if flag == 0 and double < 2:
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

s = set()
for a in A:
  for si in s:
    if a%si==0:
      break
  else:
    s.add(a)
      
ans = 0
C = Counter(A)
for si in s:
  if C[si]==1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    ans=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:
    #             ans+=1

    for i,a in enumerate(A):
        a_set=set(make_divisors(a))
        if a_set.isdisjoint(set(A[:i])|set(A[i+1:])):
            ans+=1

    print(ans)

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]

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

A = int(stdin.readline())
B = list(map(int,stdin.readline().split()))

count=0
T=0
Q=0

if B.count(1)>0:
    if B.count(1)>1:
        print(0)
    elif B.count(1)==1:
        print(1)
    B=[]
    T=1

while len(B)>0:
    if len(B)==1:
        if Q==0:
           count+=1
        break
    K=min(B)

    B.remove(K)

    Q=0
    D=B.copy()
    for t in D:

        if t==K:
            Q=1
        if t%K==0:
            B.remove(t)

    if Q==0:
       count+=1

if T==0:
   print(count)

Submission status: Time Limit Exceeded

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

count = set()

for i in asetlist:
  if alist.count(i) >= 2:
    count.add(i)

i = 0

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

  while j < len(asetlist):
    if asetlist[j] % a == 0:
      del asetlist[j]
    else:
      j += 1

  i += 1

print(len(set(asetlist) - count))

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:
        if i < n/5:
          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 = list(map(int, input().split(' ')))
count = 0
for i in range(N):
    flag = True
    for j in range(N):
        if i != j and A[i]%A[j] == 0:
            flag = False
            continue
    if flag: count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))
def prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:return False
    return True


n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    l.sort()
    c=Counter(l)
    ans=0
    for k,v in c.items():
        if v>1:continue
        elif prime(k)==True:ans+=1
        else:
            f=True
            for i in range(l.index(k)):
                if k%l[i]==0:
                    f=False
                    break
            if f==True:ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
x=[0]*len(a)

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if a[i]%a[j]==0:
      x[i]+=1
      continue
print(x.count(0))

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 val in A:
    if count[val] >= 2:
        ans += 1
        happend.add(val)
        continue
    for j in range(1, int(val**(1/2))+2):
        if val % j == 0:
            if j in happend or val//j in happend:
                ans += 1
                break
    happend.add(val)

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
S=[]
S.append( [A[0],0] )
for a in A[1:]:
  flag=0
  for s in S:
    if a%s[0]==0:
      if s[0]==a: s[1]+=1
      flag=1
      break
  if flag==0:
    S.append( [a,0] )

ans=0
for s in S:
  if s[1]==0:
    ans+=1
#print(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7
    n = int(input())
    a = [int(x) for x in input().split()]
    a_set = set(a)
    #約数の列挙
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)

        divisors.sort()
        return divisors
    from collections import Counter
    c = Counter(a)
    cnt = 0
    for i in a:
        prime = make_divisors(i)
        flag = 1
        if c[i] > 1:
            continue
        for j in prime:
            if j == i:
                continue
            if j in a_set:
                flag = 0
                break
        if flag:
            cnt += 1
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import copy
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

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

if 1 in A:
    if A.count(1) == 1:
        print(1)
    else:
        print(0)
    exit()

ret = 0

D = collections.Counter(A)
D2 = copy.copy(D)


for k, v in D2.items():
    if v != 1:
        D.pop(k)
    elif is_prime(k):
        D.pop(k)
        ret += 1



A = list(set(A))

for a in D.keys():
    f = make_divisors(a)
    flag = True
    for f2 in f[2:]:
        if D2[f2] == 0: continue
        else: flag = False
    if flag: ret += 1


print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
A = sorted(A)
 
zyuhuku = [x for x in set(A) if A.count(x) > 1]
 
for i in range(len(A)):
  for j in range(i+1,len(A)):
    if A[j] != 0 and A[i] != 0:
      A[j] = 0 if A[j] % A[i] == 0 else A[j]
 
print(len([i for i in A if (i > 0) and (i not in zyuhuku)]))

Submission status: Time Limit Exceeded

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

a.sort()
if a[0] == 1:
    if len(a) == 1 or a[1] != 1:
        print(1)
    else:
        print(0)
else:
    a += [-1]
    ret = 0
    d_lst = []
    add = 1
    for i in range(n):
        if a[i] != a[i+1]:
            for d in d_lst:
                if a[i] % d == 0:
                    break
            else:
                ret += add
                d_lst.append(a[i])
                add = 1
        else:
            add = 0
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
ans=0
List=[]
ans+=1
flag=0
List.append(a[0])

for i in range(1,n):
    m=len(List)
    for j in range(m):
        if (a[i]==List[-1]):
            if (flag==0):
                ans-=1
            flag=1
            break
        elif (a[i]%List[j]==0):
            flag=0
            break
        elif (a[i]/List[j]<2):
            List.append(a[i])
            flag=0
            ans+=1
            break
        elif(j==m-1):
            List.append(a[i])
            flag=0
            ans+=1
            break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alis = list(map(int, input().split()))
Alis.sort()
Alis = [a for a in Alis if Alis.count(a) == 1]
for a in Alis:
    if Alis.count(a) > 1:
        Alis.remove(a)
ans = 0
while Alis:
    ans += 1
    lis2 = []
    for j in range(1, len(Alis)):
        if Alis[j] % Alis[0]:
            lis2.append(Alis[j])
    Alis = lis2

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):
    RemA = [ A[i]%j for j in A]
    R = RemA[:i] + RemA[i+1:]
    if (not 0 in R): #自身を除く内に割り切れるものがあるか
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
same = 0
l_list = []
i = 0
while n > i:
    if i < n-1 and a[i] == a[i+1]:
        l_list.append(a[i])
        same += 1
        i += 1
    else:
        flag = 0
        for l in l_list:
            if a[i] % l == 0:
                flag = 1
        if flag == 0:
            l_list.append(a[i])
    i += 1

print(len(l_list)-same)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = []
    count = 0
    for i in range(n):
        t = a[i]
        if i+1 < n and t == a[i+1]:
            if len(pool) == 0 or pool[-1] != t:
                pool.append(t)
            continue
        limit = t // 2
        is_ok = True
        for j in pool:
            if j > limit:
                if len(pool) == 0 or pool[-1] == t:
                    is_ok = False
                break
            elif t % j == 0:
                is_ok = False
                #print("bad", t, j)
                break
        if is_ok:
            #print("good", t)
            pool.append(t)
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def loop(N,A):
    res = 0
    for i in range(N):
        now = A[i]
        for j in range(N):
            if j == i:
                continue
            if now % A[j] == 0:
                res -= 1
                break
        res += 1
    return res


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

    A = np.array(A)

    res = loop(N,A)

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import heapq

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

def heapsort(iterable):
  h = []
  for value in iterable:
    heapq.heappush(h, value)
  l = []
  for _ in range(len(h)):
    l.append(heapq.heappop(h))
  return l

n = ri()
li = rl()
dic = collections.Counter(li)
li1 = []
li2 = []
for k, v in dic.items():
    if v > 1:
        li1.append(k)
    else:
        li2.append(k)
li1 = heapsort(li1)
li2 = heapsort(li2)
le1 = len(li1)
le2 = len(li2)
cnt = 0
for i in range(le2):
    li2i = li2[i]
    for j in range(i):
        if li2i % li2[j] == 0:
            break
    else:
        for k in range(le1):
            li1k = li1[k]
            if li1k > li2i**0.5:
                cnt += 1
                break
            if li2i % li1k == 0:
                break
        else:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = list(map(int, input().split()))
count = 0

for i in range(n):
    flag = True
    for j in range(n):
        #print(i,j)
        
        if i == j:
            continue

        tmp = a[i]%a[j]
        #print(tmp)
        
        if tmp == 0:
            flag = False
            break
    if flag == True:
        count += 1
    
    flag = True

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

count = 0
ans_count = 0
for i in range(x):
    for j in range(x):
        if i == j:
            continue
        if a[i] % a[j] != 0:
            count += 1
            #print(count)
    if count == x - 1:
        ans_count += 1
    count = 0
print(ans_count)
#print(a)

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:
def binarySearch(arr,x,l,r):
    if(r>=l):
        mid=(l+r)//2
        if(x==arr[mid]):
            return mid
        elif(x>arr[mid]):
            return binarySearch(arr,x,mid+1,r)
        else:
            return binarySearch(arr,x,l,mid-1)
    return -1
def factors(x):
    result = []
    i = 1
    while i*i <= x:
        if x % i == 0:
            result.append(i)
            if x//i != i:
                result.append(x//i)
        i += 1
    return result
def countFun(x,arr):
    cou = 0
    for i in arr:
        if i==x:
            cou+=1
    return cou
count = 0
n = int(input())
res = list(map(int,input().split()))
lis = list(set(res))
lis = sorted(lis)
for i in lis:
    temp = factors(i)
    temp.remove(i)
    flag = 1
    for j in temp:
        if(binarySearch(lis,j,0,len(lis)-1)!=-1):
            flag=0
    if(flag and countFun(i,res)==1):
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(n):
    #ll += 1
    #print(i)
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
for i in A:
    dic[i] += 1
cnt = 0
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter


n = int(input())
a = [int(x) for x in input().split(' ')]

s = np.array(sorted(set(a)),int)
i = 1
while i < len(s)-1:
    s = np.concatenate([s[:i], s[i:][s[i:]%s[i-1]!=0]],0)
    i += 1
s = set(s)

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

print(len(s&keys))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
L = list(map(int,input().split()))
count = 0

for n in np.array(range(N)):
    l = L[n]
    L_s = L.copy()
    L_s.pop(n)
    for l_s in L_s:
        if l%l_s == 0:
            break
    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp
n = int(input())
a = list(map(int, input().split()))
hp.heapify(a)
ans = 0
while len(a) > 0:
    b = hp.heappop(a)
    if b in a:
         ans += -1
    a = [i for i in a if i % b != 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:
            continue
        if li[j]%li[i]==0:
            done[j]=1
            dp[j]=0
        if li[j]==li[i]:
            done[i]=1
            dp[i]=0
            
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
import copy
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()))
# gcd_table = defaultdict(int)
ans = 0
# for num in a:
#     table = make_divisors(num)
#     for i in table:
#         gcd_table[i] += 1
times = defaultdict(int)
for i in a:
    times[i] += 1
for j in a:
    if times[j] > 1:
        continue
    # tmp = gcd_table.copy()
    tmp = set(a)
    tmp.remove(j)
    table_ = make_divisors(j)
    for i in table_:
        if i in tmp:
            break
    else:
        ans += 1
    # table_ = table_[1:]
    # for k in table_:
    #     tmp[k] -= 1
    # print(tmp)
    # for l in table_:
    #     if l in tmp:
    #         if tmp[l] > 0:
    #             break
    # else:
    #     print(j)
    #     ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

N = int(input())
A = list(input().split())
A = sorted([int(A[i]) for i in range(N)])
A_count = Counter(A)
count = 0

for i in reversed(range(N)):
    tmp = A[i]
    for j in range(N):
        if A[j] > (tmp // 2) and A_count[tmp] == 1:
            count += 1
            break
        elif tmp % A[j] == 0:
            break

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
dic = defaultdict(int)
for a in A:
  dic[a] += 1

A = list(set(A))
A.sort()
B = []
ans = 0
for a in A:
  flag = True
  for b in B:
    if a % b == 0:
      flag = False
      break

  if flag:
    B += [a]
    if dic[a] == 1:
      ans += 1

print(ans)
      

"""E問題"""

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    # 約数
    N = ir()
    A = lr()
    A.sort()
    answer = 0
    bl = [0] * (A[-1]+1)

    def make_divisors(n):  # nの約数を列挙
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        divisors.sort()
        return divisors

    for i, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = 1
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x] == 1:
                flag = False
                break
        bl[a] = 1
        if flag:
            answer += 1

    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def make_divisors(n):
    lower_divisors, upper_divisors = set(), set()
    tmp = 1
    while tmp * tmp <= n:
        if n % tmp == 0:
            lower_divisors.add(tmp)
            if tmp != n // tmp:
                upper_divisors.add(n // tmp)
        tmp += 1
    return lower_divisors | upper_divisors


n = int(input())
*A, = map(int, input().split())
A.sort()
cnt = 0
for i, a in enumerate(A):
    if bisect.bisect_right(A, a) - bisect.bisect_left(A, a) != 1:
        cnt += 1
        continue
    X = make_divisors(a)
    for x in X:
        if x != a and bisect.bisect_right(
                A, x) - bisect.bisect_left(A, x) != 0:
            cnt += 1
            break
print(n - cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    for j in range(N):
        if(i!=j and A[i]%A[j]==0):
            B.append(i)
B=list(set(B))
print(N-len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split(' ')))
count = 0
for i in range(N):
    flag = True
    for j in range(N):
        if i != j and A[i]%A[j] == 0: flag = False
    if flag: count += 1

print(count)

Submission status: Time Limit Exceeded

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

A.sort()
prime = []

de = []
for i in range(len(A)-1):
  if A[i] == A[i+1]:
    de.append(A[i])
de = de + list(set(de))
for j in de:
  A.remove(j)

while A:
  p = A[0]
  if p > max(A)//2:
    break
  prime.append(p)
  A = [e for e in A if e % p != 0]


print(len(prime)+len(A))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
A = Counter(list(map(int, input().split())))
A_keys = list(A.keys())
A_keys.sort()
for key in A_keys:
    if A[key] == 0:
        continue
    for x in A_keys:
        if x != key and x % key == 0:
            A[x] = 0
ans = 0
for key in A_keys:
    if A[key] > 1 or A[key] == 0:
        continue
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    flag=True
    for j in range(n):
        if(((a[i]%a[j]) == 0) and (i != j)):
            flag=False
    if(flag == True):
        x += 1
print(x)

Submission status: Time Limit Exceeded

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

B = [1 for _ in range(n)]

for i in range(n):
  if A[i]*2 > A[n-1] and A[i] <= A[n-1]:
    if i < n-1 and A[i] == A[i+1]:
      B[i] = 0
      B[i+1] = 0
      for j in range(n)[i+2:]:
        if A[j] == A[i]:
          B[j] = 0
        else:
          break
    else:
      continue
      
  c = 0
  if B[i] == 0:
    continue
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 0
    B[i+1] = 0
    for j in range(n)[i+2:]:
      if A[j] == A[i]:
        B[j] = 0
      else:
        break
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if A[j] == A[i]*c:
        B[j] = 0
print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
DI={}
for i in A:
  if i not in DI:
    DI[i]=1
  else:
    DI[i]+=1  
d=0
B=sorted(list(set(A)))
n=len(B)
for i in range(n):
  if DI[B[i]]==1:
    d+=1
    for j in range(0,i):
      if B[i]<B[j]*2:
        break
      if B[i]%B[j]==0:
        d-=1
        break
print(d)

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    B=list(map(int,input().split()))
    cho=set()
    B.sort()
    for i in range(N-1):
        if B[i]==B[i+1]:
            cho.add(B[i])
    A=set(B)
    A=list(A)
    A.sort()
    lenA=len(A)
    for i in range(lenA):
        if A[i]==-1:
            continue
        for j in range(i+1,lenA):
            if A[j]==-1:
                continue
            if A[j]%A[i]==0:
                A[j]=-1
    cnt=set()
    for i in range(len(A)):
        if A[i]!=-1:
            cnt.add(A[i])
    print(len(cnt-cho))
    
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = (int)(input())
a = list(map(int, input().split()))
#print("p = {}".format(p))

ret = 0
for i in range(len(a)):
    flag = False
    for j in range(len(a)):
        if i != j and a[i] % a[j] == 0:
            #print("{} % {} == 0".format(a[i], a[j]))
            flag = True
            break
    if flag == False:
        ret += 1

print("{}".format(ret))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

count=0
isDividable=0

for i in range(n):
  isDividable=0
  for j in range(n):
    if i != j and (a[i] == a[j] or a[i] % a[j] == 0):
      isDividable=1
      break
  if isDividable==0:
    count=count+1
print(count)