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


A.sort()

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

print(N-s)

Submission status: Time Limit Exceeded

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

cnt = 0

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    A.sort()

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = set()
    ans = 0
    for i in range(1, N):
        a0 = A[i-1]
        if A[i-1] == A[i]:
            ax.add(a0)
            continue

        for x in ax:
            if a0 % x == 0:
                break
        else:
            ax.add(a0)
            ans += 1

    a0 = A[-1]
    for x in ax:
        if a0 % x == 0:
            break
    else:
        ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

not_divisible = 0
for num1, Ai in enumerate(As):
    for num2, Aj in enumerate(As):
        if num1==num2:
            continue
        if Ai%Aj == 0:
            break
    else:
        not_divisible += 1
print(not_divisible)

Submission status: Time Limit Exceeded

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

for i in range(N):
    flag = False
    temp = A.pop(i)
    for j in range(N-1):
        if temp % A[j] == 0 :
            flag = True
    if flag == False:
        result += 1
    A.insert(i,temp)

print(result)

Submission status: Time Limit Exceeded

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

for i in range(len(A)):
    if i >= len(A)-1:
        break
    for j in range(len(A)-1,i,-1):
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1:
        del A[i]
        onaji = 0

print(len(A))

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

@jit(cache = True)
def solve(i,j,a):
    k=False
    sc=0
    for c in a:
        if c>j:
            break
        elif c>j//2 and c<j:
            continue
        elif c==j:
            sc+=1
            if sc>=2:
                k=True
                break
        else:
            if j%c==0:
                k=True
                break
    return k

n=int(input())
a=sorted(list(map(int,input().split())))
ans=0
for i,j in enumerate(a):
    if solve(i,j,a):
        continue
    else:
        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):
    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:
import copy

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

result = 0

for i, ai in enumerate(a):
    for j, aj in enumerate(ac):
        if i == j:
            continue
        elif ai % aj == 0:
            break
    else:
        result+=1

print(result)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import copy


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

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

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

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

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
A = sorted(A)

maxA = A[-1]
halfA = maxA // 2

ans = [False] * maxA
for a in A:
    if A.count(a) > 1:
        continue
    ans[a - 1] = True

for i in A:
    if i > halfA:
        break
    j = i + i
    while j <= maxA:
        ans[j - 1] = False
        j += i

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right


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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0

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

        if right-left > 1:
            continue

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

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

Submission status: Time Limit Exceeded

Solution code:
def iput(): return int(input())
def mput(): return map(int, input().split())
def lput(): return list(map(int, input().split()))

def solve():
    n = iput()
    a = lput()
    ans = 0
    for i in range(n):
        for j in range(0, i):
            if a[i] % a[j] == 0:
                ans += 1
                break
        else:
            for j in range(i+1, n):
                if a[i] % a[j] == 0:
                    ans += 1
                    break
    print(n - ans)
    return 0

if __name__ == "__main__":
    solve()

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(list(set(As)))
for i in range(N):
  try:
    now = As2[i]
    As3=[x for x in As2[i+1:] if x%now!=0]
    As2 = As2[:i]+As3
    if As.count(now)==1:
      As2.insert(i,now)
  except:
    break
print(len(As2))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = s[0][0]
A = s[1]

cnt = 0
A = sorted(A)
for i in range(N):
    sw = 0
    if i < N - 1:
        if A[i] != A[i + 1]:
            for j in range(i):
                if A[i] % A[j] == 0:
                    sw = 1
                    break
            if sw == 0:
                cnt += 1
    else:
        for j in range(i):
            if A[i] % A[j] == 0:
                sw = 1
                break
        if sw == 0:
            cnt += 1


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
y = [0 for i in range(max(a) + 1)]
same = [0 for i in range(max(a) + 1)]
for i in a:
    same[i] += 1

# 約数
def divisor(x):
    ret = []
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            if y[i] == 1 or y[x // i] == 1:
                return False
    return True


ans = 0
for i in a:
    if divisor(i) and same[i] <= 1:
        ans += 1
    y[i] = 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    st = set(A)
    counter = Counter(A)

    ans = 0
    for i in range(N):
        if counter[A[i]] >= 2:
            continue
        divisors = calc_divisors(A[i])
        for divisor in divisors:
            if divisor == A[i]:
                continue
            if divisor in st:
                break
        else:
            ans += 1
    
    print(ans)

def calc_divisors(n):
    divisors = []
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            divisors.append(i)
            if (i*i != n):
                divisors.append(n//i)

    return divisors

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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     

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

ans=0
while len(A)>0:
    a=A.popleft()
    l=make_divisors(a)

    for i in l:
        if i==a:
            if d[i]>1:
                break
        elif d[i]>0:
            break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    flg = 0
    for j in range(N):
        if p[i]%p[j] == 0 and not i==j:
            flg=1
    if flg==0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(N):
        if A[j] % A[i] == 0:
            flag_lst[j] += 1

res = 0
for flag in flag_lst:
    if flag == 1:
        res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])

n = 0
for i in range(N):
  x = A[i]
  a = x % A
  if(np.count_nonzero(a == 0) == 1):
    n += 1
print(n)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

    count = 0

    a.sort()


    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:
def div(n):
    lower_div, upper_div = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_div.append(i)
            if i != n // i:
                upper_div.append(n // i)
        i += 1
    return lower_div + upper_div[::-1]

def main():
    from collections import Counter
    n = int(input())
    A = list(map(int, input().split()))
    s = set(A)
    c = Counter(A)
    cnt = 0
    for a in A:
        if c[a] >= 2:
            continue
        else:
            d = set(div(a))
            if len(d & s) == 1:
                cnt += 1
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
def solve(i,j,a):
    k=False
    sc=0
    for c in a:
        if c>j:
            break
        elif c>j//2 and c<j:
            continue
        elif c==j:
            sc+=1
            if sc>=2:
                k=True
                break
        else:
            if j%c==0:
                k=True
                break
    return k

n=int(input())
a=sorted(list(map(int,input().split())))
ans=0
for i,j in enumerate(a):
    if solve(i,j,a):
        continue
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = []
while len(A) > 1:
    a = A[0]
    B = []
    if a != A[1]:
        ans.append(a)
    for aa in A:
        if aa % a != 0:
            B.append(aa)
    A = B
if len(A) == 1:
    print(len(ans)+1)
else:
    print(len(ans))

Submission status: Time Limit Exceeded

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

a = sorted(a)
idx = 0
popped = set()
while idx != len(a):
  i = idx+1
  while i != len(a):
    if a[i] % a[idx] == 0:
      popped.add(a.pop(i))
    else:
      i += 1
  idx += 1
idx = 0
while idx != len(a):
  if a[idx] in popped:
    a.pop(idx)
  else:
    idx += 1
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
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:
            break
        if j == n-1:
            count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a = list(collections.Counter(a).items())
    ans = 0
    for i in range(len(a)):
        if a[i][1] > 1:
            continue
        isDiv = False
        for j in range(i):
            if a[i][0] % a[j][0] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

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

for i in range(N):
    if flags[i]:
        k = A[i]
        for j in range(N):
            if i != j:
                if A[j] % k == 0:
                    flags[j] = False
                    if A[j]==k:
                        flags[i] = False
print(sum(flags))

Submission status: Time Limit Exceeded

Solution code:
from time import time

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    ok = [1] * N

    A.sort(reverse=True)

    for i in range(N):
        if A.count(A[i]) >= 2: continue
        for j in range(N-1, i, -1):
            if A[i] % A[j] == 0:
                break
        else: ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
#count = 0
judge = [1]*N

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

    x = {}
    for idx in range(n):
        x[a[idx]] = 0

    cnt = 0
    for i, j in combinations(a, 2):
        if i % j == 0:
            x[i] += 1
        if j % i == 0:
            x[j] += 1

    ans = 0
    for i in x.values():
        if i == 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import numpy as np

if os.path.exists('input.txt'):
    test_mode = True
else:
    test_mode = False

if test_mode:
    f = open('input.txt')
    
def get_input():
    if test_mode:
        return f.readline().rstrip()
    else:
        return input().rstrip()

def int_list(l):
    for i in range(len(l)):
        l[i] = int(l[i])


N = int(get_input())
A = get_input().split()
int_list(A)
ans = 0

for i in range(0, N):
    wareta = False
    for j in range(0, N):
        if i != j and A[i] % A[j] == 0:
            wareta = True
            break
    if not wareta:
        ans += 1
print(ans)
    
if test_mode:
    f.close()

Submission status: Time Limit Exceeded

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

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

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)'''

n=int(input())
a=list(map(int, input().split()))
#print(sorted(a))
a.sort()
wa=[a[0]]
cnt=0
bl=[]
def ok(wa,item,cnt,bl):
    for j in range(len(wa)):
        if item%wa[j]==0:
            if item==wa[j]:
                bl.append(item)
                return
            else:
                return
    wa.append(item)
    #print(item,wa,cnt)
    return

for item in a[1:]:
    ok(wa,item,cnt,bl)
    #print(cnt)

print(max(0,len(wa)-len(set(bl))))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    b = set()
    c = 0
    for i in range(n):
        if i < n - 1 and a[i] == a[i + 1]:
            b.add(a[i])
            continue
        for j in range(1, int(a[i]**0.5) + 1):
            if a[i] % j:
                continue
            if j in b or a[i] // j in b:
                break
        else:
            c += 1
            b.add(a[i])
    print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A = sorted(A)
F = [False for _ in range(N)]

for i in range(N):
    cur = A[i]

    for j in range(i+1, N):
        if not F[j] and A[j] % cur == 0:
            F[j] = True

        if cur == A[j]:
            F[i] = True

print(F.count(False))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

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

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

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

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,*A = get_all_int()
A.sort()



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

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int,input().split()))
a.sort()
que = []
flg = []
for ai in a:
    if len(que) == 0:
        que.append(ai)
        flg.append(0)
    else:
        for j in range(len(que)):
            if ai == que[j]:
                flg[j] = 1
                break
            if ai % que[j] == 0:
                break
        else:
            que.append(ai)
            flg.append(0)
print(len(que)-sum(flg))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
ans = 0
numlist = []
kaburilist = []
for i in range(N):
  if(i==0):
    ans += 1
    numlist.append(B[i])
  else:
    candivflag = 0
    for j in range(ans):
      if(B[i]==numlist[j]):
        if(B[i] not in kaburilist):
          kaburilist.append(B[i])
      elif(B[i]%numlist[j]==0):
        candivflag = 1
        break
      else:
        if(j == ans - 1):
          ans += 1
          numlist.append(B[i])
print(ans - len(kaburilist))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = list(map(int,input().split()))
ans = []
for i in range(len(lst)) :
    for j in range(len(lst)) :
        if j != i :
            if lst[i] % lst[j] == 0 :
                break
        else :
            continue
    else :
        ans.append(i)
print(len(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

D = [A[0]]
E = []

for i, x in enumerate(A):
  Flag = True
  
  if i >= 1:
    
    for j in D:
      if x%j == 0:
        Flag = False
        if x == j:
          E.append(x)
        break
    
    if Flag:
      D.append(x)

print(len(set(D)-set(E)))

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = [0] * (10**6 + 1)
for i in range (N - 1):
    if A[i] == A[i + 1] and B[A[i]] == 0:
        B[A[i]] = 1
        c = A[i]
        d = A[i]
        while c + d <= max(A):
            c = c + d
            B[c] = 1
ans = 0
for i in range(N):
    if B[A[i]] == 0:
        ans += 1
        B[A[i]] = 1
        c = A[i]
        d = A[i]
        while c + d <= max(A):
            c = c + d
            B[c] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter as ct


def solve(n):
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i in b:
                if b[i] >= 2:
                    return 0
                if i != n:
                    return 0
            if i != n // i:
                if n // i in b:
                    if b[n // i] >= 2:
                        return 0
                    if n // i != n:
                        return 0
    return 1


n = int(input())
a = list(map(int, input().split()))
b = ct(a)
cnt = 0
for i in a:
    cnt += solve(i)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
As = list(map(int, input().split()))
As.sort()
table = [0] * (10 ** 6 + 1)
ans = n
for a in As:
    tmp = a
    table[tmp] += 1
    for _ in range((10 ** 6) // a - 1):
        tmp += a
        table[tmp] += 1
for a in As:
    ans -= (table[a] > 1)
print(ans)

Submission status: Time Limit Exceeded

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

counter = 0
for i in range(len(A)):
    warikire = False
    for j in range(len(A)):
        # print(i, j, A[i], A[j])
        if i == j:
            continue
        if A[i] % A[j] == 0:
            warikire = True
            break
        if A[i] < A[j]:
            break
    counter += 1 if not warikire else 0
print(counter)

Submission status: Time Limit Exceeded

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

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]):
					flg[i]=1
					flg[j]=1
				else:
					if(a[i]>a[j]):
						if(a[i]%a[j]==0):
							flg[i]=1
					else:
						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:
n = int(input())
a = list(map(float,input().split()))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
li = np.zeros(10**6)
a = np.array(list(map(int, input().split())))
a.sort()

u, counts = np.unique(a,return_counts=True)

for item in a:
  li[item-1] = 1
#print(li[:100])

for item in a[::-1]:
  li[item-1::item] = 0
  li[item-1] = 1

#print(li[:100])

for i in range(len(u)):
  if counts[i] >=2:
    li[u[i]-1] = 0

print(int(li.sum()))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
aaa.sort()
judge = [1] * len(aaa)
for i in range(len(aaa) - 1):
    if judge[i]:
        for j in range(i + 1, len(aaa)):
            if aaa[j] % aaa[i] == 0:
                judge[j] = 0
        if aaa[i] == aaa[i + 1]:
            judge[i] = 0
    else:
        continue
print(sum(judge))

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):
    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())
a = [int(x) for x in input().split(' ')]

s = sorted(set(a))
i = 0
while i < len(s):
    l = len(s)
    for j in range(l-1, i, -1):
        if s[j] % s[i] == 0:
            s.pop(j)
    i += 1
s = set(s)

from collections import Counter
c = Counter(a)
keys = set([k for k, v in c.items() if v == 1])

print(len(s&keys))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import Counter
    import sys
    input = sys.stdin.readline
    _ = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    s = set(a)
    ans = 0
    for i in s:
        if c[i] >= 2:
            continue
        for j in range(1, int(i ** 0.5) + 1):
            if i % j == 0:
                if j in s and j != i:
                    break
                if j != i // j:
                    if i // j in s and i // j != i:
                        break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def check(s, a, next):
    if a==next:
        return False
    x = 1
    while a>=x*x:
        if a%x==0:
            if x in s:
                return False
            if a//x in s:
                return False
        x += 1
    return True

n = int(input())
al = list(map(int, input().split()))
al.sort()

s = set()
res = 0
for i in range(n):
    a = al[i]
    next = -1
    if i<n-1:
        next = al[i+1]
    if check(s,a,next):
        res += 1
    s.add(a)
print(res)

Submission status: Time Limit Exceeded

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

wa = 0
for i in range(len(a)):
    flg = 0
    for j in range(len(a)):
        if i != j and a[i]%a[j] == 0:
            flg = 1
    if flg == 0:
          wa += 1
    
print(wa)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
s=set()
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            B.append(x)
        else:
            s.add(x)
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
    else:
        B.append(x)


ans=0
for x in B:
    for j in range(1,int(x**0.5)+1):
        if j==1:
            if x==1:
                continue
            else:
                if j in s:
                    break
        elif x%j==0:
            if x//j in s or j in s:
                break
    else:
        ans+=1
    s.add(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = 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

A.append(10**10)
A.append(0)
A.sort()

ans = 0
for i in range(1,N+1):
    li = make_divisors(A[i])

    # print(li)
    for j in li:
        if j==A[i]:
            continue
        mm = bisect.bisect(A,j)
        if A[mm-1]==j and A[mm-1]!=A[i]:
            # print(A)
            break
    else:
        if A[i+1]==A[i] or A[i-1]==A[i]:
            continue
        ans += 1

print(ans)