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:
def check_prime(k):
    if k == 1:return 1
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0

    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()
if a[0] == 1:
    if n == 1 or a[1] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

    if flag:
        ans += 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(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:
import numpy as np
import sys

def resolve():
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    N = int(input())
    A = list(map(int,input().split()))
    ans = np.ones(N,dtype=int)
    for i in range(N-1):
        for j in range(i+1,N):
            if A[i] % A[j] == 0:
                ans[i] = 0
                break
    for i in range(N-1):
        for j in range(i+1,N):
            if A[N-1 - i] % A[N-1 -j] == 0:
                ans[N-1 - i] = 0
                break
    print(sum(ans))
resolve()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i in range(N)])
#A = list(set(A))
A = sorted(A)#わるほう

kouho = list(A.copy())#わられるほう
target = list(set(A))
#print(A)

for i in range(1,len(kouho)):
    if (kouho[max(0,i-1)]==kouho[i]):
        if kouho[i] in target:
            target.remove(kouho[i])
            
kouho = sorted(target.copy())

for i in range(len(A)):
    for j in range(0, len(target)):
        if target[j] <= A[i]:
            continue
        elif  target[j] in kouho:
            if target[j] % A[i] == 0:
                #print(target[j], A[i])
                kouho.remove(target[j])
    target = list(kouho.copy())
    if target == []:
        break
        
print(len(target))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def make_divisors(n):
    divisors = set()
    i = 1
    while i*i <= n:
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
        i += 1
    return divisors


def main():
    N = int(input().strip())
    divisors = set()
    ans = set()
    l = [int(i) for i in input().strip().split()]
    heapq.heapify(l)

    for _ in range(N):
        n = heapq.heappop(l)

        if n in divisors:
            if n in ans:
                ans.remove(n)
            continue

        divs = make_divisors(n)

        for d in divs:
            if d in divisors:
                divisors.add(n)
                break
        else:
            divisors.add(n)
            ans.add(n)

    return len(ans)


if __name__ == "__main__":
    print(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)
from numba import njit,i8


@njit(i8(i8,i8[:]))
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:
# 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 = [False] * (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] = True
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x]:
                flag = False
                break
        bl[a] = True
        if flag:
            answer += 1

    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
in_data = [int(x) for x in input().split(' ')]
result = 0

for i in range(n):
  ok_flg = True
  toBeDiv = in_data[i]
  for j in range(n):
#    toDiv = in_data[j]
#    if max(in_data) == toBeDiv:
#      ok_flg = False
#      break
    if i == j:
      continue
    if toBeDiv%in_data[j]==0:
      ok_flg = False
      break
  if ok_flg:
    result += 1

print(result)

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
  l=a[i]/2
  for j in range(n):
    if i != j and (a[i] == a[j] or (a[j]<=l and a[i] % a[j] == 0)):
      isDividable=1
      break
  if isDividable==0:
    count=count+1
print(count)

Submission status: Time Limit Exceeded

Solution code:
a=[input() for i in range(2)]
a1=int(a[0])
a2=a[1].split()
p=[int(i) for i in a2]
c=0

for i in range(len(p)):
	mod=[]
	#mod=[a[i]%a[j] for j in range(len(p)) if i!=j]
	for j in range(len(p)):
		if i!=j:
			amari=p[i]%p[j]
			mod.append(amari)

	count=len([i for i in mod if i==0])

	#print(mod)

	if count==0:
		c+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import Counter

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

candidate = set(seq)

result = set()

while candidate:
    x = min(candidate)
    candidate.remove(x)
    for y in tuple(candidate):
        if x == y:
            continue
        if y % x == 0:
            candidate.remove(y)
    result.add(x)

for c in tuple(result):
    if seq.count(c) > 1:
        result.remove(c)

print(len(result))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def divisors(n):
    lower = []
    upper = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            lower.append(i)
            if i != n // i:
                upper.append(n // i)

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    A.sort()
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A:
        D = divisors(a)
        if C[a] == 1 and all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

num = 0
t_2 = False
t_3 = False
t_5 = False
t_7 = False


for i in range(N):
    flag = True

    if t_2 == True:
        if A[i] % 2 == 0:
            flag = False
    if t_3 == True:
        if A[i] % 3 == 0:
            flag = False
    if t_5 == True:
        if A[i] % 5 == 0:
            flag = False
    if t_7 == True:
        if A[i] % 7 == 0:
            flag = False


    if flag == True:
        for j in range(N):
            if A[i] % A[j] == 0 and i != j:
                flag = False
                break

    if i < 20:
        if A[i] == 2:
            t_2 = True
        elif A[i] == 3:
            t_3 = True
        elif A[i] == 5:
            t_5 = True
        elif A[i] == 7:
            t_7 == True


    if flag == True:
        num += 1

print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([int(s) for s in input().split()])
k = 0
l = []
for i in A: #ｎ個の数について調べる 今調べてるのはi
    for j in A:  #要素で割っていって余りがないか調べる　自分自身で割るときは余らないことに注意
        if (i%j == 0):
            k += 1
        if (k > 1):
            break
    if (k == 1):
        l = l + [i]
    k = 0
print (len(l))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tmp = list(map(int, input().split()))
ans = 0
a = sorted(tmp)
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()
double = set(a)
for i in double:
    if not tmp.count(i) == 1:
        ans -= tmp.count(i)

# a.sort()


check = True
loop = list(range(len(a)))
for i in loop:
    for j in range(0, i):
        if not a[j] == 1:
            if a[j]*2 > a[i]:
                break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True
# print(a)
# print(ans)
# print(double)

# ans -= len(set(double))
# ans -= len(double)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [False]*n
a.sort()
z = 0
for i,v in enumerate(a):
    if b[i]:
        continue
    for j in range(i+1,n):
        if b[j]:
            continue
        if a[j] == v:
            b[i] = True
            b[j] = True
        elif a[j] > a[-1]//v * v:
            break
        elif a[j] % v == 0:
            b[j] = True
print(b.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
a = int(input())
b = list(map(int,input().split()))
count = 0
b = sorted(b)
b_len = len(b)
for i in range(b_len):
  _count = 0
  _main = b[i]
  if (i+2)<=b_len:
    if _main==b[i+1]:
      continue
  for j in range(0,i):
    if i==j:
      continue
    if (_main%b[j])==0:
      break
    else:
      _count +=1
  if _count == i:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
# print(a)
# print(n)
ans = [0 for _ in range(n)]


for i_out in range(n):
    if ans[i_out] == 1:
        continue
    # print(i_out)
    r = np.array(a) / a[i_out] - \
        (np.array(a) / a[i_out]).astype('int64')
    # print(r)
    idx = np.where(r == 0)
    # print(idx)
    # print((np.array(list(idx)))[0].tolist())
    if i_out < n-1:
        if a[i_out] == a[i_out + 1]:
            ans[i_out] = 1
    for i in (np.array(list(idx)))[0].tolist():
        if i == i_out:
            continue
        # print('i', i)
        ans[i] = 1

# print(ans)
print(n - sum(ans))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = sorted([int(i) for i in input().split()],reverse=True)
[_b,r,c] = [0,0,0]

for i in range(N-1):
  b = A[i]
  if _b == b:
    c += r
    continue
  for y in range(i+1,N):
    if b % A[y] == 0:
      r = 0 
      break
  else:
    c += 1
    r = 1
  _b = b
else:
  if A[N-1] != _b:
    c += 1
  print(c)

Submission status: Time Limit Exceeded

Solution code:
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]


def main():
    n = int(input())
    a = list(map(int, input().split()))
    Ans = n
    for i in range(len(a)):
        b = a[i]
        if a.count(b) >= 2:
            Ans = Ans - 1
        else:
            c = make_divisors(b)[:-1]
            for j in range(len(c)):
                if c[j] in a:
                    Ans = Ans - 1
                    break
    print(Ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

i = 0
while i < len(a):
  j = i+1
  while j < len(a):
    if a[j]%a[i]==0 and a[j]!=a[i]:
      a.pop(j)
    else:
      j += 1
  i += 1

for i in a:
  if a.count(i)>=2:
    a = [j for j in a if i!=j]

print(len(a))

Submission status: Time Limit Exceeded

Solution code:
A1 = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
N = A1[0]
i_list=[]
for i in range(N):
  for j in range(N):
    if i!=j and p[i] % p[j]==0:
      i_list.append(i)
      break
new_list=[]
for i in range(int(len(i_list))):
  j=i_list[i]
  new_list.append(p[j])
check = set(p) ^ set(new_list)
print(int(len(check)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin

def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    a = np.sort(a)
    count = 0
    idxes = np.arange(len(a))
    while len(idxes):
        idx = idxes[0]
        idxes = np.delete(idxes, 0)
        var = a[idx]
        if len(np.where(a[idxes] == var)[0]) == 0:
            count += 1
        idxes = idxes[np.where(a[idxes] % var != 0)[0]]
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  n = int(input())
  a = list(map(int,input().split()))

  a.sort()
  ans = 0

  while True:
    x = a[0]
    if a.count(x) == 1:
      ans += 1
    for y in a[:]:
      if y%x == 0:
        a.remove(y)
    if len(a) == 0:
      break
  print(ans)
  
main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    NG = 0
    finish = 0
    X = A[i]
    for j in range(N):
        if i == j:
            continue
        if NG == 1:
            break
        else:
            #print(X, A[j], X % A[j])
            if X < A[j]:
                ans += 1
                finish = 1
                break
            if X % A[j] == 0:
                NG = 1
                break
    if NG == 0 and finish == 0:
        ans +=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
flag = dict()
for a in A:
    if a in flag:
        if flag[a]:
            flag[a] = False
    else:
        flag[a] = True

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

print(list(flag.values()).count(True))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N
    c = collections.Counter(As)

    if N == 1:
        print(1)
    elif len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    elif As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)

i = 0
for key, count in sorted_dict:
    if flag_list[i] == 0:
        i += 1
        continue
    if count > 1:
        flag_list[i] = 0
    i += 1
    j = i
    for key1, count1 in sorted_dict[i:]:
        if flag_list[j] == 0:
            j += 1
            continue
        if key1 % key == 0:
            flag_list[j] = 0
        j += 1

print(sum(flag_list))

Submission status: Time Limit Exceeded

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

count=n


for i in range(n):
    flg=0
  
    for j in range(n): 
        
        if a[i]%a[j]==0 and i!=j:
            #print(a[i],a[j])
            count-=1
            break

print(count)

Submission status: Time Limit Exceeded

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

N=int(input().rstrip('\n'))
As=[int(x) for x in input().rstrip('\n').split()]
As2 = sorted(list(set(As)))
res = 0
for i in range(N):
  if len(As2)>0:
    now = As2[0]
    if As.count(now)==1:
      res += 1
    if now * 2 > As2[-1]:
      As2=As2[1:]
    else:
      As2=[x for x in As2 if x%now!=0]
  else:
    break
print(res)

Submission status: Time Limit Exceeded

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

import math
import bisect
import collections
from collections import deque
import heapq
c = collections.Counter(li)
li = list(set(li))
heapq.heapify(li)
b = []
for l in li:
    heapq.heappush(b,(-1)*l)
while len(b)>0:
    ba = heapq.heappop(b) * (-1)
    #print(ba)
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in b:
        if ba%tt == 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()

memo = [0] * n

for i in range(n):
    for j in range(n):
        if memo[j] or i == j:
            continue
        if A[j]%A[i] == 0 and A[j] >= A[i]:
            memo[j] = 1

print(n - sum(memo))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
c = 0
for i in range(N):
  d =0 #カウンタの初期化
  for j in range(N):
    if a[i] % a[j] == 0:
      d = d+1
  if d > 1:#あるiを割り切れるjの存在の確認
    c = c+1
print(N-c)

Submission status: Time Limit Exceeded

Solution code:
length = int(input())
mat = list(map(int, input().split()))

count=0
for i in range(length):
  flg =False
  flist=[]
  for j in range(length):
    if i!= j:
      if mat[i]%mat[j] !=0:
        flist.append(True)
      else:
        flist.append(False)
  if all(flist)==True:
    count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L = list(map(int,input().split()))
L2 = sorted(L,reverse=True)

#print(L)
#print(L2)

a = 0
s = set()
for i in range(n):
    t = L2.index(L[i])
#    print(str(L[i]) + 't:' + str(t))
    for j in range(n-t-1):
#        print('j:' + str(t+j+1) + ' L2:' + str(L2[t+j+1]))
        if L[i]%L2[t+j+1] == 0:
            break
    else:
#        print(L[i])
        if L[i] not in s:
            a += 1
    s.add(L[i])
print(a)

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)
#print(A)

ans=[]

flg=0 
for i in range(N):
  flg=0
  #print(A.count(A[i]))
  if A.count(A[i]) > 1:
    flg=1

  if flg == 0:
    for j in range(0,N-1-i):
      #print(i,j,A[i],A[N-1-j])
      if A[i] % A[N-1-j] == 0:
        flg=1
        break
      if A[i]/2 < A[N-1-j]:
        break
      
  if flg == 0:
    ans.append(i)
  else:
    flg = 0

#print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from builtins import int, map, list, print, len
    from collections import deque
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = (lambda: (sys.stdin.readline()).rstrip())
    input_list = (lambda: input().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N = input_number()
    A = input_number_list()
    A.sort()
    A = deque(A)
    tmp_A = deque(A)
    tmp_ls = [A[0]]
    for i in range(1, len(A)):
        for t in tmp_ls:
            if A[i] % t == 0:
                # print(f'remove: {A[i]}')
                tmp_A.remove(A[i])
                break
        else:
            tmp_ls.append(A[i])
    minus_count = 0
    for t in tmp_A:
        if A.count(t) > 1:
            minus_count += 1
    print(len(tmp_A) - minus_count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input().strip())
L = list(map(int, input().strip().split()))
seen = Counter()
ans=0

for x in L:
    seen[x]+=1

for x in L:
    if seen[x]>1 or x!=1 and 1 in seen:
        continue

    tmp=2
    while tmp**2<=x:
        if x%tmp==0 and (tmp in seen or x/tmp in seen):
            break
        tmp+=1
    else:
        ans+=1

print(ans)

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)

Submission status: Time Limit Exceeded

Solution code:
n, *l = map(int,open(0).read().split())
l = sorted(l, key = abs, reverse= True)
check = [1]*n
for i in range(n-1):
#     print(i,check)
    if check[i] == 0:
        continue
    for j in range(1,n-i ):
#         print(i,j,check)
        if l[i]%l[-j] == 0:
            index_num = [n for n, e in enumerate(l) if e == l[i]]
            
            for e in index_num:
                check[e] = 0
            break
print(sum(check))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(map(int, input().split()))
S.sort()
ans = 0
if N > 1:
    if S[0] < S[1]:
        ans += 1
else:
    ans = 1
for i in range(N-1, 0, -1):
    num = S[i]
    M = num//2
    flg = True
    for j in range(i):
        if num%S[j] == 0:
            flg = False
            break
        elif S[j] > M:
            break
    if num == S[i-1]:
        flg = False
    elif i < N-1:
        if num == S[i+1]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

print(l.count(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = Counter(list(map(int, input().split(' '))))
ans = 0
for i in A.keys():
    flg = True
    if A[i] > 1:
        continue
    tmp = set([])
    for j in range(1,int(i**0.5)+2):
        if not i%j:
            tmp.add(j)
            tmp.add(i//j)
    for k in tmp:
        if A[k] and i != k:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = [int(i) for i in input().split()]

a.sort()
b = set()
c = 0
for i, v in enumerate(a):
    flag = True
    for j in range(1, int(math.sqrt(v))+1):
        if v % j == 0 and (j in b or v/j in b):
            flag = False
            break
    if flag == True:
        b.add(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
  
print(c)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
j=(input().split())

jj=[]
f=0

for a in range(len(j)):
    jj.append(int(j[a]))
        

for a in range(N):
    e=0
    for x in range(N):
        if x!=a:
            if jj[a]%jj[x]!=0:
                e=e+1
    if e==N-1:
        f=f+1

print(f)

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))+1):
        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()))
total = 0
for i in range(0,N):
  count = 0
  for j in range(0,N):
    if i == j:
      continue
    if A[i] % A[j] == 0:
      count += 1
  if count == 0:
    total += 1
  count = 0
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    b = []
    for i in range(n):
      flag = True
      if not a[i] in b:
        for x in b:
          if a[i] % x == 0:
            flag = False
            break
        if flag:
          for k in range(n):
            if i != k and a[i] % a[k] == 0:
              flag = False
              break
        if flag:
          count += 1
          b.append(a[i])
    print(count)
  
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
np_A = np.array(A)
sort_A = np.sort(np_A)
l = np.zeros(N)

ans = 0
for i in range(N):
  q_1 = sort_A//sort_A[i]
  q_2 = sort_A/sort_A[i]
  count_q = np.where(q_1 == q_2)
  for j in range(len(count_q[0])):
    l[count_q[0][j]] += 1
l = l-1
print(N-np.count_nonzero(l))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()
A = sorted(A)
time = 0
for i in range(N):
    list = []
    for z in range(N):
        list.append(z)
    list.remove(i )
    point = 0
    for y in range(len(list)):
        x = int(A[i]) % int(A[list[y]])
        if x == 0:
            point += 1
            break
    if point == 0:
        time += 1
print(time)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
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 solve():
    N = II()
    A = LI()

    cost = {}
    for a in A:
        if cost.get(a, -1) == -1:
            cost[a] = 1
        else:
            cost[a] = 0

    A = sorted(A)

    memo = {}
    ans = 0
    for a in A:
        divs = make_divisors(a)
        for d in divs:
            if memo.get(d, -1) != -1:
                break
        else:
            ans += cost[a]
        memo[a] = 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if i != j and A[i]%A[j] == 0:
            b += 1
            break


print(n-b)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = [int(x) for x in input().split()]
ans = 0
for i in range(int(n)):
  for j in range(int(n)):
    if i!=j and a[i]%a[j]==0:
      ans = ans + 1
      break
print(int(n) - ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,bisect
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
x=list(set(l))
x.sort()
def div(n):
    ass = set([1,n])
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ass.add(i)
            ass.add(n//i)
    return ass 
ans=0
s=set()
if len(x)==0:
  print(0)
else:
  for y in x: 
    memo=0
    if c[y]>1:
      s.add(y)
    else:
      for j in range(1,int(y**0.5)+1):
        
        if y%j == 0 :
          if y//j in s or j in s:
            memo-=1
      s.add(y)
      if memo==0:
        ans+=1       
  print(ans)