Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,*a=map(int,open(0).read().split())
    s=set(a)
    import collections
    c=collections.Counter(a)
    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
        return divisors
    ans=0
    for i in a:
        if c[i]>1:
            continue
        l=set(make_divisors(i))
        if l&s=={i}:
            ans+=1
        
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    for i in range(n):
      count_temp = 0
      for k in range(n):
        if i != k and a[i] % a[k] == 0:
        	count_temp += 1
      if count_temp == 0:
        count += 1
    print(count)
  
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

A_sort = sorted(A)
A_counter = Counter(A)

res = 0
# res_list = []
for i in range(len(A_sort)):
    count = 0
    A_sort_tmp = A_sort[:i]

    if A_counter[A_sort[i]] >= 2:
        continue

    for j in range(len(A_sort_tmp)):
        if A_sort[i] % A_sort_tmp[j] != 0:
            count += 1

    if count == len(A_sort_tmp):
        res += 1
        # res_list.append(i + 1)

print(res)
# print(res_list)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
for i in range(0,n):
  temp=0
  if i>1:
    if a[i]==a[i-1]:
      temp=1
  if i<n-1:
    if a[i]==a[i+1]:
      temp=1
  if temp==1:
    ans=ans-1
  else:
    for j in range(0,i):
      if a[i]%a[j]==0:
        ans=ans-1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = set(i for i in range(n))
ans = [0]*n
warizai_index = set()

for i in range(n):
    for wari in warizai_index:
        if a[i]%a[wari] == 0 and i != wari:
            ans[i] = 1
            if i in warizai_index:
                warizai_index.remove(i)
            break
    if ans[i] == 1:
        continue
    
    #for j in b:
    for j in range(n):
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            if i in warizai_index:
                warizai_index.remove(i)
            warizai_index.add(j)
            break

print(ans.count(0))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
A = np.array(A)
result = 0
for a in A:
    if sum(a % A == 0) == 1:
        result += 1

# 結果出力
print(result)

Submission status: Time Limit Exceeded

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

count = 0

for i in a_list:
  a = 0
  for j in a_list:
    if i == j:
      continue
    if i % j == 0:
      break
    a += 1

  if a == (n-1):
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

ans = 0
while(len(a)):
    a_min = a.pop(0)
    if len(a) == 0:
        ans += 1
        break
    if a_min == a[0]:
       ans -= 1 
    a = [el for el in a if el % a_min != 0]
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = [int(x) for x in input().split()]

ans = 0

for i in range(n):
	good = True
	for j in range(n):
		if j != i:
			if a[i] % a[j] == 0:
				good = False
				break
	if good:
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
ans=[l[0]]
c=set()
for i in range(1,a):
  t=True
  if l[i]==ans[-1]:
    c.add(l[i])
  else:
    for j in ans:
      if l[i]<2*j:
        break
      elif l[i]%j==0:
        t=False
        break
    if t:
      ans.append(l[i])
print(len(ans)-len(c))

Submission status: Time Limit Exceeded

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

A.sort()
count = 0

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

print(count)

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()))

counter = Counter(A)

ans = 0
for k, v in counter.items():
    if v != 1:
        continue
    can = True
    for d in make_divisors(k):
        if d == k:
            continue
        if d in counter:
            can = False
    if can:
        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):
    x, y = a[i], a[:i] + a[i + 1 :]
    flag = True
    for b in y:
        if x % b == 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()))
count = 0
for i in range(n):
    hantei = True
    for j in range(n):
        if i == j: continue
        elif a[i] % a[j] == 0: 
            hantei = False
            break
    if hantei == True:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
from collections import Counter
c = Counter(A)
sorted_key = sorted(c.keys(),reverse=True)
res = [0]*len(sorted_key)
#print(sorted_key)
for i,key in enumerate(sorted_key):
    for j in range(len(sorted_key)-1, i, -1):
        #print(i,key,j,sorted_key[j])
        if (key/sorted_key[j]>=1) and (key%sorted_key[j])==0:
            res[i] = 1
            #print('===========',)
            break

#print('res', res)
#print(c)
ans = 0
for i,v in enumerate(sorted_key):
    if res[i]:
        ans += c[v]
    else:
        if c[v] >1:
            ans += c[v]
print(n-ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_fact(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    n = int(input())
    nums = list(map(int,input().split()))
    #prime_factors = list(map(prime_fact,nums))
    #prime_factors_to_s = list(map(str,prime_factors))
    #prime_factors_string = list(map(lambda x:",".join(x),prime_factors_to_s))
    ind = dict()
##    for i in range(n):
##        if not i in ind:
##            ind[nums[i]] = [i] #インデックスを保存
##        else:
##            ind[nums[i]].append(i) #重複も一応……)
    nums.sort()
    undivisable = [True] * n
    counter = 0
    #print(nums)
    for i in range(n-1):

        if not undivisable[i]:
            continue #すでに何かで割られた数はスルー(それより小さい数で割れる)
        divisor = nums[i]
        for j in range(i+1,n):
            if nums[j] % divisor == 0:
                undivisable[j] = False
            if nums[j] == divisor:
                undivisable[i] = False
        #print(nums[i],undivisable)

    print(undivisable.count(True))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ts = {}
fs = set()

for i, a in enumerate(A):
    if a in ts or a in fs:
        continue
    flag = True
    for j, b in enumerate(A):
        if a % b == 0 and i != j:
            fs.add(a)
            flag = False
    if flag:
        ts[a] = ts.get(a, 0)+1

ans = 0
for i in ts:
    ans += ts[i]

print(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])
divider = set()


ans = 0
for num, c in count:
  if c > 1:
    divider.add(num)
    continue
  for i in divider:
    if num % i == 0:
      break
  else:
    divider.add(num)
    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[0]
    sortA =[X for X in sortA if X%x != 0 ]
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
A.sort()
limit = math.sqrt(max(A))
def eratos(A, limit):
    prime = []
    for a in 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())
l=list(map(int,input().split()))
c=0
def isfactors(n):
	for i in range(1,n//2+1):
		if n%i==0 and i in l:
			return False
	return True
for i in l:
	if l.count(i)==1 and isfactors(i):
		c+=1
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
def main():
    N=int(input())
    A=list(map(int,input().split()))
    s=set()
    A.sort()
    a=0
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.5)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
length = int(input())
intList  = input().split()
intList = [int(x) for x in intList]

resultSet = set()
for i in range(length):
    cnt = 0
    for j in range(length):
        if i != j and intList[i] % intList[j] != 0:
            cnt += 1

    if cnt == length - 1:
        resultSet.add(i)

print(len(resultSet))

Submission status: Time Limit Exceeded

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

ans_list = []
for i in range(n):
    f = True
    for j in range(n):
        if i == j:
            continue

        if data[i] % data[j] == 0:
            f = False
            break

    if f:
        ans_list.append(data[i])

print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()
a.sort()

ans = 0
for i in a:
  data = []
  for n in range(1, int(i**0.5)+1):
    if i % n == 0:
      data.append(n)
      if n != i // n:
        data.append(i//n)

  for j in data:
    l = bisect.bisect_left(a, j)
    r = bisect.bisect_right(a, j)
    if i == j:
      if r - l >= 2:
        ans += 1
        break
    else:
      if r - l >= 1:
        ans += 1
        break
print(N - ans)

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
    temp[i] = 0.1
    check = np.where(temp % 1 == 0)
    check = check[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:
n = int(input())
a = list(map(int,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]

div = []
for i in range(n):
    div.append(make_divisors(a[i]))


cnt = 0
for j in range(n):
    f = 1
    for k in range(len(div[j])):
        if k != len(div[j])-1:
            if div[j][k] not in a:
                pass
            else:
                f = 0
                break
        else:
            if a.count(div[j][k]) == 1:
                pass
            else:
                f = 0
    if f:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

count=N

for i in range(N):
  n=A[i]
  B=A.copy()
  B.pop(i)
  for j in range(1, int(n**0.5)+1):
    if n % j == 0:
      if j in B:#count
        #print(n,j)
        count-=1
        break
      if j != n // j:
        if n//j in B:#count
          #print(n,n//j,"//")
          count-=1
          break

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
flags = [1] * n
for i, a in enumerate(A):
    if flags[i]:
        for j, f in enumerate(flags[i+1:], i+1):
            if a == A[j]:
                flags[i] = 0
                flags[j] = 0
            if A[j] % a == 0:
                flags[j] = 0
print(sum(flags))

Submission status: Time Limit Exceeded

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

    divisors.sort()
    return divisors
  

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

for i,num in enumerate(A):
    for div in divisor(num):
        FLG = True
        if div in A[:i] + A[i+1:]:
            FLG = False
            break
    if FLG:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
ret = 0

for i in range(N):
  for j in range(N):
    if (Alist[i] % Alist[j]) == 0:
      if i!=j:
      	break
  if j + 1 == N:
  	ret += 1

print( ret )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()
s = set()
for a in A:
    i = 2
    if a in s:
        continue
    while a * i <= 10 ** 6:
        s.add(a * i)
        i += 1

cnt = Counter(A)
ans = 0
for a in A:
    if a not in s and cnt[a] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

st = set(As)

Fs = [0]*N

As.sort()
if N == 1:
  print(1)
  exit()
else:
  rlt = 1
  
for i in range(1,N):
  if As[i] == As[i-1]:
    Fs[i] = 1
    if Fs[i-1] == 0:
      rlt -= 1
    continue
  for j in range(i):
    flag = 0
    if Fs[j] == 1:
      continue
    else:
      if As[i] < 2*As[j]:
        break
      if As[i]%As[j] == 0:
        Fs[i] = 1
        flag = 1
        break
  if flag == 0:
    rlt += 1
        
print(rlt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
    flg = 0
    for j in range(i):
        if i != 0:
            if A[i]%A[j] == 0:
                flg = 1
                break    
    if flg == 0:
        if i +1 < N:
            if A[i+1] != A[i]:
                ans += 1
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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 divisors


if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    cnt = 0
    pattarn = []
    for i in range(n):
        b = make_divisors(a[i])
        pattarn.append(set(b))
    queue = collections.deque(a)
    for i in range(n):
        flag = 0
        p = queue.popleft()
        d = set(queue)
        e = pattarn[i]&d
        if len(e) == 0:
            cnt+=1
        queue.append(p)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = np.array(A)
ans = 0
for i in aa:
  b = (i % aa == 0)
  if sum(b) == 1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

ans = [0] * n
for i in range(len(a) - 1):
    if ans[i] == 1:
        continue
    for j in range(i + 1, len(a)):
        if a[i] % a[j] == 0:
            ans[i] = 1
        if a[j] % a[i] == 0:
            ans[j] = 1
print(n - sum(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(input())
#print(N)
A=input().split()
A_int = [int(s) for s in A]
#print(A_int)

#ここから本題
#print(A_int[2])
outcount=0
for i in range(0,N):
  for k in range(0,N):
    if i==k:
      continue
    #本操作
    #print(i,k)
    if A_int[i]%A_int[k]==0:
      outcount+=1
      break
      
print(N-outcount)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans=0
for i in range(N):
  flag=0
  for j in range(N):
    if i==j:
      continue
    if A[j] > A[i]:
      break
    if A[i]%A[j]==0:
      flag=1
      break
  if flag==0:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# from sympy import divisors
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]


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a_list = list(map(int, input().split()))
    # キーに要素、値に出現回数を持つカウンタ
    a_counter = Counter(a_list)
    ans = 0
    for a in a_list:
        # aの約数の集合
        divs = make_divisors(a)
        for divisor in divs:
            if a_counter[divisor] > 0:
                if divisor == a and a_counter[divisor] == 1:
                    continue
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
A = sorted(A)
checked = [True] * N
ans = 0
for i, a in enumerate(A):
    if not checked[i]: continue
    flag = True
    for j in range(i+1, N):
        if A[j] % a == 0:
            checked[j] = False
            if A[j] == a: flag = False
    if flag: ans += 1 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
a.sort()
b = copy.deepcopy(a)

maps = {}

for aa in a:
    if aa in maps:
        tmp = maps[aa]
        maps[aa] = tmp+1
    else:
        maps[aa] = 1

i = 0
while True:
    a_tmp = a[i]
    check = set()
    for j in range(i+1, len(b)):
        if b[j]==a_tmp:
            check.add(i)
        if b[j]%a_tmp==0:
            check.add(j)

    check = list(check)
    check.sort(reverse=True)
    for c in check:
        del b[c]
    
    a = copy.deepcopy(b)
    i += 1
    if i>=len(a):
        break



print(len(a))

Submission status: Time Limit Exceeded

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()

A.sort()
flag = [True] * N

ans = 0
# for i in range(N):
#     if not(flag[i]):
#         continue

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

i = 0
while i < len(A):
    if i == len(A)-1:
        ans += 1
        break
    elif A[i] != A[i+1]:
        ans += 1
    
    j = i+1
    while j < len(A):
        if A[j] % A[i] == 0:
            A.pop(j)
        else:
            j += 1
    i += 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()
a_cnt = Counter(a)

def divisor(n):
    res = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            res.append(i)

            if i != n // i and i != 1:
                res.append(n // i)
    return res

divs = [set(divisor(a[i])) for i in range(n)]

ans = 0
memo = set()
for i in range(n):
    if a_cnt[a[i]] == 1:
        if memo & divs[i] == set():
            ans += 1

    memo.add(a[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

results = deque()
while len(A) > 0:
    if not (len(A) > 1 and A[0] == A[1]):
        results.append(A[0])
    A = [a for a in A if a % A[0] != 0]

print(len(results))

Submission status: Time Limit Exceeded

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

ans = 0
divjl = []
sAl = sorted(Al)
for i in range(len(Al)):
    if i in divjl:
        continue
    flag = True
    for j in range(len(Al)):
        if i == j:
            continue
        if sAl[i] % sAl[j] == 0:
            flag = False
            divjl.append(j)
    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


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


n = int(input())
*A, = map(int, input().split())
A.sort()
setA = set(A)
cnt = 0
for i, a in enumerate(A):
    if bisect.bisect_right(A, a) - bisect.bisect_left(A, a) != 1:
        cnt += 1
        continue
    X = set(make_divisors(a))
    if len(X & setA) != 1:
        cnt += 1
print(n - cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
ans = 0
while A:
    tmp = A[0]
    if len(A) > 1:
        if tmp not in A[1:]:
            ans += 1
        A = [a for a in A[1:] if a % tmp != 0]
    else:
        ans += 1
        break
print(ans)

Submission status: Time Limit Exceeded

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

for a in A:
    temp = a
    while temp < 10**6+1:
        L[temp] += 1
        temp += a

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = a=int(input())
listP=[]
while True:
    try:
        listP=list(map(int,input().split()))
    except:
        break;
#listP=list(set(listP))
#print(N,listP)
counter=0
for i in range(len(listP)):
  for j in range(len(listP)):
    if i!=j and listP[i]%listP[j]==0:
      counter+=1
      break

print(len(listP)-counter)

Submission status: Time Limit Exceeded

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

import collections


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


def count_nondivisors(n, bs):
    ctr = collections.Counter(bs)
    num_div_elems_table = [0 for _ in range(n)]
    for i, k in enumerate(bs):
        v = ctr[k]
        num_div_elems_table[i] = sum(ctr[d] for d in divisors(k))
    res = sum(num_div_elems_table[i] == 1 for i in range(n))
    return res


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    res = count_nondivisors(n, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [int(x) for x in input().split()]
A.sort()
n=0

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

"""
10
33 18 45 28 8 19 89 86 2 4
5
"""

Submission status: Time Limit Exceeded

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

def henkan(LIST):
    ANS=[LIST[i] for i in range(len(LIST)) if not LIST[i] % LIST[0] == 0]
    return ANS
cnt=0
check=0
for i in range(10**9):
    cnt+=1
    if len(A)>=2:
        if A[0]==A[1]:
            check+=1
    A=henkan(A)
    if A==[]:
        print(cnt-check)
        exit()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import math

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


A = sorted(A)


queue = []
double_queue = []

dd = 0

for a in A:

    in_queue = True

    for q in queue:
        if a==q:
            if a not in double_queue:
                dd += 1
                double_queue.append(a)
            in_queue = False
        elif a % q == 0:
            in_queue = False

    if in_queue:
        queue.append(a)


print(len(queue)-dd)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from itertools import *
import copy

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().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]

N = I()
A = LI()
ans = 0

for i, kazu in enumerate(A):
    div = make_divisors(kazu)
    temp = copy.deepcopy(A)
    temp.pop(i)
    
    l1_l2_and = set(temp) & set(div)
    
    if len(l1_l2_and) == 0:
        ans += 1
print(ans)