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:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(len(a)):
    sign = []
    for j in range(len(a)):
        p = a[i]%a[j]
        if p == 0:
            sign.append(1)
        else:
            sign.append(0)
    if sum(sign) == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*n
    a.sort(reverse=True)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect, bisect_left
N = int(input())
A = list(map(int, input().split()))
A_ = sorted(list(set(A)))
A = sorted(A)
ans = 0
i = 0
while i < len(A_):
  a = A_[i]
  j = i+1
  while j < len(A_):
    if A_[j] % a == 0:
      A_.pop(j)
    else:
      j += 1
  if bisect(A, a)-bisect_left(A, a) > 1:
    ans -= 1
  i += 1
print(ans+len(A_))

Submission status: Time Limit Exceeded

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    one_cnt = 0
    has_two = False
    for i in range(n):
        i_value = a_list[i]
        if i_value == 1:
            one_cnt += 1
            if 2 <= one_cnt:
                print(0)
                return
        elif one_cnt == 1:
            print(1)
            return

        if i_value == 2:
            has_two = True
        elif has_two:
            if i_value % 2 == 0:
                continue

        fail = False
        for j in range(0, min(i + 2, n)):
            if i == j:
                continue
            j_value = a_list[j]
            q, mod = divmod(i_value, j_value)
            if mod == 0:
                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:
from math import sqrt

N = int(input())
A = list(map(int, input().split()))
A.sort()
#print(A)
ans = []
res = []
nans = 0
doubling = 0
i = 0
while i < N:
  a = A[i]
  #sqa = sqrt(a)
  #print(i,a)
  if i == 0:
    flag = False
    while i + 1 < N:
      bufa = A[i+1]
      if bufa == a:
        i += 1
        flag = True
      else:
        break
    if flag:
      nans += 1
      doubling += 1
      ans.append(a)
    else:
      nans += 1
      ans.append(a)
      res.append(a)
  elif i < N-1:
    flag = False
    while i + 1 < N:
      bufa = A[i+1]
      if bufa == a:
        i += 1
        flag = True
      else:
        break
    if flag:
      d = 0
      flag2 = True
      while 1:
        if a%ans[d] == 0:
          flag2 = False
          break
        if nans -1 == d:
          break
        d += 1
      if flag2:
        nans += 1
        doubling += 1
        ans.append(a)
    else:
      d = 0
      flag2 = True
      while 1:
        if a%ans[d] == 0:
          flag2 = False
          break
        if nans -1 == d:
          break
        d += 1
      if flag2:
        nans += 1
        ans.append(a)
        res.append(a)
  else:
    d = 0
    flag2 = True
    while 1:
      if a%ans[d] == 0:
        flag2 = False
        break
      if nans -1 == d:
        break
      d += 1
    if flag2:
      nans += 1
      ans.append(a)
      res.append(a)
  i += 1
        
        
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x)for x in input().split()]
cumin=0
for i in range(N):
    curry=0
    for j in range(N):
        if(j!=i and A[j]<=A[i]):
            if A[i]%A[j]==0:
                curry +=1
    if curry == 0:
        cumin +=1
print(cumin)

Submission status: Time Limit Exceeded

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

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

is_continue = [False] * n

A.sort()
ans = 0

for i in range(0, n - 1):
    if is_continue[i]:
        continue
    else:
        ans += 1
        if A[i] == A[i + 1]:
            ans -= 1
        for j in range(i + 1, n):
            if A[j] % A[i] == 0:
                is_continue[j] = True

if not is_continue[n - 1]:
    ans += 1

print(ans)
# print(A)
# print(is_prime)
# print(is_continue)

Submission status: Time Limit Exceeded

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

def solve():
    ans = 0
    count = 0
    for i in range(1, 1000001):
        if i in a_i:
            flag = 0
            for j in range(n):
                if i != a_i[j] and i % a_i[j] == 0:
                    break
                elif i == a_i[j] and flag == 0:
                    flag = 1
                elif i == a_i[j] and flag == 1:
                    break
            else:
                ans += 1
            count += 1
        if count == n:
            break
    return ans

print(solve())

Submission status: Time Limit Exceeded

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

check = [1] * n

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

print(sum(check))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
# print(a)
# print(n)
ans = [0 for _ in range(n)]


for i_out in range(n):
    for i_in in range(n):  # i_out+1,
        if i_out == i_in:
            continue
        # print(i_out, i_in)
        if int(a[i_in] / a[i_out]) == a[i_in] / a[i_out]:
            ans[i_in] = 1
            # print('!')

# print(ans)
print(n - sum(ans))

Submission status: Time Limit Exceeded

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

length = len(given_list)
count = 0

for i in range(length):
    ele_1 = given_list[i]
    for j in range(length):
        ele_2 = given_list[j]
        if (i != j) and (ele_1 % ele_2 == 0):
            count += 1
            break

print(length - count)

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:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  for j in range(n):
    if i != j:
      if a[i] % a[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()

cnt = 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:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
input_line = list(map(int,input().split(' ')))

ans = num

for i in range(num):
    now = input_line[i]
    for j in range(num):
        if(i!=j):
            if(now%input_line[j]==0):
                ans-=1
                break

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
import copy

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


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

A.sort()
rA.sort(reverse=True)
ans = 0
for i in range(len(rA)):
    if rA.count(rA[i]) >= 2:
        continue
    flag = 1
    for j in range(len(A)):
        if rA[i] < A[j] * 2:
            break
        if rA[i] % A[j] == 0:
            flag = -1
            break
    if flag == 1:
       ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
count = 0
for i in range(N):
  flag = False
  for j in range(N):
    if i != j:
      if A[i] % A[j] == 0:
        flag = True
        break
  if flag == False:
    count += 1
print(count)

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

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

ret = 0

for i in range(n):
    is_ok = True
    val = a[i]
    if val in dup:
        continue
    divs = make_divisors(val)
    for item in divs:
        if item == val:
            continue
        elif item in cand:
            is_ok = False
            break
    if is_ok:
        ret += 1

print(ret)

Submission status: Time Limit Exceeded

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

A.sort()
#print(A)
count = 0
for i in range(N):
    Ai = A[i]
    hantei = True
    # j
#    k = bisect.bisect_right(A, Ai)
#    print(Ai, k)
    for j in range(i):
        if Ai % A[j] == 0:
            hantei = False
            break
    # 同じ数があった場合の対策
    if i+1 < N and Ai % A[i+1] == 0:
        hantei = False
    if hantei:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

def calc(N, S):
    A = {}
    for s in S.split():
        x = int(s)
        if x in A:
            A[x] = 0
        else:
            A[x] = 1
        for a in A:
            if a == x:
                continue
            if x % a == 0:
                A[x] = 0
            if a % x == 0:
                A[a] = 0
    n = 0
    for a in A:
        n += A[a]
    return n
    

N = int(input())
S = input()
print(calc(N, S))

Submission status: Time Limit Exceeded

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

flags = [True for i in range(N)]

count = 0
for i in range(N):
    if flags[i]:
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                flags[j] = False
            if A[j] == A[i]:
                flags[i] = False
        if flags[i]:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from builtins import int, map, list, print, len
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = (lambda: (sys.stdin.readline()).rstrip())
    input_list = (lambda: input().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N = input_number()
    A = input_number_list()
    A.sort()
    i = 0
    while i < len(A) - 1:
        tmp = A[i]
        j = i + 1
        if A[i] == A[j]:
            del A[i]
            j -= 1
        while j < len(A):
            if A[j] % tmp == 0:
                del A[j]
            else:
                j += 1
        i += 1
    print(len(A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(s) for s in input().split()]
# a = list(range(1, 2*10**5))
ans = 0
for i,j in enumerate(a):
  a_i = sum(a[i]%s==0 for s in a)
  ans += min([2, a_i])
  # print(min([2, a_i]))
# print('###')
print(n - (ans-n))

Submission status: Time Limit Exceeded

Solution code:
ans=0
N=int(input())
A=list(map(int,input().split()))
B=[[]] * N
A.sort(reverse=True)
for i in range(N):

    if i!=0 and A[i]==A[i-1]:
        B[i]=B[i-1]
    else:
        B[i]=1
        for k in range(i+1,N):
            if A[i]%A[k]==0:
                B[i]=0
                break
for i in range(N):
    ans+=B[i]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque 
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
a = deque(a)
if a.count(min(a)) >= 2:
    ans = 0
else:
    ans = 1
ln = [i for i in a if a.count(i) >= 2]
while a:
    v = a.popleft()
    if v not in ln:
        x = 0
        for j in a:
            if v % j == 0:
                break
            else:
                x += 1
            if x == len(a):
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

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



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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
  fNum = nums[i]
  for j in range(N):
    if (count[j] == 1):
      continue
    elif (i == j):
      continue
    else:
      sNum = nums[j]
      if (sNum%fNum == 0):
      	count[j] += 1
answer = 0
for i in count:
  if (i == 0):
    answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a_cnt = Counter(a)

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

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

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

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

    memo.add(a[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
lena = len(a)
a.sort(reverse=True)

tmp = [0] * lena

for i in range(lena):
    for j in range(i + 1, lena):
        if a[i] == a[j]:
            tmp[i] += 1
            tmp[j] += 1
            break
        elif not (a[i] % a[j]):
            tmp[i] += 1
            break

ans = 0
for one in tmp:
    if not one:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    divs = []
    dup = []
    for a in alist:
        div_found = False
        for v in divs:
            if a % v == 0 and a != v:
                div_found = True
                break
        if div_found:
            continue

        if a in divs:
            dup.append(a)
            continue

        divs = [v for v in divs if v % a != 0]
        divs.append(a)

    print(len([v for v in divs if not v in dup]))

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

N,*A = map(int, sys.stdin.buffer.read().split())

A = sorted(A)
setA = set(A)

def yakusu(x):
  if x==1:
    return []
  result = [1]
  y = 2
  while y**2<=x:
    if x%y==0:
      result.append(y)
      result.append(x//y)
    y += 1
  return result

count = N
for i in range(N):
  a = A[i]
  if i>0 and a==A[i-1]:
    count -= 1
    continue
  if i<N-1 and a==A[i+1]:
    count -= 1
    continue
  y = 1
  while y**2<=a:
    if a%y==0:
      if y!=a and y in setA:
        count -= 1
        break
      if a//y!=a and a//y in setA:
        count -= 1
        break
    y += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
aa = list(map(int, input().split()))
aa.sort()

from collections import Counter
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

oks = np.ones(len(aa))
for i in range(len(aa)):
    if i < len(aa)-1:
        if aa[i+1] == aa[i]:
            oks[i] = 0
    for j in range(i+1,len(aa)):
        if (aa[j]%aa[i] == 0):
            oks[j] = 0
print(int(oks.sum()))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
A = [int(i) for i in input().split()]
d = defaultdict(int)
for i in A:
    d[i] += 1
# remember to remove duplicates
A = sorted(list(set(A)))
m = len(A)
visited = [False for i in range(m)]
ans = set()
for i in range(m):
    if not visited[i]:
        ans.add(A[i])
        for j in range(i+1, m):
            if A[j] % A[i] == 0:
                visited[j] = True
ans = [i for i in ans if d[i] == 1]
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if New_List[i] == New_List[j]:
        Flag[i] = 0
        Flag[j] = 0
      elif New_List[j] % New_List[i] ==0:
        Flag[j] = 0
      else:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
line = list(map(int, input().split()))
count = []
for i in range(0, n):
	f = False
	ai = line[i]
	for j in [k for k in range(0, n) if k != i]:
		aj = line[j]
		if ai % aj == 0: f = True
	if f is False and line[i] not in count: count.append(line[i])
print(len(count))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = set()
    count = 0
    for i in range(n):
        t = a[i]
        limit = t // 2 +1
        is_ok = True
        if i+1 < n and t == a[i+1]:
            pool.add(t)
        if t in pool:
            continue
        for j in pool:
            if j > limit:
                break
            elif t % j == 0:
                is_ok = False
                #print("bad", t, j)
                break
        if is_ok:
            #print("good", t)
            pool.add(t)
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
A = sorted(A)
S = Counter(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

numlist = [0] * (10 ** 6 + 1)

cnt = 0
for i in range(N):
    flag = True
    ng_list = make_divisors(A[i])
    for ng in ng_list:
        if numlist[ng] >= 1:
            flag = False
            break
    if flag:
        numlist[A[i]] += 1
        cnt += 1

for i in range(len(numlist)):
    if numlist[i] >= 1 and S[i] >= 2:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

l=[]
for n in A:
    data=[x%n for x in A]
    l.append(data)

arr=np.rot90(np.array(l))

res=0
for l in arr:
    if np.count_nonzero(l==0)==1:
        res+=1
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
isinA = [0] * (a_ls[-1]+1)
for i in range(n):
    isinA[a_ls[i]] = 1

def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    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()
    divisors.pop()
    return divisors

ans = 0
for i in range(n):
    divisors = make_divisors(a_ls[i])
    not_divisible = True
    for j in range(len(divisors)):
        if isinA[divisors[j]]:
            not_divisible = False
    if i > 0:
        if a_ls[i-1] == a_ls[i]:
            not_divisible = False
    if i < n-1:
        if a_ls[i+1] == a_ls[i]:
            not_divisible = False
    if not_divisible:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = [int(x) for x in input().split()]
invans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            None
        else:
            if Alist[i] % Alist[j] == 0:
                invans += 1
                break

print(N - invans)

Submission status: Time Limit Exceeded

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

B = [0 for _ in range(n)]
for i in range(n):
  c = 0
  if B[i] == 1:
    continue
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 1
    B[i+1] = 1
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if B[j] == 1 or A[i]*c > A[j]:
        continue
      if A[j] == A[i]*c:
        B[j] = 1
print(n-sum(B))

Submission status: Time Limit Exceeded

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

l = []
l.append(a[0])
cou =[]
for i in range(1,n):
    b = a[i]
    for j in range(len(l)):
      if b==l[j]:
        cou.append(b)
        break
      if b%l[j]==0:
          break
    else:
        l.append(b)
print(len(l)-len(set(cou)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt, cos, radians, pi
from collections import defaultdict as d
from itertools import combinations as c

def f(n):
	i = 1
	s = set()
	while i <= sqrt(n):
		if (n % i == 0):
			if (n / i == i):
				s.add(i)
			else:
				s.add(i)
				s.add(n//i)
		i = i + 1
	return s

n = int(input())
arr = list(map(int, input().split()))
dd = d(int)
for i in arr:
	dd[i] += 1
l = set(arr)
ans = 0
for v in arr:
	s = f(v)
	g = 1
	for i in s:
		if (i != v and i in l) or dd[v]>1:
			g = 0
			break
	ans += g
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
good = N
i = 0
A = [int(x) for x in input().split()]
for i in range(N):
    counter = 0
    for j in range(N):
        if A[i]%A[j]==0:
            counter += 1
            if counter == 2:
                good -= 1
                break
print(good)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def make_divisors(n):
    lower_divisors, upper_divisors = set(), set()
    tmp = 1
    while tmp * tmp <= n:
        if n % tmp == 0:
            lower_divisors.add(tmp)
            if tmp != n // tmp:
                upper_divisors.add(n // tmp)
        tmp += 1
    return lower_divisors | upper_divisors


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted(map(int, input().split()), reverse=True)
b = 0
#print(A)
for i in range(n):
  if i != 0:
    if A[i] == A[i-1]:
      continue
  j = i+1
  if j == n:
    b += 1
    continue
  while j < n:
    if A[i]%A[j] == 0:
      break
    if j == n-1:
      b += 1
    j += 1
print(b)

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:
            count = count + 1
            break

print(N - count)

Submission status: Time Limit Exceeded

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

aa = set()
dups = set()
for a in A:
    if a in aa:
        dups.add(a)
    else:
        aa.add(a)

others = set(A)
ans = 0
for a in A:
    if a in dups:
        continue
    others.discard(a)
    i = 1
    while i * i <= a:
        if a % i == 0:
            if i in others or (a // i) in others:
                break
        i += 1
    else:
        ans += 1
    others.add(a)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

    memo.add(a[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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:
            continue
        if A[i]%A[j] == 0:
            cnt += 1
            break
    if cnt == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

from functools import lru_cache
# @lru_cache(maxsize=None)
# def divisor(n):
#     i = 1
#     table = []
#     while i * i <= n:
#         if n % i == 0:
#             table.append(i)
#             table.append(n // i)
#         i += 1
#     table = list(set(table))
#     return table

@lru_cache(maxsize=None)
def mySolve(n):
    flag = True
    i = 1
    while i * i <= n:
        if n % i == 0:
            d = i
            if d != a:
                if d in l.keys():
                    flag = False
                    break
            elif l[d] >= 2:
                flag = False
                break
            d = n//i
            if d != a:
                if d in l.keys():
                    flag = False
                    break
            elif l[d] >= 2:
                flag = False
                break
        i += 1
    return flag

# @lru_cache(maxsize=None)
# def mySolve(n):
#     flag = True
#     da = divisor(a)
#     for d in da:
#         if d != a:
#             if d in l.keys():
#                 flag = False
#                 break
#         elif l[d] >= 2:
#             flag = False
#             break
#     return flag

ans = 0
for a in A:
    if mySolve(a):
        ans += 1

print(ans)