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())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
#print(lst)
set_lst = set(lst)

if lst[n - 1] == 1:
  if n > 1:
    if lst[n - 1] == lst[n - 2]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  count = 0
  for i in range(n):
    if i < n - 1:
      flag = True
      if (lst[i] == lst[i + 1]) or (lst[i] == lst[i - 1] and i > 0):
        flag = False
      else:
        for j in set_lst:
          if j >= lst[i]:
            continue
          if lst[i] % j == 0:
            flag = False
            break
      if flag:
        count += 1
    if i == n - 1:
      if n > 1:
        if lst[i] != lst[i - 1]:
          count += 1
      else:
        count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
#print(lst)

if lst[n - 1] == 1:
  if n > 1:
    if lst[n - 1] == lst[n - 2]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  count = 0
  for i in range(n):
    if i < n - 1:
      flag = True
      if (lst[i] == lst[i + 1]) or (lst[i] == lst[i - 1] and i > 0):
        flag = False
      else:
        for j in range(n - 1, i, -1):
          if lst[i] % lst[j] == 0:
            flag = False
            break
      if flag:
        count += 1
    if i == n - 1:
      if n > 1:
        if lst[i] != lst[i - 1]:
          count += 1
      else:
        count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1 for i in range((max(a) + 1))]

for aa in a:
    for j in range(2*aa,max(a)+1, aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1 for i in range(max(a)+1)]

for aa in a:
    for j in range(2*aa,max(a)+1, aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque
from operator import mul
from functools import reduce

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

a.sort()

b = [1 for i in range(n)]

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

print(sum(b))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
data=input().split()
count=0
for i in range(N):
    for j in range(N):
        if j != i:
            if int(data[i])%int(data[j]) == 0:
                break
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
data=input().split()
count=0
for i in range(N):
    for j in range(0,i):
        if int(data[i])%int(data[j]) == 0:
            break
    else:
        for k in range(i+1,N):
            if int(data[i])%int(data[k]) == 0:
                break
        else:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A_list = defaultdict(int)
A_max = max(A)

for a in A:
    i = 2
    while a * i <= A_max:
        A_list[a * i] = 1
        i += 1
    if A.count(a) > 1:
        A_list[a] = 1

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

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    f = True
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                f = False
    if f:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and A.count(a) == 1 for a in A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = []
cnt = 0
for i in range(N):
    if A[i] in B == True:
        cnt += 1
    else:
        for j in range(i):
            if A[i] % A[j] == 0:
                cnt += 1
                if A[i] == A[j] and i == j+1:
                    cnt += 1
                for k in range(10 ** 5):
                    B.append(A[i] * k)
                break
print(N - cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

def solution():
    _ = input()
    user_input = input()
    num_list = [int(x) for x in user_input.split()]

    iter = max(num_list) // min(num_list) 

    h = {}
    for num in num_list:
        h[num] = h.get(num, -1) + 1
    
    multiplier = 1
    for _ in range(iter):
        for num in h:
            if num * multiplier in h:
                h[num * multiplier] += 1
        multiplier += 1
    
    result = 0
    for _, val in h.items():
        if val == 1:
            result += 1
    print(result)

solution()

Submission status: Time Limit Exceeded

Solution code:

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

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for i, Ai in enumerate(A):
    found = False
    for j, Aj in enumerate(A):
        if i != j and Ai % Aj == 0:
            found = True
            break
    if not found:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6 + 1)
for i in range(n):
    for j in range(1, 10**6//a[i]+1):
        num[a[i]*j] += 1

ans = 0
for i in range(n):
    if num[a[i]] < 2:
        ans += 1

# print(num[:30])
print(ans)

Submission status: Time Limit Exceeded

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

count = [0] * (max(A)+1)
for a in A:    
    if count[a] != 0:
        count[a] = 2
        continue

    for j in range(a, max(A)+1, a):
        count[j] += 1

ans = 0
for a in A:
    if count[a] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

count = [0] * (max(A)+1)
for i in range(len(A)):
    a = A[i]
    
    if count[a] != 0:
        count[a] = 2
        continue

    for j in range(a, max(A)+1, a):
        count[j] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        dp[(x-1) + i] += 1
        i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

    a.sort()
    dic = {}
    for i in range(n):
        ai_v = dic.setdefault(a[i], 0)
        dic[a[i]] = ai_v + 1

    cnt = 0
    for i in range(n):
        ai = a[i]
        # 重複は無視
        if dic[ai] > 1:
            continue
        if i == 0:
            cnt += 1
            continue

        divisible = False
        neglect_cnt = 0
        for j in range(i):
            if neglect_cnt > 0:
                neglect_cnt -= 1
                continue
            ajcnt = dic[a[j]]
            if ajcnt > 1:
                neglect_cnt = ajcnt - 1
            if ai < a[j] * 2:
                break
            if ai % a[j] == 0:
                divisible = True
                break
        if not divisible:
            cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

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

    a.sort()
    dic = {}
    for i in range(n):
        ai_v = dic.setdefault(a[i], 0)
        dic[a[i]] = ai_v + 1

    cnt = 0
    for i in range(n):
        ai = a[i]
        # 重複は無視
        if dic[ai] > 1:
            continue
        if i == 0:
            cnt += 1
            continue

        divisible = False
        for j in range(i):
            if ai < a[j] * 2:
                break
            if ai % a[j] == 0:
                divisible = True
                break
        if not divisible:
            cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

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

    a.sort()
    dic = {}
    for i in range(n):
        ai_v = dic.setdefault(a[i], 0)
        dic[a[i]] = ai_v + 1

    cnt = 0
    for i in range(n):
        ai = a[i]
        # 重複は無視
        if dic[ai] > 1:
            continue
        if i == 0:
            cnt += 1
            continue

        divisible = False
        for j in range(i):
            if ai % a[j] == 0:
                divisible = True
                break
        if not divisible:
            cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
C=[]
while len(A)>0:
    c=len(A)
    a=A[0]
    if len(A)>1 and A[1]==a:
        pass
    else:
        C.append(a)
    A=[A[j] for j in range(c) if A[j]%a!=0]
print(len(C))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
C=[]
i=0
while len(A)>0:
    c=len(A)
    a=A[0]
    del A[0]
    if a not in A:
        C.append(a)
    A=[A[j] for j in range(c-1) if A[j]%a!=0]
print(len(C))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=set(A)
F=[]
for a in S:
    if A.count(a)==1:
        F.append(a)
T=0
for a in F:
    c=0
    for l in S:
        if a%l==0 and a!=l:
            c=1
            break
    if c==0:
        T+=1
print(T)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in l:
    for j in range(i+i,lim,i):
      num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_4
# CreatedDate:  2020-07-20 00:18:24 +0900
# LastModified: 2020-07-20 00:49:48 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = sorted(map(int, input().split()))
    ans = [1 if i in A else 0 for i in range(A[-1]+1)]
    for i, a in enumerate(A):
        if ans[a] == 0:
            continue
        for s in range(a+a, A[-1]+1, a):
            ans[s] = 0
        if i < n-1 and A[i] == A[i+1]:
            ans[A[i]] = 0

    print(sum(ans))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_4
# CreatedDate:  2020-07-20 00:18:24 +0900
# LastModified: 2020-07-20 00:35:29 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = sorted(map(int, input().split()))
    ans = [1 if i in A else 0 for i in range(A[-1]+1)]
    for i, a in enumerate(A):
        if ans[a] == 0:
            continue
        for j in range(i+1, n):
            if A[j]%a == 0:
                ans[A[j]] = 0

    print(sum(ans))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

cnt = n
for i in range(n):
	if a.count(a[i]) > 1:
		cnt -= 1
		continue
	for j in range(n):
		if i <= j:
			break
		if a[i] % a[j] == 0:
			cnt -= 1
			break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
nall = list(range(n))
table = []

for j in nall:
	table.append([(aa % a[j] == 0) for aa in a])

transposed = map(list, zip(*table))

cnt = 0
for i in transposed:
	if i.count(True) <= 1:
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
nall = list(range(n))
table = []

for j in nall:
	table.append([aa % a[j] for aa in a])

transposed = map(list, zip(*table))

cnt = 0
for i in transposed:
	if i.count(0) <= 1:
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

nall = list(range(n))

cnt = n
for i in nall:
	for j in nall:
		if i == j:
			continue
		if a[i] % a[j] == 0:
			cnt -= 1
			break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, product
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353

import sys
import numpy as np
import scipy
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, permutations, product
from functools import lru_cache
from math import sin, cos, tan, asin, acos, atan
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353


class NumberTheory():
  def __init__(self, n=2*10**6, numpy=True):
    self.n = n
    self.np_flg = numpy 
    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)
  
  def sieve_of_eratosthenes(self, n):
    if self.np_flg:
      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0
      for i in range(2, int(n**.5)+1):
        if sieve[i]: sieve[i*2::i] = 0
      prime_numbers = np.flatnonzero(sieve)
    else:
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
    return sieve, prime_numbers 

  def prime_factorize(self, n):
    res = dict()
    if n < 2: return res
    border = int(n**.5)
    for p in self.prime_numbers:
      if p > border: break
      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
      if n == 1: return res
    res[n] = 1; return res

  def prime_factorize_factorial(self, n):
    res = dict()
    for i in range(2, n+1):
      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c
    return res
  
  @staticmethod
  def gcd(a, b): return gcd(b, a%b) if b else abs(a)

  @staticmethod
  def lcm(a, b): return abs(a // gcd(a, b) * b)

  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return divisors
  
  @staticmethod
  def base_convert(n, b): # return string
    if not n: return '0'
    res = ''
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res += str(r)
    return res[::-1]


class UnionFind():
  def __init__(self, n=10**6):
    self.root = list(range(n))
    self.height = [0] * n 
    self.size = [1] * n 
  
  def find_root(self, u):
    if self.root[u] == u: return u
    self.root[u] = self.find_root(self.root[u])
    return self.root[u]
  
  def unite(self, u, v):
    ru = self.find_root(u)
    rv = self.find_root(v)
    if ru == rv: return 
    hu = self.height[ru]
    hv = self.height[rv]
    if hu >= hv:
      self.root[rv] = ru 
      self.size[ru] += self.size[rv]
      self.height[ru] = max(hu, hv+1)
    else:
      self.root[ru] = rv 
      self.size[rv] += self.size[ru]


class Combinatorics():
  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):
    self.mod = mod
    self.nCr = dict()
    self.np_flg=numpy
    self.make_mod_tables(N, n)

  sys.setrecursionlimit(10**6)
  def choose(self, n, r, mod=None): # no mod, or mod ≠ prime
    if r > n or r < 0: return 0
    if r == 0: return 1
    if (n, r) in self.nCr: return self.nCr[(n, r)]
    if not mod:
      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))
    else:
      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod
    return self.nCr[(n,r)]
  
  def cumprod(self, a):
    p = self.mod
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p
    return np.ravel(a)[:l]

  def make_mod_tables(self, N, n):
    p = self.mod
    if self.np_flg:
      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = self.cumprod(ifac)[n::-1]
      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;
      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
      n_choose = [None] * (n+1); n_choose[0] = 1
      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p
      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p
    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose


def z_algorithm(s):
  n = len(s)
  a = [0] * n; a[0] = n
  l = r = -1
  for i in range(1, n):
    if r >= i: a[i] = min(a[i-l], r-i)
    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
    if i+a[i] >= r: l, r = i, i+a[i]
  return a


class ABC001():
  def A():
    h1, h2 = map(int, sys.stdin.read().split())
    print(h1-h2)

  def B(): pass
  def C(): pass 
  def D(): pass 


class ABC002():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(max(x, y))

  def B():
    vowels = set('aeiou')
    s = sys.stdin.readline().rstrip() 
    t = ''
    for c in s:
      if c in vowels: continue 
      t += c 
    print(t)

  def C():
    *coords, = map(int, sys.stdin.readline().split())
    def triangle_area(x0, y0, x1, y1, x2, y2):
      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;
      return abs(x1*y2 - x2*y1) / 2
    print(triangle_area(*coords))

  def D():
    n, m = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(m):
      x, y = map(int, sys.stdin.readline().split())
      x -= 1; y -= 1
      edges.add((x, y))
    cand = []
    for i in range(1, 1<<n):
      s = [j for j in range(n) if i>>j & 1]
      for x, y in combinations(s, 2):
        if (x, y) not in edges: break
      else:
        cand.append(len(s))
    print(max(cand))


class ABC003():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)*5000)

  def B():
    atcoder = set('atcoder')
    s, t = sys.stdin.read().split()
    for i in range(len(s)):
      if s[i] == t[i]: continue
      if s[i] == '@' and t[i] in atcoder: continue 
      if t[i] == '@' and s[i] in atcoder: continue
      print('You will lose')
      return 
    print('You can win')

  def C():
    n, k, *r = map(int, sys.stdin.read().split())
    res = 0
    for x in sorted(r)[-k:]:
      res = (res+x) / 2
    print(res)

  def D(): pass 


class ABC004():
  def A():
    print(int(sys.stdin.readline().rstrip())*2)

  def B():
    c = [sys.stdin.readline().rstrip() for _ in range(4)]
    for l in c[::-1]:
      print(l[::-1])

  def C():
    n = int(sys.stdin.readline().rstrip())
    n %= 30
    res = list(range(1, 7))
    for i in range(n):
      i %= 5
      res[i], res[i+1] = res[i+1], res[i]
    print(''.join(map(str, res)))

  def D(): pass 


class ABC005():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(y//x)

  def B():
    n, *t = map(int, sys.stdin.read().split())
    print(min(t))

  def C():
    t = int(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    m = int(sys.stdin.readline().rstrip())
    b = [int(x) for x in sys.stdin.readline().split()]
    i = 0
    for p in b:
      if i == n: print('no'); return 
      while p-a[i] > t:
        i += 1
        if i == n: print('no'); return 
      if a[i] > p: print('no'); return 
      i += 1
    print('yes')

  def D():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros((n+1, n+1), dtype=np.int64)
    for y in range(1, n+1):
      for x in range(1, n+1):
        max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
    res = np.arange(n**2+1)[:, None]
    i = np.arange(1, n+1)
    res = max_del[i, np.minimum(res//i, n)].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')


class ABC006():
  def A():
    n = sys.stdin.readline().rstrip()
    if '3' in n: print('YES')
    elif int(n)%3 == 0: print('YES')
    else: print('NO')

  def B():
    mod = 10007
    t = [0, 0, 1]
    for _ in range(1001001):
      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod
    n = int(sys.stdin.readline().rstrip())
    print(t[n-1])
    
  def C():
    n, m = map(int, sys.stdin.readline().split())
    cnt = [0, 0, 0]
    if m == 1: cnt = [-1, -1, -1]
    else:
      if m & 1: m -= 3; cnt[1] += 1; n -= 1
      cnt[2] = m//2 - n 
      cnt[0] = n - cnt[2]
    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
    else: print(*cnt, sep=' ')
      
  def D():
    n, *c = map(int, sys.stdin.read().split())
    inf = float('inf')
    lis = [inf]*n 
    for x in c: lis[bi_l(lis, x)] = x 
    print(n - bi_l(lis, inf))


class ABC007():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n-1)

  def B():
    s = sys.stdin.readline().rstrip()
    if s == 'a': print(-1)
    else: print('a')

  def C():
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())
    sy -= 1; sx -=1; gy -= 1; gx -= 1
    maze = [sys.stdin.readline().rstrip() for _ in range(r)]
    queue = deque([(sy, sx)])
    dist = np.full((r, c), np.inf); dist[sy, sx] = 0
    while queue:
      y, x = queue.popleft()
      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i += y; j += x
        if maze[i][j] == '#' or dist[i, j] != np.inf: continue 
        dist[i, j] = dist[y, x] + 1
        queue.append((i, j))
    print(int(dist[gy, gx]))
  
  def D(): pass 


class ABC008():
  def A():
    s, t = map(int, sys.stdin.readline().split())
    print(t-s+1)

  def B():
    n, *s = sys.stdin.read().split()
    res = defaultdict(int)
    for name in s: res[name] += 1
    print(sorted(res.items(), key=lambda x: x[1])[-1][0])

  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    c = n - np.count_nonzero(a[:, None]%a, axis=1)
    print(np.sum((c+1)//2/c))
  
  def D(): pass

class ABC009():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)//2)

  def B():
    n, *a = map(int, sys.stdin.read().split())
    print(sorted(set(a))[-2])
    
  def C():
    n, k = map(int, sys.stdin.readline().split())
    s = list(sys.stdin.readline().rstrip())
    cost = [1]*n
    r = k
    for i in range(n-1):
      q = []
      for j in range(i+1, n):
        if s[j] < s[i] and cost[i]+cost[j] <= r:
          heappush(q, (s[j], cost[i]+cost[j], -j))
      if not q: continue
      _, c, j = heappop(q); j = -j 
      s[i], s[j] = s[j], s[i]
      r -= c 
      cost[i] = cost[j] = 0
    print(''.join(s))
      
  def D(): pass 


class ABC010():
  def A():
    print(sys.stdin.readline().rstrip()+'pp')
  def B():
    n, *a = map(int, sys.stdin.read().split())
    tot = 0
    for x in a:
      c = 0 
      while x%2==0 or x%3==2:
        x -= 1
        c += 1
      tot += c
    print(tot)

  def C():
    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
    x, y = np.array(xy).reshape(-1, 2).T
    def dist(x1, y1, x2, y2):
      return np.sqrt((x2-x1)**2 + (y2-y1)**2)
    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
    print(ans)

  def D(): pass 

class ABC011():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n%12+1)

  def B():
    s = sys.stdin.readline().rstrip() 
    print(s[0].upper()+s[1:].lower())

  def C():
    n, *ng = map(int, sys.stdin.read().split())
    ng = set(ng)
    if n in ng: print('NO')
    else:
      r = 100
      while n > 0:
        if r == 0: print('NO'); return
        for i in range(3, 0, -1):
          if (n-i) in ng: continue 
          n -= i
          r -= 1
          break 
        else: print('NO'); return 
      print('YES')

  def D(): pass 


class ABC170():
  def A():
    x = [int(x) for x in sys.stdin.readline().split()]
    for i in range(5):
      if x[i] != i+1:
        print(i+1)
        break

  def B():
    x, y = map(int, sys.stdin.readline().split())
    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
      
  def C():
    x, n, *p = map(int, sys.stdin.read().split())
    a = list(set(range(102)) - set(p))
    a = [(abs(y-x), y) for y in a]
    print(sorted(a)[0][1])

  def D():
    number_theory = NumberTheory()
    n, *a = map(int, sys.stdin.read().split())
    a.sort()
    c = Counter(a)
    tmp = set()
    cnt = 0
    for x in a:
      cnt += c[x] == 1 and not tmp&set(number_theory.find_divisors(x))
      tmp.add(x)
    print(cnt)

  def E(): pass 
  def F(): pass 

if __name__ == '__main__':
  ABC170.D()

Submission status: Time Limit Exceeded

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

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

dp = [-1] * (A[-1]+1)
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] != -1:
        continue

    if A.count(a) == 1:
        ans += 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.array([-1] * (A[-1]+1))
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] != -1:
        continue

    if dp[a] == -1 and A.count(a) == 1:
        ans += 1
        dp[range(a+a, A[-1]+1, a)] = 0

print(ans)

Submission status: Time Limit Exceeded

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

dp = [-1] * (A[-1]+1)
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] == -1 and A.count(a) == 1:
        ans += 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0
    else:
        continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solution():
    length = int(input())
    user_input = input()
    num_list = [int(x) for x in user_input.split()]
    result = 0
    for i in range(length):
        success = True 
        for j in range(length):
            if i == j:
                continue
            if num_list[i] % num_list[j] == 0:
                success = False 
                break
        if success:
            result += 1
    
    print(result)

solution()

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===

eps = 10 ** (-9)


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

    seta = set(a)
    cnta = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        if cnta[n] > 1:
            return True
        if n == 1:
            return False
            
        if 1 in seta:
            return True

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

        return False

    ans = 0
    for ai in list(seta):
        if not make_divisors(ai):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()