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

prime = {2: True, 3: True, 5: True, 7: True, 11: True, 13: True, 17: True, 19: True, 23: True, 29: True, 31: True, 37: True, 41: True, 43: True, 47: True, 53: True, 59: True, 61: True, 67: True, 71: True, 73: True, 79: True, 83: True, 89: True, 97: True, 101: True, 103: True, 107: True, 109: True, 113: True, 127: True, 131: True, 137: True, 139: True, 149: True, 151: True, 157: True, 163: True, 167: True, 173: True, 179: True, 181: True, 191: True, 193: True, 197: True, 199: True, 211: True, 223: True, 227: True, 229: True, 233: True, 239: True, 241: True, 251: True, 257: True, 263: True, 269: True, 271: True, 277: True, 281: True, 283: True, 293: True, 307: True, 311: True, 313: True, 317: True, 331: True, 337: True, 347: True, 349: True, 353: True, 359: True, 367: True, 373: True, 379: True, 383: True, 389: True, 397: True, 401: True, 409: True, 419: True, 421: True, 431: True, 433: True, 439: True, 443: True, 449: True, 457: True, 461: True, 463: True, 467: True, 479: True,
         487: True, 491: True, 499: True, 503: True, 509: True, 521: True, 523: True, 541: True, 547: True, 557: True, 563: True, 569: True, 571: True, 577: True, 587: True, 593: True, 599: True, 601: True, 607: True, 613: True, 617: True, 619: True, 631: True, 641: True, 643: True, 647: True, 653: True, 659: True, 661: True, 673: True, 677: True, 683: True, 691: True, 701: True, 709: True, 719: True, 727: True, 733: True, 739: True, 743: True, 751: True, 757: True, 761: True, 769: True, 773: True, 787: True, 797: True, 809: True, 811: True, 821: True, 823: True, 827: True, 829: True, 839: True, 853: True, 857: True, 859: True, 863: True, 877: True, 881: True, 883: True, 887: True, 907: True, 911: True, 919: True, 929: True, 937: True, 941: True, 947: True, 953: True, 967: True, 971: True, 977: True, 983: True, 991: True, 997: True, 1009: True, 1013: True, 1019: True, 1021: True, 1031: True, 1033: True, 1039: True, 1049: True, 1051: True, 1061: True, 1063: True, 1069: True}


def make_divisors(n):

    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n and i in c:
                return False

            tmp = n // i
            if i != tmp:
                if tmp != n and tmp in c:
                    return False
    return True


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

c = Counter(A)

# 1がある時
if 1 in c:
    if c[1] >= 2:
        print(0)
    else:
        print(1)
    exit(0)

ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 素数の時
    if a in prime:
        ans += 1
        continue

    # 小さい数の倍数であるか
    for i in [2, 3, 5, 7, 11, 13]:
        if i in c:
            if a % i == 0:
                break
    else:
        # 約数を取得
        if make_divisors(a):
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

N = int(input())
A = np.fromiter(list(map(int, input().split(' '))), dtype=np.int32)
A.sort()

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

print(len(results))

Submission status: Time Limit Exceeded

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


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


for _ in range(2*(10**5)):
    make_divisors(10**6)
print(1)

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=[]
    for i in range(len(LIST)):
        if LIST[i]%LIST[0]==0:
            pass
        else:
            ANS.append(LIST[i])
    return ANS
cnt=0
check=0
for i in range(10**9):
    cnt+=1
    if A.count(A[0])>=2:
        check+=1
    A=henkan(A)
    if A==[]:
        print(cnt-check)
        exit()

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    count = 0
    for i in range(n):
        for div in divisors[a[i]]:
            if (div in hm and (div!=a[i] or hm[a[i]]>1)) or ((a[i] // div in hm) and (div!=1 or hm[a[i]]>1)):
                count -= 1
                break
        count += 1
    print(count)
    return


def get_divisors():
    divisors = [[] for _ in range(10**6+1)]
    for i in range(1, 10**3+1):
        for j in range(i, 10**6+1, i):
            divisors[j].append(i)
    return divisors



n = RN()
a = RA()
hm = {}
for ai in a:
    if not ai in hm:
        hm[ai] = 0
    hm[ai] += 1
divisors = get_divisors()
solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([int(a) for a in input().split()])
B = A[:]
dup = []
for i in range(N):
    if len(B) <= i:
        break
    j = i+1
    while True:
        if len(B) <= j:
            break
        if B[i] == B[j]:
            dup.append(B[i])
        if B[j] % B[i] == 0:
            del B[j]
        else:
            j += 1
print(len(B) - len(set(dup)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

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

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

        memo.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans=0
for i in range(n):
  if all([i==j or a[i]%a[j]!=0 for j in range(n)]):
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

count = 0
for i in range(n):
    flg = True
    for j in range(n):
        if i == j:
            continue
        if a[i] < a[j]:
            break
        if a[i] % a[j] == 0:
            flg = False
            break
    if flg:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

ans_set=set(a)
for i in range(len(a)):
    if(a[i] not in ans_set):
        continue
    else:
        for j in range(i+1,len(a)):
            if(a[j] in ans_set and a[j]%a[i]==0):
                ans_set.remove(a[j])
#print(ans_set)
print(len(ans_set))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  i = 2
  if Adic[temp] >= 2:
    continue
  while i*i <= temp:
    #print(i,temp)
    if temp%i == 0:
      #print(i,temp//i,temp)
      if i in Aset or temp//i in Aset:
        Flag = False
        #print(i,temp//i,"X")
        break
    if temp%2 !=0: #奇数の時
      if i == 2:
        i = 3
      else:
        i += 2
    else:
      i += 1
  if not Flag:
    continue
  ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def _main(n, a_list):
    count = 0
    for i in range(n):
        i_value = a_list[i]
        fail = False
        for j in range(n):
            if i == j:
                continue
            j_value = a_list[j]
            result = i_value // j_value
            if j_value * result == i_value:
                fail = True
                break
        if not fail:
            count += 1

    print(count)


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

Submission status: Time Limit Exceeded

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

X.sort()
Y=[]
onaji=0
pre=-1
for x in X:

    if x==pre:
        onaji+=1
        pre=-1

    flag=0#warenai

    for y in Y:
        if x%y==0:
            flag=1#wareta
            break

    if flag==0:#全部われなかった
        Y.append(x)
        pre=x

print(len(Y)-onaji)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(v) for v in input().split()]
s = set()
not_uniq = set()

for a in A:
    if a in s:
        not_uniq.add(a)
    else:
        s.add(a)

A.sort()

furui = [True for _ in range(int(1e6)+1)]

ans = 0

s = set()
for a in A:
    base = a * 2
    if a in s:
        continue
    if not a in not_uniq:
        ans += 1 if furui[a] else 0

    while base < (1e6) + 1:
        furui[base] = False
        base += a
    s.add(a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
count = 0
for i in range(n):
    flag = True
    for j in range(i):
        if (a[i]/a[j]).is_integer():
            flag = False
            break
    if i <= n-2 and a[i] == a[i+1]:
        flag = False
    if flag:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
ans = 0

for i in range(n):
  temp = a[i]
  temp_list = np.array([a[:i]])
  temp_list = np.append(temp_list,a[i+1:])
  
  if np.any(temp%temp_list == 0):
    continue
  else:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

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

def solve():
    ans = 0
    for i in range(n):
        for j in range(n):
            if j == i:
                continue
            if a_i[i] % a_i[j] == 0:
                break
        else:
            ans += 1
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
for x in p:
    i=1
    flag = True
    while i*i<=x:
        if x%i==0:
            a=x//i
            b=x//a
            if a in s or b in s:
                flag = False
                break
        i+=1
    if flag:
        s.add(x)

c = Counter(p)
for (k,v) in c.items():
    if v>1:
        s.discard(k)
print(len(s))

Submission status: Time Limit Exceeded

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

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):
	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:
from collections import defaultdict, Counter

def main():
  n, *A = map(int, open(0).read().split())
  cnt = defaultdict(int, Counter(A))
  dset = defaultdict(set)
  l = len(A)
  for i in cnt:
    for j in range(1, int(i ** 0.5) + 1):
      if not i % j:
        dset[i].add(j)
        dset[i].add(i // j)
  res = [l - sum([cnt[j] for j in dset[i]]) == n - 1 for i in A]
  print(sum(res))
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

l = 0
for i in range(len(nums)):
    for j in range(len(nums)):
        if i == j: continue
        if nums[i]%nums[j] == 0 :
            l += 1
            break
print(N-l)

Submission status: Time Limit Exceeded

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

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    else:
      if A[i] % A[j] == 0:
        Y += 1
      else:
        X += 1
    
  if X == N-1:
    Z +=1
  Y =0
  X =0
      
        
print(Z)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    count = 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: count += 1
    print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

total = 0
for i in A:
    count = 0
    for n in A:
        if i % n == 0:
            count += 1
        if count == 2:
            total += 1
            break

print(N-total)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np
npnums = np.array(nums)

cnt = 0 #個数のカウント

for i in nums:
    if np.count_nonzero(i % npnums == 0) > 1:
        cnt +=1
    else:
        continue
print(n-cnt)

Submission status: Time Limit Exceeded

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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))
# 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 C:
            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()))
A.sort()
ans=N
for i in range(N-1):
  if A[i]==A[i+1]:
    ans-=1
  else:  
    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:
a = int(input())
b = list(map(int,input().split()))
count = 0
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:
N = int(input())
A = list(map(int, input().split()))

counter = 0
for i in range(N):
    not_devide_flg = True
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            not_devide_flg = False
            break
    if not_devide_flg == True:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = 0
for i in a:
    if np.count_nonzero(i % a == 0) == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
mod = np.array([[-1 for i in range(N)] for i in range(N)])

count = 0
for i in range(N):
        mod[i] = np.mod(A,A[i])
for i in range(N):
    c = list(mod[:,i]).count(0)
    if c == 1:
        count += 1
        
print(count)

Submission status: Time Limit Exceeded

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

n = 0
for i in range(N):
  a = A[i]
  m = [x for j, x in enumerate(A) if((i != j) and ((a % x)==0))]
  if(len(m) == 0):
       n += 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque


def solve(N: int, A: "List[int]"):
    s = sorted(A)
    s = deque(s)
    min_s = s[0]
    max_s = s[-1]
    lim = int(-(-max_s**0.5//1))+1
    if min_s == 1:
        print((A.count(1)==1)*1)
        return
    
    ans = 0
    # print(s)
    temp = s.popleft()
    ct = 1
    while (len(s)>0) and (s[0] == temp) :
        ct+=1
        temp = s.popleft()
    if ct==1: ans+=1
    # print(ct)
    # print(temp)
    while (len(s)>0):
        new_s = deque()
        while(len(s)>0):
            t = s.popleft()
            if t%temp!=0:
                new_s.append(t)
        s = new_s
        temp = s.popleft()
        ct = 1
        while (len(s)>0) and (s[0] == temp) :
            ct+=1
            temp = s.popleft()
        if ct==1: ans+=1
        # print(temp, s)
        
    print(ans + len(s))

    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:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
p = 0

for i in range(n):
    j = i + 1
    for j in range(n):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            break
        else:
            pass
        if j == n - 1:
                p += 1

print(p)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

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

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

    memo.add(a)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c = Counter(a)
nu = {k for k, v in c.items() if v > 1}

s = set()
for aa in a:
    m = 2
    while aa*m <= 10**6:
        s.add(aa*m)
        m += 1

o = 0
for aa in a:
    if aa in s or aa in nu:
        continue
    o += 1

print(o)

Submission status: Time Limit Exceeded

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

    # divisors.sort()
    return divisors

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

dic = {}
for ai in a:
    if ai not in dic:
        dic[ai] = 0
    dic[ai] += 1

ans = 0

for ai in a:
    cnt = 0
    f = 1
    for i in range(1, int(ai**0.5)+1):
        if ai % i == 0:
            d = i
            if d in dic:
                cnt += dic[d]
            if d == ai:
                cnt -= 1
            if cnt > 0:
                f = 0
                break
            if i != ai // i:
                d = ai // i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break

    ans += f

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    b=list(map(int,input().split()))
    a=dict()
    for i in b:
        if i not in a:
            a[i]=1
        else:
            a[i]+=1
    ans=0
    for k in b:
        divisors=[]
        for i in range(1,int(k**0.5)+1):
            if k%i==0:
                divisors.append(i)
                if i!=k//i:
                    divisors.append(k//i)
        for j in divisors:
            if (j in a and j!=k)or(j==k and a[j]>1):
                break
        else:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

list=[]

for i in range(n):
    for j in range(n):
        if i != j and a[i]>=a[j] and a[i]%a[j] == 0:
            list.append(i)
            break


print(n-len(list))

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

A.sort()
A=deque(A)
d=defaultdict(int)
for j in A:
    d[j]+=1

ans=0
while len(A)>0:
    a=A.popleft()
    if d[a]<=1:
        ans+=1
    B=[]
    for i in A:
        if i%a!=0:
            B.append(i)
    A=deque(B)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = [int(_) for _ in input().split()]

a_list = list(sorted(a_list))

ans = []
for i, a in enumerate(a_list):
    if i < len(a_list)-1:
        if a == a_list[i+1]:
            continue
    if i == 0:
        ans.append(a)
    else:
        is_ok = True
        for a_j in a_list[0:i]:
            q, mod = divmod(a, a_j)
            if mod == 0:
                is_ok = False
                break
        if is_ok:
            ans.append(a)

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

Submission status: Time Limit Exceeded

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

    count = 0
    flag = 0

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    if a[1] > 1:
        return 0
    if a[1] == 1:
        return 1
    b = set(A)
    c = {}
    def find(x):
        if x in c:
            return c[x]
        l = make_divisors(x)
        for j in l:
            if j == x:
                if a[j] > 1:
                    c[x] = 0
                    return 0
            else:
                if j in b:
                    c[x] = 0
                    return 0
        c[x] = 1
        return 1
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())

Submission status: Time Limit Exceeded

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = LI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in A:
        y[i] += 1

    ans = 0
    for i in A:
        for j in range(1,int(math.sqrt(i)) + 1):
            if j == i and y[i] <= 1: continue
            if j == 1:
                if y[1]: break
                if y[i] > 1 : break
            else:
                if i % j == 0 and (y[j] or y[i//j]):
                    break
        else:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    from collections import deque
    from collections import Counter
    dq = deque(a)
    ans = []
    cnt = Counter(a)
    for i in range(n):
        if len(dq) == 0:
            break

        tmp = dq.popleft()

        for j in range(len(dq)):
            tmp2 = dq.popleft()
            if tmp2 % tmp == 0:
                continue
            dq.append(tmp2)
        if cnt[tmp] > 1:
            continue
        ans.append(tmp)

    print(len(ans))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [ int(i) for i in input().strip().split(' ')]
B = [0] * N

for i, Ai in enumerate(A):
    if B[i] != 0:
        continue
    for j in range(N):
        if i==j:
            continue
        if A[i] == A[j]:
            B[i] = 1
            B[j] = 1
            break
        elif A[i] % A[j] == 0:
            B[i] = 1
            break
        elif A[j] % A[i] == 0:
            B[j] = 1
            
print(N - sum(B))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N=int(input())
    A=list(map(int,input().split()))
    from math import sqrt
    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
            s.add(i)
            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
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  flag=True
  s=l[-1-i]
  for j in range(n):
    if n-1-i==j:
      pass
    elif s<l[j]:
      break
    else:
      if s%l[j]==0:
        flag=False
        break
  if flag:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
b=[0]*(10**6+1)
for i in a:
    b[i]+=1
    for j in range(2*i,10**6+1,i):
        b[j]+=2
print(b.count(1))

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 A[1:]:
      count-=1
    A=[i for i in A[1:] if i%x != 0]
    count+=1
print(count)