Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
An = list(map(int, input().split()))
ans = 0
ng = set()
a_An = np.array(An)
for i, a in enumerate(An):
    temp = a_An / a
    check = np.where(temp%1 == 0)
    check = np.delete(check, np.where(check==i))
    check = check[check != i]
    if len(check) > 0:
        ng = ng | set(check)
print(N-len(ng))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

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

counter=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        elif A[i]%A[j] == 0:
            break
    else:
        counter = counter+1
        
print(counter)

Submission status: Time Limit Exceeded

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

Num = 0
for i in range(N):
    for j in range(N):
        if i != j and L[i] % L[j] == 0:break
        if j == N-1:Num += 1
        
print(Num)

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

# 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]

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

ans = 0
for a in A:
    flag = True
    # da = make_divisors(a)
    da = divisor(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

    # divisors.sort()
    return sorted(divisors)

n = int(input())
A = sorted(tuple(map(int, input().split())))
if n ==1:
    print(1)
    exit()
if A[0] == 1:
    if A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = []
    tyo = []
    for i in range(n):
        flag = True
        if A[i] in tyo:
            continue
        tmp = make_divisors(A[i])
        for x in tmp:
            if x in ans:
                flag = False
                break
        if not flag:
            continue


        if i<n-1:
            if A[i+1] == A[i]:
                tyo.append(A[i])
                continue
        ans.append(A[i])
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right


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()))
    A.sort()
    ans = 0

    for a in A:
        flag = False
        left = bisect_left(A, a)
        right = bisect_right(A, a)

        if right-left > 1:
            continue

        divs = make_divisors(a)
        for d in divs:
            left = bisect_left(A, d)
            right = bisect_right(A, d)
            if left != right and d != a:
                flag = True
                break

        if flag == False:
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    for i in range(n):
        i_value = a_list[i]
        fail = False
        for j in range(0, min(i + 2, n)):
            if i == j:
                continue
            j_value = a_list[j]
            q, mod = divmod(i_value, j_value)
            if mod == 0:
                fail = True
                break
        if not fail:
            count += 1

    print(count)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())

    ctr = Counter(A)
    memo = set()
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break

        if ctr[a] == 1:
            for i in range(1, int(a ** 0.5) + 1):
                if a % i == 0 and ((i in memo) or (a // i in memo)):
                    break
            else:
                ans += 1

        memo.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

memo = {}
def make_divisors(n):
    if n in memo:
        return memo[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
    
    memo[n] = lower_divisors + upper_divisors[::-1]
    return memo[n]

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)

ans = 0

for i,a in enumerate(B):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            continue
        elif d in keys:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
a_i = list(map(int, input().split()))
a_i.sort()
ans = 0
for x in range(num):
    val = a_i[x]
    for y in range(num):
        val2 = a_i[y]
        if x == y and y != num - 1 and val2 == a_i[y + 1]: 
            ans += 1
            break
        elif x == y: break
        elif val % val2 == 0:
            ans += 1
            break
print(num - ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
As = list(map(int, input().split()))
count = sorted(Counter(As).items(), key = lambda x: x[0])

ans = 0
for num, c in count:
  if c > 1:
    continue
  flag = True
  for i, c2 in count:
    if i == num:
      break
    if num % i == 0:
      flag = False
      break
  if flag:
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            yakusu.append(i)
            if n // i != i:
                yakusu.append(n//i)
    return yakusu
     
baisu = [False] * (10**6 + 1)
def main():
    N = I()
    A = LI()

    ok = 0
    for a in A:
        if baisu[a]:
            continue
        if not baisu[a]:
            num = a + a
            while num < 10**6+1:
                baisu[num] = True
                num += a
    s = collections.Counter(A)
    for a in A:
        if not baisu[a]:
            if s[a] > 1:
                continue
            ok += 1
    print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
L = [0] * (10 ** 6 + 1)
S = set()

for a in A:
    if a in S:
        L[a] = 1
    S.add(a)
    for i in range(2, 10 ** 6 + 1):
        if a * i > 10 ** 6:
            break
        L[a * i] = 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()

di = Counter(A)
A.sort()

ans = 0
l = []
for item in A:
    flag = True
    for i in l:
        if item%i == 0:
            flag = False
            break
    if flag:
        l.append(item)
        if di[item] == 1:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    ans = 0
    flag = False
    while len(A) != 0:
        ans += 1
        tmp = A.pop(0)
        #print(A)
        k = 0
        for i in range(len(A)):
            if A[i-k] % tmp == 0:
                if A[i-k] == tmp:
                    flag = True
                A.remove(A[i-k])
                k += 1
        if flag:
            ans -= 1
            flag = False
        
    print(ans)


if __name__ == "__main__":
    slove()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
a_list = [int(x) for x in input().split()]
d = defaultdict(int)
for a in a_list:
    d[a] += 1
d_list = sorted(d.keys())
m = len(d_list)
ans = 0
for i in range(m):
    if d[d_list[i]] > 1:
        continue
    for j in range(i):
        if d_list[i] % d_list[j] == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
A = list(map(int,input().split()))
Count = 0
for i in A:
    List = list(map(lambda x: i % x,A))
    c = collections.Counter(List)
    if(c[0] == 1):
        Count += 1

print(str(Count))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len(A)):
  flg = 0
  for j in range(len(A)):
    if (i != j):
      if (A[i] % A[j] == 0):
        flg = 1
  if (flg == 0):
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
from collections import Counter

def factors(n):
    yield from chain.from_iterable(({i, n//i} for i in range(1, int(n ** 0.5) + 1) if n % i == 0))

def get_non_divisible():
    n, *lst = map(int, open(0).read().split())
    c = Counter(lst)
    d = {val: sum((-c.get(f, 0) for f in factors(val)), len(lst)) for val in c}
    res = 0
    for i in lst:
      if d[i] == n - 1:
        res += 1
    return res
  
if __name__ == '__main__':
    print(get_non_divisible())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
E = set()
ans = 0
for i in range(N):
    a = A[i]
    if i < N-1:
        if a == A[i+1]:
            E.add(a)
            continue
    if a in E:
        continue
    Flag = True
    for e in E:
        if a%e == 0:
            Flag = False
    if Flag:
        ans += 1
    E.add(a)
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()
b = [a[0]]
c = []

for i in range(1,len(a)):
    if a[i] in b:
        if a[i] in c:
            continue
        else:
            c.append(a[i])
        continue
    else:
        b.append(a[i])
        for j in range(len(b)-1):
            if a[i] % b[j] == 0:
                b.pop(-1)
                break
print(len(b)-len(c))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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]


divisors_list = []

for i in A:
  divisors_list.append(make_divisors(i))
  
count = 0
for i in range(N):
  B = copy.copy(A)
  del B[i]
  flag = 0
  for j in divisors_list[i]:
    if(j in B):
      flag = 1
      break
  if(flag == 0):
    count += 1
      
      
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
for i, A_i in enumerate(A):
    for A_j in (A[:i] + A[i+1:]):
        if (A_i / A_j) % 1 == 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()
ans=0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

MAX = 10 ** 6
is_divisible = [True] * (MAX + 1)
is_divisible[0] = False
for i in A:
    if not is_divisible[i]:
        continue
    for j in range(i * 2, MAX + 1, i):
        is_divisible[j] = False

for k, v in Counter(A).items():
    if v > 1:
        is_divisible[k] = False

st = {i for i in range(MAX + 1) if is_divisible[i]}
print(len(st & set(A)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math as mt
input=sys.stdin.buffer.readline  
#t=int(input())
mod=10**9+7
t=1
for __ in range(t):
    
    #x,n=map(int,input().split())
    l=[0]*(10**6+1)
    n=int(input())
    #a=[[0 for j in range(m)] for i in range(n)]
    a=list(map(int,input().split()))
    a.sort()
    ans=0
    d={}
    for i in a:
        d[i]=d.get(i,0)+1
    if d[a[0]]==1:
        ans+=1
    for i in range(1,n):
        cnt=0
        if d[a[i]]>1:
            continue
        for j in range(i):
            if a[i]%a[j]!=0:
                cnt+=1
            else:
                break
        if cnt==i:
            ans+=1
    
        
        
    print(ans)

Submission status: Time Limit Exceeded

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

X = [0]*(10**6+10)
for i in A:
    for j in range(i,10**6+1,i):
        X[j] += 1
ans = 0
for i in A:
    if X[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
seta = set(a)
dblchk = set()
dbl = set()
for i in range(n):
  if a[i] not in dblchk:
    dblchk.add(a[i])
  else:
    dbl.add(a[i])
validints = n
for i in range(n):
  if a[i] in dbl:
    validints -= 1
    continue
  for j in range(1,a[i]):
    if a[i]%j==0 and j in seta:
      validints -= 1
      break
print(validints)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
from collections import defaultdict


def main():
    n = int(input().strip())
    a_list = map(int, input().split())

    ans_set = set()
    dup_set = set()
    for a in sorted(a_list):
        if a in ans_set:
            dup_set.add(a)
            continue

        divs = set(make_divisors(a))
        if divs.isdisjoint(ans_set):
            ans_set.add(a)

    print(len(ans_set) - len(dup_set))


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
number=0
judge=0
for i in range(n):
  for j in range(n):
    if i != j:
      if a[i]%a[j]==0:
        judge=1
        break
  if judge==0:
  	number+=1
  judge=0
print(number)

Submission status: Time Limit Exceeded

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

for k in range(1, N):
    if k<N-1:
        if A[k] == A[k+1]:
            continue
    for j in range(k):
        if A[k]%A[j] ==0:
            break
    else:
        count +=1
        #print(A[k])
if N>1:
    if A[0]%A[1] >0:
        count+=1
    
if N ==1:
    count = 1
print(count)

Submission status: Time Limit Exceeded

Solution code:


def resolve():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip())

    a = [int(x) for x in input().rstrip().split()]
    duplicate = [x for x in set(a) if a.count(x) > 1]

    answer = 0
    for i in range(n):
        judge = True
        if(a[i] in duplicate):
            continue
        for j in range(n):
            if i == j:
                continue
            if a[i] % a[j] == 0:
                judge = False
                break
        if judge:
            answer += 1

    print(answer)


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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import math
    from collections import Counter
    N=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    A.sort()

    A_counter=Counter(A)

    L=[]
    count=0
    for a in A:
        if a==0:
            continue
        flag=True
        for s in L:
            if a%s==0:
                flag=False
                break
        if flag:
            L.append(a)
            if A_counter[a]==1:
                count+=1
    
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
idx = np.argsort(A)
A = np.sort(A)

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False
        if flag:
            result += 1
    return result

print(get_result())

Submission status: Time Limit Exceeded

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

count =0
for i in range(N):
    B = A[i] % A
    if np.count_nonzero(B) == N-1:
        count +=1
    
    
print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

sortA = sorted([i for i in A if A.count(i) == 1])

ans = 0

while sortA != []:
    x = sortA.pop(0)
    sortA =[X for X in sortA if X%x != 0]
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
A = list(sorted(A))
result = 0
for i in range(N):
    A_i = A[i]
    if A.count(A_i) > 1:
        continue
    can_divide = False
    for j in range(i):
        A_j = A[j]
        if A_i % A_j == 0:
            can_divide = True
            break
    if not can_divide:
        result += 1

# 結果出力
print(result)

Submission status: Time Limit Exceeded

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

ann = []
for i,a in enumerate(a_list):
  if i<len(a_list)-1 and a==a_list[i+1] and a!=0:
    for j in range(i,len(a_list)):
      if a_list[j]%a==0:
        a_list[j]=0
    continue
  
  if i==0 and a==1:
    print(1)
    exit()

  if a==0:
    continue
  ann.append(a)
  
  for j in range(i,len(a_list)):
    if a_list[j]%a==0:
      a_list[j]=0

print(len(ann))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([a for a in map(int,input().split())], reverse=True)

result = 0
for a in A:
    for b in A[(A.index(a)+1):]:
        if a%b == 0:
            result += 1
            break
print(N-result)

Submission status: Time Limit Exceeded

Solution code:
import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

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

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))

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

def solve(n, a):
    counts = {}
    for item in a:
        if item not in counts:
            counts[item] = 0
        counts[item] += 1
    items_in_a = set(a)
    result = 0
    for item in a:
        d = divisors(item)
        if len(items_in_a.intersection(d)) == 1 and counts[item] == 1:
            result += 1
    return result


if __name__ == "__main__":
    n = int_in()
    a = arr_in()
    out(solve(n, a))

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split -- START --
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l
# Factoring by trial split --- END ---

# Summarize count of factor within list -- START --
def summarizeList(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

def main():
  n=I()
  l=LI()
  l.sort()
  a=[1]*n

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

  # print(a)
  return sum(a)

# main()
print(main())

Submission status: Time Limit Exceeded

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

ans = 0

for i in a:
    cnt = 0
    for j in a:
        if i % j == 0:
            cnt += 1
    if cnt == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table


ans = 0
for i in range(N):
    x, y = a[i], a[:i] + a[i + 1 :]
    if not any(set(divisor(x)) & set(y)):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=0
for i in range(len(a)):
  c=0
  for j in range(len(a)):
    if a[i]%a[j]==0 and i != j:
      c=1
      break
  if c==0:
    b+=1
print(b)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    i = 1
    flg = True
    while i*i <= n:
        if n % i == 0:
            if i in s and i != n:
                flg = False
                break
            ii = n//i
            if i != ii:
                if ii in s and ii != n:
                    flg = False
                    break
        i += 1
    return flg

def main():
    cnt = 0
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        if c[a[i]] > 1:
            continue
        if make_divisors(a[i]):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    s = set(a)
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = (10 ** 6) + 5
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1]:
            prime[A[i]] = False
            for j in range(A[i] * 2, MAX, A[i]):
                prime[j] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
ans2=[-1 for i in range(10**6+1)]
ans=0
for i in range(n):
  x=a[i]
  if ans2[x]==-1:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        ans2[x]=1
      else:
        ans2[x]=0
  else:
    ans+=ans2[x]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
# from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
a = RI()

a.sort()

count = 0

while a:
    flag = False
    m = a[0]
    c = a[1:]
    a = []
    for i in c:
        if i==m:
            if flag:
                count += 1
            else:
                count += 2
                flag = True
        elif i%m==0:
            count += 1
        else:
            a.append(i)

# print(count)

ans = n - count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.append(10**7)


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


s = set()
ans = 0

for i in range(N):
    y = div(A[i])
    sin = y & s
    if len(sin) == 0:
        if A[i] == A[i+1]:
            s.add(A[i])
        else:
            ans += 1
            s.add(A[i])
        
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)

t=0

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


print(n-t)