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:
from collections import Counter
n=map(int, input().split())
*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())
A = list(map(int, input().split()))
c = 0
for i, ai in enumerate(A):
    for j, aj in enumerate(A):
        if i == j:
            continue
        if ai % aj == 0:
            break
    else:
        c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
c=0
x=[]
for i in range(n):
    for j in range(n):
        if a[i]%a[j]!=0:
            c+=1
    x.append(c)
    c=0
z=x.count(n-1)  
print(z)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
I2 = input().split()
intI2 = [int(a) for a in I2]
result = 0
for a in range(len(intI2)):
    flag = 0
    for b in range(len(intI2)):
        if a != b:
            if intI2[a] % intI2[b] == 0:
                flag = 1
    if flag == 0:
        result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    return set(divisors)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    divs = list(map(lambda x: divisors(x), a))

    ok = [True] * n
    nums = set()
    for i, x in enumerate(a):
        if divs[i] & nums:
            ok[i] = False
        nums.add(x)

    nums = set()
    for j, x in enumerate(a[::-1]):
        i = n - (j + 1)
        if divs[i] & nums:
            ok[i] = False
        nums.add(x)
    print(ok.count(True))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#import math
#from fractions import gcd
from math import gcd

def coprime(a, b):
    return gcd(a, b) == 1

def main():

    ##get int
    first_input = list(map(lambda x:int(x), input().split(" ")))
    second_input = list(map(lambda x:int(x), input().split(" ")))

    ##get float
    #first_input = list(map(lambda x:float(x), input().split(" ")))
    #second_input = list(map(lambda x:float(x), input().split(" ")))

    ##get string
    #first_input = input().split(" ")

    N = first_input[0]
    A_list = second_input

    count = 0
    for i in range(len(A_list)):
        buf = 0
        for j in range(len(A_list)):
            if i==j:
                continue
            if A_list[i]%A_list[j]==0:
                buf = buf+1
        if buf==0:
            count = count+1

    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

print(n - count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
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=sorted(list(map(int,input().split())), reverse=True)
cnt=0
for i in a:
    l=make_divisors(i)
    if len(set(a) & set(l))==1 and a.count(i)==1:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

    count = 0


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

    print(n - count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a_dic = {}
for i in a:
    if not i in a_dic:
        a_dic[i] = 0
    a_dic[i] += 1
res = 0
for i in a:
    j = 1
    flag = 1
    while j * j <= i:
        if i % j == 0:
            x = j
            if (x == i and a_dic[x] >= 2) or (x != i and x in a_dic and a_dic[x] >= 1):
                flag = 0
                break
            x = i//x
            if (x == i and a_dic[x] >= 2) or (x != i and x in a_dic and a_dic[x] >= 1):
                flag = 0
                break

        j += 1
    # print(flag)
    if flag:
        res += 1

# print(a_dic)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math

low = 1
high = 100

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

flg=[]
for i in range(n):
	flg.append(0)

for i in range(n-1):
	if(flg[i]==0):
		for j in range(i+1,n):
			if(flg[j]==0):
				if(a[i]%a[j]==0):
					flg[i]=1
				if(a[j]%a[i]==0):
					flg[j]=1
#		print(i,j)
ans=0
for i in range(n):
	if(flg[i]==0):
		ans+=1

#print(a)
#print(flg)
print(ans)

Submission status: Time Limit Exceeded

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


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


def main():
    N = int(input().strip())
    l = sorted([int(i) for i in input().strip().split()])
    ans = 0
    uniq = set(l)
    for i in list(uniq):
        divisors = make_divisors(i)
        if l.count(i) > 1:
            continue
        uniq.remove(i)
        for d in divisors:
            if d in uniq:
                break
        else:
            uniq.add(i)
            ans += 1
            continue
        uniq.add(i)
        continue

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

count = 0

for i, x in enumerate(seq):
    flag = False
    for j, y in enumerate(seq):
        if i == j:
            continue
        if x == y:
            break
        if x % y == 0:
            break
    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

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

    m = (10**6) + 1
    c = [0]*m
    for i in a:
        c[i] += 1

    ans = 0
    for i in a:
        if c[i] > 1:
            continue
        for j in divisor(i):
            if i == j:
                continue
            if c[j] > 0:
                break
        else:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
li = rl()
def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]
li = heapsort(li)
cnt = 0
for i in range(n):
  lii = li[i]
  if i < n-1:
    if lii == li[i+1]:
      continue
  for j in range(i):
    if lii % li[j] == 0:
      break
  else:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

aes = sorted(aes)
aes.append(1111111111111111)
# print(aes)

ans = 0
i = 0
while i < n:
  if aes[i + 1] == aes[i]:
    i += 1
    continue
  j = 0
  ok = True
  while j < i:
    if aes[i] % aes[j] == 0:
      ok = False
    j += 1
  if ok:
    ans += 1
  i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def enum_divs(n):
    res = []
    for i in range(1, int(n ** .5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    return res


N = int(input())
A = list(map(int, input().split()))
uq_A = [k for k, v in Counter(A).items() if v == 1]
set_A = set(A)
ans = 0
for uq_a in uq_A:
    if any(d in set_A - {uq_a} for d in enum_divs(uq_a)):
        continue
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, *A = map(int, open(0).read().split())
c = 0
A.sort(reverse=1)
s = set()
for i, a in enumerate(A):
    c += a not in s and all(a%j for j in A[i+1:])
    s.add(a)
print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque, Counter
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

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

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

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

def prime_factorize(n):
    """
    素因数分解
    
    Sample:
        prime_factorize(36)
        => [2, 2, 3, 3]

        collections.Counter(prime_factorize(36))
        => {2:2, 3:2}
    """
    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

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

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]

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()
C = dict(Counter(A))
keys = C.keys()
# log(C)

ans = 0

for i,a in enumerate(A):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            if C[d] > 1:
                # log(C[d])
                ok = False
                break
        elif d in keys:
            ok = False
            break
    if ok:
        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(len(a)):
    flag = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            flag = False
    if flag == True:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 1:
        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]





n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
count = 0
data = a.copy()
prime = []
limit = a[-1]
while len(data) > 0:
  p = data[0]
  if len(data) > 1 and p == data[1]:
    count += 1
  prime.append(p)
  data = [e for e in data if e % p != 0]
  #print(data)
print(len(prime)-count)

Submission status: Time Limit Exceeded

Solution code:
import math
def calc_factors(n):
    factors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            j = n // i
            if j != i: factors.append(j)
            factors.append(i)
    return factors

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]:
        done[num] = 1
        continue

    factors = calc_factors(num)
    for f in factors:
        if done[f]:
            break
    else:
        ans += 1
        done[num] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
count=0
while len(A)>0:
    x=A[0]
    if x in set(A[1:]):
        count-=1
    A=[i for i in A[1:] if i%x != 0]
    count+=1
print(count)

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()
cnt = 0
for i, a in enumerate(A):
    X = make_divisors(a)
    for x in X:
        le = bisect.bisect_left(A, x, hi=i)
        re = bisect.bisect_right(A, x, hi=i)
        if le != re:
            cnt += 1
            break
        le = bisect.bisect_left(A, x, lo=i + 1)
        re = bisect.bisect_right(A, x, lo=i + 1)
        if le != re:
            cnt += 1
            break
print(n - cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


len_arr = int(input())
arr = np.array(list(map(int, input().split())))

ans = 0
for i in arr:
    mods = np.mod(i, arr)
    num_zeros = np.count_nonzero(mods == 0)
    ans += (num_zeros == 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
aa = tuple(sorted(map(int, input().split())))
cnt = Counter(aa)

ans = 0
for i in range(n - 1, -1, -1):
    if cnt[aa[i]] > 1:
        continue

    f = True
    for j in range(i):
        if aa[i] < aa[j] * 2:
            break
        if aa[i] % aa[j] == 0:
            f = False
            break
    if f:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
input = raw_input
n = int(input())
As = map(int, input().split(" "))

As = sorted(As, reverse=True)
out = 0
for i in range(n):
    A1 = As[i]

    if i >= 1:
        if last_A == A1:
            last_A = A1
            continue

    exist = False

    for j in range(i+1, n):
        A2 = As[j]
        if A1 % A2 == 0:
            exist = True
            break
    if not exist:
        #print(A1)
        out += 1
    last_A = A1


print(out)

Submission status: Time Limit Exceeded

Solution code:
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np    # numpy.lcm()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk
# import networkx as nx
# G = Graph()

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
lisA = list(map(int,input().split()))

lisA.sort()

needcheck = set()
divable = set()
for i in range(N):
    if i == 0:
        needcheck.add(lisA[i])
        continue
    else:
        for num in needcheck:
            if lisA[i] % num == 0:
                divable.add(lisA[i])
                break
        else:
            needcheck.add(lisA[i])

ans = needcheck - divable
print(len(ans))
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd as bltin_gcd
def coprime(a, b):
    return bltin_gcd(a, b) == 1

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    cnt=0
    for j in range(n):
        if i!=j:
            if a[i]%a[j]==0:
                cnt+=1
    if cnt==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import functools
import operator
import sys

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

cnt = 0
for i in range(N):

    flg = True 
    for j in range(N):
        if i != j:
            if (A[i] % A[j] == 0):
                flg = False


    if flg == True:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[]
c=[]
for i in a:
    if len(b)==0:
        b.append(i)
        continue
    flag=True
    for j in b:
        if i==j:
            c.append(j)
        if i%j==0:
            flag=False
    if flag:
        b.append(i)
if c:
    for i in c:
        if b:
            b.remove(i)
print(len(b))

Submission status: Time Limit Exceeded

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

N=int(input().rstrip('\n'))
As=[int(x) for x in input().rstrip('\n').split()]
As2 = sorted(As)
for i in range(N):
  try:
    now = As2[i]
    As2=[x for x in As2 if x%now!=0]
    if As.count(now)==1:
      As2.insert(i,now)
  except:
    break
print(len(As2))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 約数
N = ir()
A = lr()
A.sort()
answer = 0
se = set()

def make_divisors(n):  # 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

for i, a in enumerate(A):
    if i < N-1 and a == A[i+1]:
        se.add(a)
        continue
    divs = make_divisors(a)
    bl = True
    for x in divs:
        if x in se:
            bl = False
            break
    if bl:
        answer += 1
    se.add(a)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [int(s) for s in input().rstrip().split()]

count = 0

def explore(i):
  n_i = nums[i]
  for j in range(N):
    if j != i:
      n_j = nums[j]
      if n_j <= n_i:
        if n_i % n_j == 0:
          return 0
  return 1

for i in range(N):
  count += explore(i)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())

A = list(map(int, input().split()))
A.sort()
ans = deque()
ans.append(A[0])
before = A[0]
remove = set()
for a in A[1:]:
    if before == a:
        if a in ans:
            remove.add(a)
        continue
    flag = True
    for b in ans:
        if a % b == 0:
            flag = False
            break
        if a < b*2:
            break
    if flag:
        ans.append(a)
    before = a

print(len(ans)-len(remove))

Submission status: Time Limit Exceeded

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

t=0

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


print(n-t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
ans = N
div = sorted([x for x in set(A) if A.count(x) > 1], key=A.index)
# print(A)
for i in range(N):
    for j in range(len(div)):
        if A[i] % div[j] == 0:
            ans -= 1
            break
    div.append(A[i])

print(ans)

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 s1:
                flg = False
                break
            if i != n // i:
                if n//i in s1:
                    flg = False
                    break
        i += 1
    return flg

n = int(input())
a = list(map(int,input().split()))
s = set(a)
cnt = 0
from collections import Counter
c = Counter(a)
for i in range(n):
    if c[a[i]] > 1:
        continue
    s1 = s-{a[i]}
    if make_divisors(a[i]):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter
from numba import jit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
c = Counter(a)

se = set()

@jit
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]

for i in a:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
            break
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
array = list(map(int, input().split()))
count = 0
for i in range(n):
    judge = 1
    ai = array[i]
    for j in range(n):
        aj = array[j]
        if j == i:
            continue
        if ai >= aj:
            if ai % aj == 0:
                judge *= 0
                continue
    if judge != 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

    x = [[0 for i in range(n)] for j in range(n)]

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

    ans = 0
    for i in range(n):
        if sum(x[i]) == 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
import collections
c = collections.Counter(l)
if 1 in c:
  if c[1]==1:
    print(1)
    quit()
  else:
    print(0)
    quit()
x=[y for y in c if c[y]==1]
x.sort()
def div(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass 
ans=1
if len(x)==0:
  print(0)
else:
  s=set([x[0]])
  for i,y in enumerate(x[1:]):
    memo=0
    for z in div(y):     
      if z in s:
        pass
      else:
        memo+=1
      if memo==len(div(y)):
        ans+=1
    s.add(y)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
a=list(map(int,input().split()))
d=dict()
for i in range(n):
    if d.get(a[i],None)==None:
        d[a[i]]=0
    d[a[i]]+=1 
ans=0
s=d.keys()
for i in range(n):
    if d[a[i]]>1:
        continue 
    flag=True
    # print(a[i],end='    s\n')
    for ii in range(1,math.ceil(a[i]**(1/2))+1):
        if (a[i]%ii)==0:
            aa,bb=ii,a[i]//ii
            if aa!=a[i] and aa in s:
                # print(aa)
                # print('aa')
                flag=False
                break
            if bb!=a[i] and bb in s:
                # print('bb')
                # print(bb)
                flag=False
                break
    if(flag):
        # print(a[i])
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A_counters = 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)
    return set(divisors)

heapq.heapify(A)

nums = set()
ans = 0
while A:
    a = heapq.heappop(A)
    a_divs = make_divisors(a)
    if len(nums & a_divs) == 0 and A_counters[a] == 1:
        ans += 1
    nums.add(a)
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
done[0] = 1

for i in range(n):
    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:
# coding: utf-8


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

    return sorted(ans)


def main():
    N = int(input())

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

    # is_in_A_flag = [0] * (10**6+1)
    is_in_A_flag = {f"{i}": 0 for i in range(10**6+1)}

    for a in A:
        is_in_A_flag[f"{a}"] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[f"{b}"] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[f"{B[i][-1]}"] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())

Submission status: Time Limit Exceeded

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

for i in range(N):
  flag = "true"
  for j in range(N):
    if i != j:
      if A[i] % A[j] == 0:
        flag = "false"
        break
  if flag == "true":
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
if 0 in a:
    ans=0
else:
    cnt=n
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            else:
                if a[i] % a[j] == 0:
                    cnt -= 1
                    break
    ans=cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    A=sorted(list(map(int,input().split())))
    cnt=0

    for i in range(n):
        if i<n-1 and A[i+1]==A[i]:
            continue
        for j in range(i):
            if A[i]%A[j]==0:
                break
        else:
            cnt+=1
    print(cnt)

    
resolve()