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

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

A = numpy.array(A)
c = 0
size = A.size
for a in A.tolist():
    if A[a % A > 0].size == size - 1:
        c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
l = list(map(int,input().split()))
#print(n)
#print(l)

ans = 0
for i in range(n):
    for j in range(n):
        if i != j:
            if l[i] % l[j] == 0:
                break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())
lis=list(map(int, input().split()))
lis.sort()
arr=np.array(lis)
ans=0
ok=[]
f=0
arr_se=np.array(list(set(lis)))

for i in range(0,N-1):
    if lis[i]==lis[i+1]:
        f=1
    elif f:
        f=0
        if lis[i]==lis[i+1]:
            f=1
            
    else:
    
        if np.count_nonzero(lis[i]%arr_se==0) == 1:
            ans+=1
    
if f==0:
    if np.count_nonzero(lis[-1]%arr_se==0) == 1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    list = [0]*len(a)

    count = 0

    for i in range(len(a)):
        if list[i]==0:
            for j in range(i+1,len(a)):
                if list[j] == 0:
                    if a[j] == a[i]:
                        list[i]=1
                        list[j]=1
                if a[j] % a[i] ==0:
                    list[j]=1
            if list[i] == 0:
                count+=1

    print(count)

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
import heapq
heapq.heapify(A)
while A != []:
    a = heapq.heappop(A)
    ans += 1
    AA = []
    if a in A:
        ans -= 1
    for i in range(len(A)):
        if not (A[i] % a == 0):
            AA.append(A[i])
    A = AA
print(ans)

Submission status: Time Limit Exceeded

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

A.sort()
A_set = set(A)
count = 0
last_num = 0
flag = True
now_num = 0

count_flag = False

if A.count(1) == 1:
    print(1)
    exit()
for i in range(N):
    count_flag = True
    now_num = A[i]

    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:
        for j in range(0, i):
            if now_num % A[j] == 0:
                count_flag = False
                break
        if count_flag:
            if not flag:
                flag = True
            count += 1
        last_num = A[i]
print(count)

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 = [a[0]]
for i in range(1, n):
    num = a[i]
    for item in tmp:
        if num%item==0:
            break
    else:
        tmp.append(num)
tmp = set(tmp) - s
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()))
B = []
while True:
    if not A:
        break
    p = A[0]
    if A.count(p) == 1:
        B.append(p)
    A = [e for e in A if e % p !=0]
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n = int(input())
a=list(map(int,input().split()))
a=sorted(a)
c=Counter(a)
x=set()
for i in range(n):
    x.add(a[i])
ans = 0
for i in range(n):
    if c[a[i]]>1:
        continue
    l=make_divisors(a[i])
    x.remove(a[i])
    f=1
    for r in l:
        if r in x:
            f=0
            break
    if f:
        ans += 1
    x.add(a[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = 0
tmp = np.array([0]*n)
for i in range(n):
    tmp = np.array([a[i]]*n)
    #print(tmp)
    tmp = tmp % a
    #print(tmp)
    if n - np.count_nonzero(tmp) == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n =(int)(input())
str=input().split(" ")
a=[(int)(str[i]) for i in range(n)]
flg=[True for i in range(n)]
a.sort()
count=0
for i in range(n):
    if(not(flg[i])):
        continue
    if(i==n-1 or a[i]!=a[i+1]):
        count+=1
    for j in range(i+1,n):
        if(flg[i] and a[j]%a[i]==0):
            flg[j]=False
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    A.sort()
    c = Counter(A)
    ans = []
    for i in range(N):
        for a in ans:
            if A[i] % a == 0:
                break
        else:
            ans.append(A[i])

    print(len([a for a in ans if c[a] == 1]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
#a = list(set(a))
#n = len(a)
ans = 0
for i in range(n):
    flag = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

k=0
while k<=len(alist)-1:
    unit = alist[k]
    ls =  [i for i in alist if i%unit!=0]
    alist = [unit] + ls
    k+=1

choufuku = 0
for num in alist:
    choufukulist = [x for x in set(alistold) if alistold.count(x) > 1]
    if num in choufukulist:
        choufuku += 1

print(k-choufuku)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
  for j in a:
    b.append(i%j)
  if b.count(0)>1:
    n-=1
  b=[]
print(n)

Submission status: Time Limit Exceeded

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

ans = 0
  
while True:
  d = A.pop(0)
  if d in A:
    ans -= 1
  
  for a in A[::-1]:
    if a % d == 0:
      A.remove(a)
  ans += 1
  if A:
    True
  else:
    break
  
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l = [int(x) for x in input().split()]
l.sort()
mp = [1]*n
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if(l[j]==l[i]):
            mp[i] = 0
        if(l[j]%l[i]==0):
            mp[j] = 0
print(sum(mp))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

alist.sort(reverse = False)

i = 0
count = 0

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

  if alist.count(alist[i]) >= 2:
    count += 1
    
  while j < len(alist):
    if alist[j] % a == 0:
      del alist[j]
    else:
      j += 1
   
  i += 1
  
print(len(alist) - count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
# n=10**5
# a=[i for i in range(2,10**5+2)]
# print(len(a))
a.sort()
tmp=Counter(a)
p=[]
while 1:
    if len(a)==0:
        break
    prime=a[0]
    if tmp[prime]!=1:
        a.pop(0)
        continue
    p.append(prime)
    i=0
    while i <len(a):
        if a[i]%prime==0:
            a.pop(i)
            continue
        i+=1
    # print(a)
    # print(p)
for i in a:
    p.append(i)
print(len(p))
# def eratosthenes(limit):
#     A = [i for i in range(2, limit+1)]
#     # A=a[:]
#     P = []
#     time = 0
#     while True:
#         prime = min(A)
#         if prime > math.sqrt(limit):
#             break  
#         P.append(prime)   
#         i = 0
#         while i < len(A):
#             if A[i] % prime == 0:
#                 A.pop(i)
#                 continue
#             i += 1    
#     for a in A:
#         P.append(a)    
#     return len(P)
# print(a)
# tmp=Counter(a)
# lst=[]
# for i in range(n):
#     if tmp[a[i]]!=1:
#         continue
#     for j in lst:
#         if a[i]%j==0:
#             break
#     else:
#         lst.append(a[i])
# print(len(lst))
# print(eratosthenes(10**5+10))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
while len(l) > 0:
    tmp = l[0]
    if len(l) >= 2 and l[0] == l[1]:
        cnt -= 1
    for i in range(len(l)):
        if l[i]%tmp == 0:
            l[i] = 0
    cnt += 1
    l = [x for x in l if x != 0]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = sorted(map(int, input().split()))

flgs = [True] * N
for i in range(N):
    if flgs[i]:
        for j in range(i+1, N):
            if As[j] == As[i]:
                flgs[i] = False
                flgs[j] = False
            elif As[j] % As[i] == 0:
                flgs[j] = False

print(flgs.count(True))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
if 1 in arr:
    if arr.count(1)>1:
        print(0)
        quit()
    else:
        print(1)
        quit()
d={}
ans=0
for i in arr:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
for i in range(n):
    x=arr[i]
    if d[x]==1:
        f=1
        for j in range(2,int(x**0.5)+1):
            y=x//j
            if (j in d and x%j==0) or ( y in d and x%(y)==0):
                f=0
                break
        if f==1:
             ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

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

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:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b=set()
kas=set()
for i in a:
    if len(b)==0:
        b.add(i)
    elif i in b:
        kas.add(i)
    else:
        flag= True
        for j in b:
            if i % j ==0:
                flag=False
                break                
        if flag:
            b.add(i)
print(len(b)-len(kas))

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
for i in range(n):
    k=a[i]
    c=True
    for j in range(n):
        if i==j:
            continue
        if k%a[j]==0:
            c=False
            break
    if c:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(n):
    for j in range(n):
        if i==j:
            continue

        if a[i]%a[j]==0:
            break
    else:
        cnt += 1
    continue

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
cnt=0
l={}
for i in range(n-1):
    if a[i] in l:
        cnt+=1
        continue
    else:
        l[a[i]]=1
    for j in range(i+1,n):
        if a[i]%a[j]==0:
            cnt+=1
            break
if a[-1] in l:
    cnt+=1
print(n-cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

n = I()
l = LI()
list.sort(l, reverse=True)
c = 0
for a in range(n):
  for b in range(n):
    if a == b:
      continue
    if l[a] % l[b] == 0:
      break
  else:
    c += 1
  
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())#
*a,=map(int, input().split())
sa=Counter(a)

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ad=True

    for i in range(1,min(int(ai**(1/2)+7),ai)):
        if ai%i==0:
            if i in sa and i!=ai:
                ad=False
                break
            if i>1 and ai//i in sa:
                ad=False
                break
    if ad:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

result = 0
n_list_a = set(n_list)

result = []
for i in n_list:
    d_flag = 0
    if n_list.count(i) > 1:
        d_flag = 1
    for j in n_list_a:
        if (i != j) and (i % j == 0):
            d_flag = 1
    if d_flag == 0:
        result.append(i)

print(len(result))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        break
    for j in range(i+1,n):
        if done[j] != 1:
            if li[j]==li[i]:
                done[i]=0
                done[j]=0
                dp[i]=0
                dp[j]=0
            elif li[j]%li[i]==0:
                done[j]=0
                dp[j]=0
 
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
result=[0]*N

for i in range(N):
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            result[i]+=1
            break
print(result.count(0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for x in range(n):
    c = a.pop()
    if c == d:
        continue
    else:
        temp = 1
        for y in a:
            if c % y == 0:
                temp = 0
                break
        answer += temp
        d = c

print(answer)

Submission status: Time Limit Exceeded

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


A.sort()

count = 0
B = []
for i in range(N):
    temp = A[i]
    if i != (N - 1):
        if A[i] == A[i + 1]:
            count += 1
            if temp not in B:
                B.append(temp)
            continue
    if i == 0:
        pass
    else:

        for j in range(len(B)):
            if A[i] % B[j] == 0:
                count += 1
                break
    B.append(temp)

print(N - count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    n= int(input())
    inlis = list(map(int, input().split()))
    inlis.sort()
    for num in inlis:
        new = [e for e in inlis if e % num == 0]
        new.sort()
        #print(new)
        if len(new) > 1:
            if new[0] != new[1]:
                for i in range(1, len(new)):
                    inlis.remove(new[i])
            else:
                for i in range(0, len(new)):
                    inlis.remove(new[i])
            

    print(len(inlis))

    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

setA = set(A)
result = 0
for i in range(N):
    divisors = make_divisors(A[i])

    B = copy.copy(A)
    B[i] = 0
    setA = set(B)

    for d in divisors:
        if d in setA:
            break
    else:
        result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
#一行で入力された数値をリストに
notans = 0
for i in range(n):
    for j in range(n):
        if a[i]%a[j]==0 and i!=j:
            notans += 1
            break

print(n-notans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    count = int(input())
    integars = sorted(int(x) for x in input().split())
    ans = 0
    for i, x in enumerate(integars):
        chosen = True
        for j, y in enumerate(integars):
            if i == j:
                continue
            elif i + 1 < j:
                break
            elif x % y == 0:
                chosen = False
                break
        if chosen:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math

sys.setrecursionlimit(10 ** 6)

# Made for abc097D
class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self, i, j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip] += 1

    def same(self, i, j):
        return self.ancestor(i) == self.ancestor(j)

    def __str__(self):
        parentDict = { }
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = "===UnionFind description===\nSize:" + str(self.size) + "\nGroupCount:" + str(
            len(parentDict)) + "\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements += " " + str(elem) + ","
            result += "Group-"+str(k)+"(Count:"+str(len(parentDict[k]))+"):["+elements+"]\n"
        return result

def debug(s):
    if False:
        print(s)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    debug(f"Sorted: {A}")
    found = []
    c = 0
    i = 0
    while i < len(A):
        if i < len(A)-1 and A[i] == A[i+1]:
            found.append(A[i])
            ni = i+1
            while A[ni] == A[i]:
                if len(A)-1 == ni:
                    ni = len(A)
                    break
                ni += 1
            debug(f"i was skipped from {i} to {ni}")
            i = ni
            continue
        else:
            contained = False
            for f in found:
                if A[i] % f == 0:
                    debug(f"{A[i]} was divided with {f}")
                    contained = True
                    break
            if not contained:
                debug(f"{A[i]} is not contained appending")
                c+=1
                found.append(A[i])
            i+=1
    print(c)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set(A)
    tmp2 = []
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if ok or p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        #print(v, ok)
        if not ok:
            for t in A:
                if t == v:
                    continue
                #if ok or t * t > v:
                #    break
                if v % t == 0:
                    ok = True
                    break
        if ok:
            pass
        else:
            #tmp.add(v)
            #tmp2.append(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

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]
    a = list(set(a))
    a.sort()

    answer = 0
    divisors = set()
    for i in range(len(a)):
        judge = True
        for divisor in divisors:
            if a[i] % divisor == 0:
                judge = False
                break
        if judge:
            divisors.add(a[i])
            if (a[i] in duplicate):
                continue
            answer += 1

    print(answer)


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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

A.sort()
ans=0

B=[1]*N

#print(A)
for i in range(N):
    flg=True
    if B[i] == 1:
        for j in range(1,N-i):
            if A[j+i]%A[i]==0:
                B[j+i]=0
                if A[i]==A[j+i]:
                    B[i]=0
    #print(B)

print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Nmax = 10**6+1

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

prime = [0]*Nmax
for i in range(N):
    if prime[A[i]] == 0:
        prime[A[i]] = 1
    else:
        prime[A[i]] = -1

for a in A:
    if prime[a] != 0:
        for q in range(a*2, Nmax, a):
            prime[q] = 0



print(sum(a for a in prime if a == 1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    # a.sort()
    # from collections import deque
    import heapq
    from collections import Counter
    heapq.heapify(a)
    ans = []
    cnt = Counter(a)

    for i in range(n):
        if len(a) == 0:
            break

        tmp = heapq.heappop(a)

        tmpary = []
        for j in range(len(a)):
            tmp2 = heapq.heappop(a)
            # print(tmp,tmp2)

            if tmp2 % tmp == 0:
                # print(tmp,tmp2)
                # print(a)
                continue
            else:
                tmpary.append(tmp2)
        heapq.heapify(tmpary)
        a = tmpary
        if cnt[tmp] > 1:
            continue

        ans.append(tmp)
        # print(a)
        # print(tmp)

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

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

counta = 0

for index, num in enumerate(A):
    tmp_list = copy.deepcopy(A)
    del tmp_list[index]

    for tmp in tmp_list:
        if num % tmp == 0:
            break
    else:
        counta += 1

print(counta)

Submission status: Time Limit Exceeded

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

    A.sort()

    ans = 0
    modlist = list()
    ignor = list()
    for i in range(N):
        flag = True
        for j, m in enumerate(modlist):
            if A[i] in ignor:
                flag = False
                break
            if m == A[i]:
                ignor.append(A[i])
                ans -= 1
                flag = False
                break

            if A[i] % m == 0:
                flag = False
                break
        if flag:
            modlist.append(A[i])
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a_sorted = sorted(a)
divisible_list = [True] * n
for i in range(n-1):
    if not divisible_list[i]:
        continue
    for j in range(i+1, n):
        if a_sorted[j] == a_sorted[i]:
            divisible_list[i] = False
            divisible_list[j] = False
        if a_sorted[j] % a_sorted[i] == 0:
            divisible_list[j] = False
print(sum(divisible_list))

Submission status: Time Limit Exceeded

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

A.sort()
count = 0
for i in range(n - 1):
    if A[i] % A[i + 1] == 0:
        count += 1
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            count += 1
            break
i = n - 1
for j in range(i):
    if A[i] % A[j] == 0:
        count += 1
        break
print(n - count)