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:
N = int(input())
A = list(map(int, input().split()))
A.sort()
limit = max(A) / 2


def eratos(A, limit):
    prime = []
    for a in A:
        if a > limit:
            return A
        A = [x for x in A if (x == a or x % a != 0)]
        # print(A)
    return A

if __name__ == '__main__':
    eratosed_list = eratos(A, limit)
    # print(f'eratosed_list:{eratosed_list}')
    print(len([x for x in set(eratosed_list) if eratosed_list.count(x) == 1]))

Submission status: Time Limit Exceeded

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

check = True
for i in range(n):
    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())
p = list(map(int, input().split()))
count = 0
k = 0

for i in range(n):
    for j in p:
        if p[i] % j == 0 and i != k:
            break
        k += 1
    if(k == n):
        count += 1
    flag = False
    k = 0

print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


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

    # 愚直に行うとO(N^2)となる
    # 各要素、約数を列挙(sqrt(N))
    # 約数がこれまでに存在したかをチェックO(1)*約数の個数
    # 存在すれば1を加える

    # print(A)
    ans = 0
    history = [False]*N
    for i in range(N):
        if history[i]:
            continue
        # A[i]を乗じていくとどうか
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                history[j] = True
        if i+1 < N and A[i] == A[i+1]:
            history[i] = True
    print(N-sum(history))

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    a_set = set(a)

    a_cnt = collections.Counter(a)

    a_list = list(a_set)
    a_list.sort()

    ans = 0
    for i, ai in enumerate(a_list):
        if a_cnt[ai] > 1:
            continue
        idx = bisect.bisect_left(a_list, ai // 2)
        if i == idx:
            idx -= 1
        flg = True
        for j in range(idx, -1, -1):
            if ai % a_list[j] == 0:
                flg = False
                break
        if flg:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in A:
  for j in A:
    if i%j==0:
      count+=1
  if count>1:
      s+=1
  count=0
      
ans=N-s
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()
from bisect import bisect_left
while True:
    v = a[0]
    if v*2>a[-1]:
        for item in a:
            tmp.add(item)
        break
    tmp.add(v)
    a = [item for item in a if item%v!=0]
    if not a:
        break

# tmp = [a[0]]
# for i in range(1, n):
#     num = a[i]
# #     for i in range(len(tmp)-1, -1, -1):
#     for i in range(len(tmp)):
#         item = tmp[i]
#         if num%item==0:
#             break
#         if item*2>num:
#             tmp.append(num)
#             break
#     else:
#         tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
A = np.sort(A)

c = 0
while len(A) > 0:
    ai = A[0]
    if not ai in A[1:]:
        c += 1
    mask = A[1:] % ai != 0
    A = A[1:][mask]

print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
while len(A)>1:
    p = A[0]
    if len(A)==1:
        ans += 1
    else:
        if A[0] != A[1]:
            A = [j for j in A if j % p !=0]
            ans += 1
        else:
            A = [j for j in A if j % p !=0]
if len(A)==1:
    print(ans+1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
import sys


def input():
    return sys.stdin.readline()[:-1]


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n and i in c:
                return False

            tmp = n // i
            if i != tmp:
                if tmp != n and tmp in c:
                    return False
    return True


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

c = Counter(A)

# 1がある時
if 1 in c:
    if c[1] >= 2:
        print(0)
    else:
        print(1)
    exit(0)

ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 1と同数がなくて素数なら割り切れる数はない
    if is_prime(a):
        ans += 1
        continue

    # 約数があるか
    if make_divisors(a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

counts_two = list_input.count(2)

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i == 2 and counts_two == 1:
            break
        if i == 2 and counts_two >= 2:
            anti_ans += 1
            break
        if i != 2 and counts_two >= 2 and i % 2 == 0:
            anti_ans += 1
            break
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    # a = list_a.pop(0)
    # list_a.append(a)
    list_a.append(list_a.pop(0))
print(len(list_input) - anti_ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

arr.sort()
c = Counter(arr)

cnt = 0

while cnt < len(arr):
    arr = [arr[cnt]] + [x for x in arr if x % arr[cnt] != 0]
    arr.sort()
    cnt += 1

result = set(arr) - {x for x, y in c.items() if y >= 2}

print(len(result))

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(N-i-1):
    if A[i]%A[N-j-1]==0:
      break
    elif A[i]//A[N-j-1] < 2:
      continue
  else:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def divisors(n):
    lst = []; i = 1
    while i ** 2 <= n:
        q, r = divmod(n, i)
        if r == 0:
            lst.append(i)
            if i != q: lst.append(q)
        i += 1
    return lst

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
cnt = Counter(A)
ans = 0
for a in A:
    if cnt[a] > 1: continue
    for i in divisors(a):
        if i == a: continue
        if cnt[i] >= 1: break
    else:
        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):
    ok = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            ok = False
    if ok: ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0

div = [1] * n
for i in range(n):
    lst = list(map(lambda x: x % a[i], a))
    lst[i] = 1
    div = [x * y for (x, y) in zip(div, lst)]

print(n-div.count(0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    count = 0
    for j in range(n):
        if i != 0:
            if a[i] == a[i - 1]:
                break
        if i == j:
            pass
        elif count == 0:
            if a[i] % a[j] == 0:
                count = 1
        else:
            break
    else:
        if count == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().strip().split()))
a.sort(reverse=True)
s = a.copy()
for i in a:
  mod = True
  for j in s:
    if i % j == 0 and i > j :
      mod = False
      s.remove(i)
      break

import collections
c = collections.Counter(s)
result = 0
for i in c:
  if c[i] == 1:
    result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mcount=0
for i in range(0,n):
  count=0    
  for j in range(0,n):
    if i==j:
      continue
    else:
      if a[i]%a[j]!=0:
        count+=1 
  if count==n-1:
      mcount+=1
print(mcount)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num = list(int(x) for x in input().split())
num.sort()
count = 0
for i in range(N):
    # インデックス確認
    if i >= len(num):
        break
    no = num[i]
    flag = 0
    for j in num[i+1:]:
        if j % no == 0:
            # 同じ数だった場合
            if j == no:
                flag = 1
            num.remove(j)
    if flag == 1:
        count += 1
print(len(num)-count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input()) 
a = list(map(int, input().split()))
a2 = sorted(a)
ans = n
for i in range(len(a2)):
  for j in range(len(a2)):
    if i != j or i > j:
      if a2[i] % a2[j] == 0:
        ans -= 1
        break

print(ans)

Submission status: Time Limit Exceeded

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

alist.sort(reverse=True)
results = [True for i in range(n)]

for i in range(len(alist)):
    result = False
    if results[i]!=False:
        for j in reversed(range(i,len(alist))):
            result = True
            ai = alist[i]
            aj = alist[j]
#            print("{}[{}] {}[{}] {}/{}".format(ai,i,aj,j,(ai==aj),(ai%aj==0)))
            if i!=j and (ai==aj):
                results[j] = False
            if i!=j and (ai%aj  == 0):
                result = False
                break
    results[i] = result

print(results.count(True))

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):
    flg = 0
    for j in range(i):
        if i +1 < N:
            if A[i+1] == A[i]:
                flg = 1
                break
        if A[i] == A[i-1]:
            flg = 1
            break
        if A[j]*2 > A[i]:
            #print(A[j], A[i])
            break
        if i != 0:
            if A[i]%A[j] == 0:
                flg = 1
                break    
    if flg == 0:
        if i +1 < N:
            if A[i+1] != A[i]:
                ans += 1
        else:
            ans += 1

print(ans)

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)):
  count = 0
  for j in range(int(n)):
    if i!=j and a[i]%a[j]!=0:
      count = count + 1
  else:
    if count == int(n) - 1:
      ans = 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):
    for j in range(i+1,n):
        if a[i]==a[j]:
            l[i]=1
        if a[j]%a[i]==0:
            l[j]=1

print(l.count(0))

Submission status: Time Limit Exceeded

Solution code:


N = int(input())


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


A.sort()

d=[A[0]]
s=0
for i in range(N):
    if i!=N-1:
        if A[i]==A[i+1]:
            s+=1
            continue
    if i!=0:
        if A[i]==A[i-1]:
            s+=1
            continue
    if i==0:
        continue
    for j in range(len(d)):
        if A[i]<2*d[j]:
            d.append(A[i])
            break
        if A[i] % d[j] == 0:
            s += 1
            break
        if j == len(d)-1:
            d.append(A[i])

print(N-s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
good = N
i = 0
A = [int(x) for x in input().split()]
A.sort(reverse=True)
for i in range(N):
    if A[i]==A[i-1] and i >= 1:
        good -= 1
        continue
    for j in range(i+1,N):
        if A[i]%A[N-j+i]==0:
            good -= 1
            break
print(good)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

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

from itertools import product
lst = []
for x, y in product(A, A):
    lst.append(x%y)

counter = 0
for i in range(n):
    if lst[i*n:i*n+n].count(0) == 1:
        counter=counter+1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import collections

def factorization(n):
    pf_cnt = {1:1}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt



def main():
    n = int(input())
    al = list(map(int, input().split()))

    al_not_multi = []
    dels = []
    cnt = collections.Counter(al)
    for i,v in cnt.items():
        if v == 1:
            al_not_multi.append(i)
        else:
            dels.append(i)

    if not al_not_multi:
        print(0)
        return

    al_not_multi.sort()
    primes = []
    for a in al_not_multi:
        for prime in primes + dels:
            if a%prime == 0: break
        else:
            primes.append(a)
    # print(primes)
    print(len(primes))


    # primes = {}
    # for a in al:
    #     fac = factorization(a)
    #     for prime,cnt in fac:
    #         primes.setdefault(prime,10000)
    #         primes[prime] = min(cnt, primes[prime])




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    if 1 in l[i]:
        continue
    for j in range(i+1,n):
        if a[i]%a[j]==0:
            l[i][j]=1
        if a[j]%a[i]==0:
            l[j][i]=1

cnt=0
for i in range(n):
    if 1 not in l[i]:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
N= int(input())
A = list(map(int, input().split()))
A.sort()
prod = math.prod(A)

count = 0

for i in range(N):
    qualify = 1

    if i < N-1 and A[i + 1] == A[i]:
        continue

    if i > 1 and A[i - 1] == A[i]:
        continue

    max_index = np.searchsorted(A, A[i]/2+1)
    for j in range(i):
        if (A[i] % A[j]) == 0:
            qualify = 0
            break


    count += qualify


print(count)

Submission status: Time Limit Exceeded

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

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

from functools import lru_cache

@lru_cache(maxsize=None)
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

@lru_cache(maxsize=None)
def mySolve(n):
    flag = True
    if l[n] >= 2:
        flag = False
    else:
        da = divisor(n)
        for d in da:
            if d in l.keys() and d != n:
                flag = False
                break
    return flag

ans = 0
for a in A:
    if mySolve(a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    c=0
    la=len(a)
    for i in range(la):
        for j in range(la):
            if a[i]%a[j]==0 and i!=j:
                break
        else:
            c+=1
    print(c)
if __name__ == "__main__":
    main()

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:
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:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(v, pp):
	if v == pp[-1]:
		return False, -1
	
	for p in pp:
		if v % p == 0:
			return False, 0
		if v < 2*p:
			return True, 0
	return True, 0
			

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp)
		if tf:
			pp.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math, copy

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

ans = 0
A.sort()

for i in range(len(A)):
    root = math.sqrt(A[i])
    for x in range(1, int(root)+1):
        if (A[i] / x in A[:i]) or (A[i] / x in A[i+1:]) or ((x in A[:i]) and (A[i] % x == 0)):
            break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a = list(map(int,input().split()))
a.sort()
if len(set(a))==1 and len(a) != 1:
    print(0)
    sys.exit()

wa = 0
for i in range(len(a)):
    flg = 0
    for j in range(len(a)):
        if i != j and a[i]%a[j] == 0:
            flg = 1
            break
    if flg == 0:
          wa += 1
    
print(wa)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections

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

C = collections.Counter(A)
C_keys = np.array(list(C.keys()))
C_values = tuple(C.values())

divisible = 0
for i, c in enumerate(C_keys):
    if 0 in c % C_keys[i + 1:]:
        divisible += C_values[i]
    else:
        if C_values[i] > 1:
            divisible += C_values[i]
        
print(N - divisible)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
A = sorted(A)
S = Counter(A)

# エラストテネスの篩
prime = [2]
max = 10 ** 6 + 1
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

prime_list = [0] * (10 ** 6 + 1)
for i in range(len(prime)):
    prime_list[prime[i]] = 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

numlist = [0] * (10 ** 6 + 1)

cnt = 0
for j in range(N):
    flag = True
    ng_list = []
    if prime_list[A[j]] == 1:
        ng_list = [1, A[j]]
    else:
        ng_list = make_divisors(A[j])
    for ng in ng_list:
        if numlist[ng] >= 1:
            flag = False
            break
    if flag:
        numlist[A[j]] += 1
        cnt += 1

for i in range(len(numlist)):
    if numlist[i] >= 1 and S[i] >= 2:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
mod0 = [True] * N
for i in range(N):
    if not mod0[i]:
        continue
    for j in range(1,N - i):
        if not mod0[i+j]:
            continue
        elif A[i + j] % A[i] == 0:
            mod0[i + j] = False
cnt = 0
for i in range(N):
    if mod0[i]:
        cnt += 1
        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 = list(map(int,input().split()))
aa = np.array(A)
aa = np.sort(aa)
for i in range(len(aa)):
  div = []
  for j in range(i+1,len(aa)):
    if aa[j]%aa[i] == 0:
      div.append(j)
      if aa[j] == aa[i]:
        div.append(i)
  aa = np.delete(aa,div,0)
print(len(aa))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

total = 0

for i in range(N):
    Flg = True
    for j in range(N):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            Flg = False
            break
    if Flg:
        total += 1
print(total)

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=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:
    continue
  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 bisect
n_temp=int(input())
x_temp=list(map(int,input().split()))
x_temp.sort()

x=[x_temp[0]]
n=1
ans=[]
if(n_temp==1):
    ans.append(True)
else:
    if(x_temp[0]==x_temp[1]):
        ans.append(False)
    else:
        ans.append(True)
for i in range(1,n_temp):
    if(x_temp[i]!=x_temp[i-1]):
        x.append(x_temp[i])
        n+=1
        if(i==n_temp-1):
            ans.append(True)
        else:
            if(x_temp[i]==x_temp[i+1]):
                ans.append(False)
            else:
                ans.append(True)


for i in range(n-1):
    for j in range(2,1+x[n-1]//x[i]):
        basho=i+bisect.bisect_right(x[i+1:],x[i]*j)
        if(x[i]*j==x[basho]):
            ans[basho]=False

kotae=0

for a in ans:
    if(a):
        kotae+=1

print(kotae)

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]==0:
        for j in range(i+1,n):
            if done[j]==0:
                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:
from math import ceil

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

m = 10**6+100
n_map = {}
v_a = []
nn_map = {}
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
    if i in nn_map:
        continue
    for j in range(2, ceil(m / i) + 1):
        nn_map[i * j] = True

v_a = [k for k, v in n_map.items() if v == 1]

v_a.sort()
vv_a = []

for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)

print(len(vv_a))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
flags = {i: 0 for i in range(N)}

ans = []

for i in range(N):
    if flags[i]:
        continue

    x = A[i]
    for j in range(N):
        if i == j:
            continue
        y = A[j]

        if flags[j]:
            continue
        if x > y:
            if x % y == 0:
                flags[i] = 1
        if x == y:
            flags[i] = 1
            flags[j] = 1
        else:
            if y % x == 0:
                flags[j] = 1
#print(flags)
print(N-sum(flags.values()))

Submission status: Time Limit Exceeded

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

a = sorted(a)
w = 0
while True:
    h = 1
    cn = 0
    while True:
        if w + h == len(a):
            '''
            print(a)
            '''
            if cn == 1:
                del a[w]
                w -= 1
            break
        if a[w] == a[w+h]:
            cn =1
        if a[w+h] % a[w] == 0:
            '''
            print(h)
            '''
            del a[w+h]
        else:
            '''
            print(a[w+h], h, w, a)
            '''
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

Submission status: Time Limit Exceeded

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


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().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:
N = int(input())
A = list(map(int, input().split()))

ans = 0
NG = 0
for i in range(N):
    NG = 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] == 0:
                NG = 1
                break
    if NG == 0:
        ans +=1

print(ans)