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

count = 0

for i in range(0, N):
    flag = 0
    j_list = list(range(N))
    j_list.pop(i)
    for j in j_list:
        if (A[i] % A[j] == 0):
            flag = 1
            break
    if flag == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

A.sort()
B = [0]*N

for i in range(N):
    if B[i]:
        continue
    if i < N-1:
        if A[i] == A[i+1]:
            B[i] = 1
    x = A[i]
    for j in range(i+1, N):
        if A[j]%x == 0:
            B[j] = 1

print(N-sum(B))

Submission status: Time Limit Exceeded

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

As = sorted(As)
c = []
e = set()
p = 0

for a in As:
    if a == p:
        e.add(a)
    else:
        nd = True
        for b in c:
            if a % b == 0:
                nd = False
                break
        if nd:
            c.append(a)
    p = a
c = [v for v in c if v not in e]
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
# D - Not Divisible

n = int(input())
a = list(map(int, input().split()))
b = [1]*n
for i in range(n):
    for j in range(n):
        #print(i,j)
        if i!=j and a[i]%a[j]==0:
            b[i]=0
            break

#check
#print(b)

print(sum(b))

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import bisect

N=one_int()

As = many_int()
def naive(As, N):
    l = len(As)
    count=0
    for i in range(l):
        flg = True
        for j in range(l):
            if i==j:
                continue
            if As[i]%As[j]==0:
                flg=False
                break
        if flg:
            count+=1
    return count

print(naive(As, N))

Submission status: Time Limit Exceeded

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

a.sort()
c = [1]*n
m = 0

for i in range(n):
    for j in range(n):
        if i == j:
            m = m
        elif a[i] % a[j]==0:
            c[i] = 0

s = c.count(1)
print(s)

Submission status: Time Limit Exceeded

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

A.sort()

X = [1 for _ in range(N)]

for i in range(N):
    Ai = A[i]
    for j in range(max(i-1, 0), N):
        if i != j and X[j] == 1 and A[j] % Ai == 0:
            X[j] = 0

print(sum(X))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
nlist = list(map(int, input().split()))

perm = list(itertools.permutations(nlist, 2))
ref = []
tmp = []
for num, j in enumerate(perm):
    tmp.append(j)
    if (num + 1) % (len(nlist) - 1) == 0:
        ref.append(tmp)
        tmp = []
check = []
for ind, i in enumerate(ref):
    for k in i:
        if k[0] % k[1] == 0:
            check.append(ind)
            break

print(len(nlist) - len(check))

Submission status: Time Limit Exceeded

Solution code:
import collections
import random

N = int(input())
A = list(map(int, input().split()))
A.sort()
counter = collections.Counter(A)
counta = 0


for index, num in enumerate(A):
    B = A[:index]
    random.shuffle(B)
    for tmp in B:
        if num % tmp == 0:
            break
    else:
        if counter[num] == 1:
            counta += 1

print(counta)

Submission status: Time Limit Exceeded

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

if n==1:
    print(1)
    exit()
if len(set(orga)) == 1:
    print(0)
    exit()

import collections
c = collections.Counter(orga)
a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

aset=set(orga)

def m_div(n,aset):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i!=n and i in aset:
                return False
            if i != n // i:
                if (n//i != n) and (n//i in aset):
                    return False
    return True

ans=0
for num in a:
    if m_div(num,aset):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

'''

'''

def is_not_div(n, arr, rightp, num):
    if rightp == -1:
        return True
    else:
        for i in range(0, rightp+1):
            if num % arr[i] == 0:
                return False
        return True



def solve(n, arr):
    count = 0
    for i, num in enumerate(arr):
        if i > 0 and arr[i-1] == num:
            continue
        if i < len(arr) - 1 and arr[i+1] == num:
            continue

        if is_not_div(n, arr, i-1, num):
            count += 1
    return count



n = int(input())
arr = sorted(map(int, input().split()))
print(solve(n, arr))

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import Counter

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

counter = Counter(seq)
candidate = set(seq)

count = 0

for i, x in enumerate(sorted(candidate)):
    if x not in candidate:
        continue
    for y in copy.copy(candidate):
        if x == y:
            continue
        if y % x == 0:
            candidate.remove(y)

for c in tuple(candidate):
    if seq.count(c) > 1:
        candidate.remove(c)

print(len(candidate))

Submission status: Time Limit Exceeded

Solution code:
n, *a = map(int, open(0).read().split())
a.sort()
key = [0]*n
for i in range(n-1):
  if key[i]: continue
  for j in range(i+1, n):
    if a[i]==a[j]:
      key[i] = 1
      key[j] = 1
    elif a[j]%a[i]==0:
      key[j] = 1
print(key.count(0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

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
m = [0] * MAX
for i in range(n):
  m[a[i]] += 1
#print(m[:30])
mx = max(a)
ans = 0
for i in range(2, mx + 1):
  if m[i] != 1:
    continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
A = list(sorted(A))
q = deque(A)
ans = 0
while q:
  t = q.popleft()
  cnt = q.count(t)
  if t == 1:
    if cnt == 0:
      print(1)
      sys.exit()
    else:
      print(0)
      sys.exit()
  if cnt == 0:
    ans += 1
  count = 0
  for j in range(len(q)):
    if q[j] % t == 0:
      count +=1
      q.remove(q[j])
      q.appendleft(1)
  for i in range(count):
    q.remove(1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = (list(map(int, input().split(' '))))
D = [0]*(pow(10,6)+1)
ans = 0
for i in A:
    D[i] += 1
for i in A:
    flg = True
    if D[i] > 1:
        continue
    for j in range(1,int(pow(i,0.5))+2):
        if not i%j:
            if D[j] and i != j:
                flg = False
                break
            if j != i//j and D[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import sympy

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

# def div(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 i in range(N):
    Ao = A[:i]+A[i+1:]
    # mod = set(A) & set(div(A[i]))
    # print(div(a))
    if all([A[i]%a!=0 for a in Ao]):
    # if len(mod)==1:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
orga = list(map(int, input().split()))

if n==1:
    print(1)
    exit()
if len(set(orga)) == 1:
    print(0)
    exit()

import collections
c = collections.Counter(orga)
a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

aset=set(orga)

def m_div(n,aset):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i!=n and i in aset:
                return False
            if i != n // i:
                if (n//i != n) and (n//i in aset):
                    return False
    return True

ans=0
for num in a:
    if m_div(num,aset):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

    for i in range(n):
        flg = True
        if i != 0 and i != n - 1:
            if a[i] in a[: i] or a[i] in a[i + 1:]:
                flg = False
        elif i == n - 1:
            if a[i] in a[: i]:
                flg = False
        else:
            if a[i] in a[i + 1:]:

                flg = False

        for j in range(i):
            if a[i] % a[j] == 0:
                flg = False
            if a[i] < a[j] * 2:
                break

        if flg:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
rm_dct = {}
# rm_list = []
for c in a:
  if str(c) not in rm_dct:
    # rm_list.append(c)
    rm_dct[str(c)] = 1
  else:
    rm_dct[str(c)] += 1
a = list(set(a))

index = 0
p = a[0]
last = a[-1]
flg = False
while True:
  for i in range(index+1, len(a)):
    if a[i] % p == 0:
      a[i] = 0
  for i in range(index+1, len(a)):
    if a[i] > 0:
      index = i
      p = a[i]
      flg = True
      break
  if not flg or p >= last:
    break
  flg = False

ans = 0
for c in a:
  if c != 0 and ((str(c) not in rm_dct) or rm_dct[str(c)] <= 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
count = 0
k = 0
flag = False

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

Ali.sort()

dup_count = 0
for index_i,i in enumerate(Ali):
    dup_flag = False
    for j in Ali[index_i+1:]:
        if j==i:
            dup_flag = True
        if j%i == 0:
            Ali.remove(j)
    
    if dup_flag:
        dup_count += 1

print(len(Ali)-dup_count)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
 
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True


n=int(input())
As = list(map(int, input().split()))
i=0
j=0
count =0
if As.count(1)==1:
    print(1)
    sys.exit()
if As.count(1)>=2:
    print(0)
    sys.exit()
for a in As:
    if As.count(a)>=2:
        i+=1
        continue
    elif isPrime(a):
        count+=1
        i+=1
        continue
    for b in As:
        if i!=j:
            if a%b==0:
                break
            elif j==n-1:
                count+=1
        elif j==n-1:
            count+=1
        j+=1
    i+=1
    j=0

print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
ans=0
for i in range(N):
    count=0
    LL=L.copy()
    LL.remove(L[i])
    for j in range(N-1):
        if L[i]%LL[j]==0:
            count+=1
    if count==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=[]

icnt=0
while True:
    aa.append(a[0])
    a2=[]
    for i in range(1,len(a)):
        if a[i]%a[0]!=0:
            a2.append(a[i])
    a=a2.copy()
#    print(aa,a)     
    if len(a2)==0:
        break
    icnt+=1
#    if icnt>10:break

aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()

# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#     tmp.add(v)
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

tmp = [a[0]]
for i in range(1, n):
    num = a[i]
#     for i in range(len(tmp)-1, -1, -1):
    for i in range(len(tmp)):
        item = tmp[i]
        if num%item==0:
            break
        if item*2>num:
            tmp.append(num)
            break
    else:
        tmp.append(num)
tmp = set(tmp) - s
print(len(tmp))

Submission status: Time Limit Exceeded

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

count = 0
for index_i, a_i in enumerate(list_A):
    for index_j, a_j in enumerate(list_A):
        if index_i == index_j:
            continue
        if a_i % a_j == 0:
            # print(a_i, a_j)
            count += 1
            break
            
print(N - count)

Submission status: Time Limit Exceeded

Solution code:
#-*- using:utf-8 -*-
 
N = int(input())
A = list(map(int, input().split()))
c = 0
for i in range(N):
    for j in range(N):
        if(i == j):
            continue
        if A[i]%A[j] == 0:
            c = c+1
            break
print(N-c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
chols={}
ansls={}
ans=0
for i in range(n):
  s=l[i]
  st=s//2
  flag=True
  for j in range(ans):
    if s%ansls[j]==0:
      if s==ansls[j]:
        chols[s]=1
      flag=False
      break
    if ansls[j]>st:
      if ansls[ans-1]==s:
        flag=False
        chols[s]=1
      break
  if flag:
    ansls[ans]=s
    ans+=1
de=chols.keys()

print(ans-len(de))

Submission status: Time Limit Exceeded

Solution code:
n=input()
a_list=input().split()
for h in range(len(a_list)):
    a_list[h]=int(a_list[h])
num_suc=0

for i in range(len(a_list)):
    out=[]
    for j in range(len(a_list)):
        if i==j:
            continue
        else:
            if a_list[i]!=a_list[j]:
                q=a_list[i]//a_list[j]
                if a_list[j]*q==a_list[i]:
                    out.append("failed")
            else:
                out.append("failed")
        if "failed" in out:
            break
    if not "failed" in out:
        num_suc+=1

print(num_suc)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
i = 0
chk = 0
while len(a) > 0:
    if len(a) == 1:
        ans += 1
        break
    l = []
    for j in range(1, len(a)):
        if a[j]%a[0] != 0:
            l.append(a[j])
        elif a[j] == a[0]:
            chk = 1
    if chk == 0:
        ans += 1
    chk = 0
    a = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

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

m = 10**6+100
n_map = {}
v_a = []
nn_map = {}
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
    for j in range(2, ceil(m / i) + 1):
        nn_map[i * j] = True

v_a = [k for k, v in n_map.items() if v <= 1]

v_a.sort()
vv_a = []

for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)

print(len(vv_a))

Submission status: Time Limit Exceeded

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

n.sort()

counter = 0

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

print(l - counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = deque(sorted(a))
    ans = []
    S = True
    while len(A)>0:
        rem = []
        L = A.popleft()
        for i in A:
            if i == L:
                S = False
            if i%L == 0:
                rem.append(i)
        for r in rem:
            A.remove(r)
        if S:
            ans.append(L)
        S = True
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3
# coding: utf-8
n = int(input())
ha = input()
kita = ha.split(" ")
count = 0
for i in range(n):
    ifC = True
    for j in range(n):
        if(i != j):
            a = int(kita[i])
            b = int(kita[j])
            if(a%b == 0):
                ifC = False
                break
    if(ifC):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int, input().split()))
#A =list(set(A))
dupli = [x for x in set(A) if A.count(x) > 1]
ans = 0
for i,a in enumerate(A):
    flg = 0
    if a in dupli:
        continue
    for i2,a2 in enumerate(A):
        if i == i2:
            continue
        if a % a2 == 0:
            flg = 1
            break
    if flg == 0:
        #print(a)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = set(A)
B = ans.copy()

while True:
    for ai, aj in product(B, A):
        if ai == aj:
            continue
        if ai % aj == 0:
            ans.remove(ai)
            break
    if len(B) == len(ans):
        break
    B = ans.copy()

s = len(ans)
for bi in B:
    if A.count(bi) != 1:
        s -= 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)
wm = d[0][0]

while len(d):
    a, c = d.pop()
    if c == 1:
#         print(f'count {a=}, {c=}, {count=}, {d=}')
        count += 1
    if a == 1:
        break
    if len(d):
        m = d[0][0]
    else:
        m = a - 1
    if a * 2 <= m:
        d = [elm for elm in d if elm[0] % a]

print(count)

Submission status: Time Limit Exceeded

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

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass #sortされていない

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

#print(A)
ans = 0

for i in A:
    jdg = 0
    if L[i] != 1:
        continue
    P = divisor(i)
    for p in P:
        #print(p,i)
        if p in A and p != i:
            jdg += 1
            break
    if jdg == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def divisors(n):
    m = 1
    divs = []
    while m * m <= n:
        if n % m == 0:
            divs.append(m)
            if n != m * m:
                divs.append(n // m)
        m += 1
    divs.sort()
    return divs


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

cnt = 0
for i, a in enumerate(A):
    divs = divisors(a)[:-1]
    if len(set(divs) & set(A)) > 0:
        continue
    acc = A.count(a)
    if acc > 1:
        continue
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for i in range(N):
    tmp = set()
    if count[A[i]] >= 2:
        ans += 1
        happend.add(A[i])
        continue
    for j in range(1, int(A[i]**(1/2))+2):
        if A[i] % j == 0:
            if j in happend or A[i]//j in happend:
                ans += 1
                break
    happend.add(A[i])

print(N-ans)

Submission status: Time Limit Exceeded

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

num_li = [0]*(10**6+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(reverse=True)
    return divisors

#昇順
ai.sort()
min_ai = ai[0]

for i in range(n):
    num_li[ai[i]] += 1

ans = 0
    
for i in range(n):
    if num_li[ai[i]] > 1:
        continue
    #print(ai[i])
    flag = True
    div = make_divisors(ai[i])
    #print(div)
    #print(div)
    for j in range(len(div)):
        if div[j] < min_ai:
            break
        if div[j] == ai[i]:
            continue
        #print(div[j],div)
        if num_li[div[j]] > 0:
            flag = False
            break
    if flag == True:
        ans += 1
    #exit()
print(ans)

Submission status: Time Limit Exceeded

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

answers = []
ng_list = []
for a in a_list:
    if a in answers:
        if a not in ng_list:
            ng_list.append(a)
        continue

    if len(answers) == 0:
        answers.append(a)
        continue

    append_num = True
    for answer in answers:
        if a % answer == 0:
            append_num = False
            break
    if append_num:
        answers.append(a)

print(len(answers) - len(ng_list))

Submission status: Time Limit Exceeded

Solution code:
# import sympy

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]

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


ans = num

# flg2 = 0
# flg3 = 0
# if(2 in input_line):
#     flg2 = 1
# if(3 in input_line):
#     flg3 = 1

for i in range(num):
    now = input_line[i]
    # if(now!=2):
    #     if(now%2==0):
    #         if(flg2):
    #             ans-=1
    #             continue
    # if(now!=3):
    #     if(now%3==0):
    #         if(flg3):
    #             ans-=1
    #             continue
    divisor_now = make_divisors(now)
    for j in range(num):
        if(i!=j):
            if(input_line[j] in divisor_now):
                ans -= 1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input())):
n=int(input())
l=[int(x) for x in input().split()]
v=set()
l.sort(reverse=True)
ans=0
for i in range(n):
	c=0
	for j in range(n-1,-1,-1):
		if l[i]<l[j]:
			break
		if  i==j:
			continue
		if l[i]%l[j]==0:
			c=1
			#print(l[j],l[i])
			break
		if l[i]/l[j]<0:
			break
	if c==0:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

if __name__ == '__main__':
	N = int(input())
	A = [int(a) for a in input().split()]

	lst = [0] * N

	AA = copy.copy(A[:])
	A.sort()

	i = 0
	while(i < len(A)-1):
		a = copy.copy(A[0:i+1])
		for j in range(i+1,len(A)):
			if A[j]%A[i] != 0:
				a.append(A[j])
		A = copy.copy(a[:])
		i += 1

	c = 0
	for a in A:
		if AA.count(a) == 1:
			c += 1

	print(c)

Submission status: Time Limit Exceeded

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

def func1(a):
    a.sort()
    cnt=0
    chker={}
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
        else:
            for j2 in chker:
                j=int(j2)
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
        chker[str(i)]=1
    print(cnt)
func1(a)

Submission status: Time Limit Exceeded

Solution code:
import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    # a = list_a.pop(0)
    # list_a.append(a)
    list_a.append(list_a.pop(0))
print(len(list_input) - anti_ans)

Submission status: Time Limit Exceeded

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

As = sorted(As)
c = []
e = set()
p = 0

for a in As:
    if a == p:
        e.add(a)
    nd = True
    for b in c:
        if a % b == 0:
            nd = False
            break
    if nd:
        c.append(a)
    p = a
c = [v for v in c if v not in e]
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
 
  
def handle(i,a):
  tmp = list(map(lambda x: i%x, a))
  if tmp.count(0) == 1:
    return 1
  else:
    return 0

result = 0
for i in a:
  result += handle(i,a)
  
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
# a = sorted(a)
a.sort()
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()
check = True
ans = 0
double = []
for i in range(n):
    if not i == 0:
        if a[i-1] == a[i]:
            double.append(a[i])
    for j in range(0, i):
        if not a[j] == 1:
            if a[j]*2 > a[i]:
                break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True
# print(a)
# print(ans)
# print(double)
for i in set(double):
    ans -= a.count(i)
# ans -= len(set(double))
# ans -= len(double)
print(ans)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
def d():
    import numpy as np
    N = int(input())
    A = np.array(list(map(int, input().split())))
    uniques, counts = np.unique(A, return_counts=True)
    ans = 0

    for i, a in enumerate(uniques):
        if counts[i] > 1:
            continue
        else:
            B = uniques[uniques <= a/2]
            if 0 not in a % B:
                ans += 1

    print(ans)


##########
if __name__ == "__main__":
    d()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())
lis=list(map(int, input().split()))
lis.sort()
ans=0
f=0
arr_se=np.array(list(set(lis)))

for i in range(0,N-1):
    if lis[i]==lis[i+1]:
        f=1
    elif f:
        f=0
        if lis[i]==lis[i+1]:
            f=1
            
    else:
        if sum(lis[i]%arr_se==0) == 1:
            ans+=1
    
if f==0:
    if sum(lis[-1]%arr_se==0) == 1:
        ans+=1
print(ans)