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

count = 0
A = list(map(int, input().split()))

s = set([])
for i in range(n):
  for j in range(n):
    if i != j and A[i] % A[j] == 0:
      s.add(i+1)
      
print(n-len(s))

Submission status: Time Limit Exceeded

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

A.sort()
A_set = set(A)
count = 0
last_num = 0
flag = True
now_num = 0
half_num = 0

count_flag = False

if A.count(1) == 1:
    print(1)
    exit()
for i in range(N):
    count_flag = True
    now_num = A[i]
    half_num = A[i]/2
    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:
        for j in range(0, i):
            if A[j] > half_num:
                break
            if now_num % A[j] == 0:
                count_flag = False
                break
        if count_flag:
            if not flag:
                flag = True
            count += 1
        last_num = A[i]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
Ain=list(map(int,input().split())) 
ansn=0
A=set(Ain)
A=list(A)
A.sort()
A2=list(t for t in A)


ans=[]
while len(A2)!=0:
    ans.append(A2[0])
    temp=[]
    for facs in A2:
        if facs%A2[0]==0:
            temp.append(facs)
    for temps in temp:
        A2.remove(temps)

for anss in ans:
    if Ain.count(anss)==1:
        ansn+=1
print(ansn)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
al = [int(i) for i in 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[:-1]
  
import collections

if n == 1:
  print(1)
else:
  total = 0
  ss = set(al)
  c = collections.Counter(al)
  for num in al:
    if c[num] >= 2:
      continue
    for d in make_divisors(num):
      if d in ss:
        break
    else:
      total += 1
  print(total)

Submission status: Time Limit Exceeded

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

ans = 0 

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')


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


def main():

    N = in_n()
    A = list(in_nn())

    d = defaultdict(lambda: 0)
    for i in range(N):
        d[A[i]] += 1

    ans = 0
    for i in range(N):
        for num in make_divisors(A[i]):
            #print(A[i], num)
            if num == A[i]:
                if d[num] >= 2:
                    break
            else:
                if d[num] >= 1:
                    break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=input().split()
nl=[]
for x in a:
  nl.append(int(x))
  
nl.sort(reverse=True)

count=0
while nl!=[]:
  p=nl[-1]
  if len(nl)==1:
    count+=1
    break
  elif nl[-2]!=p:
    count+=1
    del nl[-1]
  else:
    while nl!=[] and nl[-1]==p:
      del nl[-1]
  len0=len(nl)
  for i in range(len0-1,-1,-1):
    if nl[i]%p==0:
      nl[i]=0
  newl=[]
  for x in nl:
    if x!=0:
      newl.append(x)
  nl=newl
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
for a in range(N):
  newA = [A[a]%n for n in A]
  newA.pop(a)
  if 0 in newA:
    ans = ans
  else:
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def check_prime(k):

    if k == 1:return 1
    for i in rec:
        if i > k // 2:break
        if k % i == 0:return 0
    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
rec = [a[0]]
double = dict()
for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        rec.append(a[i])
        continue

    if double.get(a[i]):continue
    
    temp = check_prime(a[i])
    if temp:
        rec.append(a[i])
        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 val in A:
    tmp = set()
    for i in range(1, int(val**(1/2))+2):
        if val % i == 0:
            tmp.add(i)
            tmp.add(val//i)

    if len(tmp & happend) >= 1 or count[val] >= 2:
        ans += 1
    happend.add(val)

print(N-ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_list = sorted(a_list)
flag  = [0]*n

ans = 0
for i in range(len(a_list)):
    if flag[i] == 1:
        continue
    if i == n-1:
        ans += 1
        break
    if 0 not in flag:
        break
    flag[i] = 1
    
    if a_list[i] != a_list[i+1]:
        ans += 1
    for j in range(i+1,len(a_list)):
        if a_list[j]%a_list[i] == 0:
            flag[j] = 1

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(len(AS)):
    if AS[i] == 0:
        continue
    elif i == n-1:
        AS[i] = 1
        break
    dup = 0
    for j in range(i+1, len(AS)):
        if AS[j] % AS[i] == 0:
            if AS[j] == AS[i]:
                dup += 1
            AS[j] = 0
    if dup != 0:
        AS[i] = 0
    else:
        AS[i] = 1

print(sum(AS))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    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)

resolve()

Submission status: Time Limit Exceeded

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

import math
ans=0
for i in range(n):
    check=True
    for k in range(i):
        if A[k]/2>(A[i]):
            break
        if A[i]%A[k]==0:
            check=False
            break
    if i!=n-1:
        if A[i]==A[i+1]:
            check=False
    if check:
        ans+=1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl
import sys
input = sys.stdin.readline

def main() :
    N = int(input())
    A_list = [int(i) for i in input().split()]
    A_list.sort()
    A_counter = cl.Counter(A_list)

    # memo 最小値が2つあるとき

    cnt = 0
    for i in range(N) :
        not_divisible = True
        if (A_counter[A_list[i]] > 1) :
            # 数列内に同じものを含んでいる場合は必ず割り切れるのでパスする
            continue

        for k in range(i) : 
            # print(A_list[i],A_list[k])
            if (A_list[i] % A_list[k] == 0) :
                not_divisible = False
                # print("divisble", A_list[i],A_list[k])
                break
        if (not_divisible) :
            cnt += 1

    print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    one_cnt = 0
    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

        fail = False
        for j in range(0, min(i + 2, n)):
            if i == j:
                continue
            j_value = a_list[j]
            mod = 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:
n = int(input())
l = list(map(int, input().split()))
l.sort()
l_b = [True] * n
for i in range(n):
    if l_b[i] == False:
        continue
    v = l[i]
    if i < n-1 and v == l[i+1]:
        l_b[i] = False
    for j in range(i+1, n):
        if l_b[j] and l[j]%v == 0:
            l_b[j] = False
print(sum(l_b))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        if i < n-1 and a[i] == a[i+1]:
            dic[a[i]] = 1
            continue
        flag = 1
        for e in dic:
            if e >= int(a[i]**2)+1:
                break
            if a[i]%e == 0:
                flag = 0
                break
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

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, reverse=True)

    x = {}
    for i in a:
        x[i] = True

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

left = 0
right = n - 1
ans = 0

for i in range(n):
    left = 0
    right = n - 1
    while left <= right:
        if i == left == right:
            left, right = left + 1, right - 1
            continue

        elif i == left:
            if a[i] % a[right] == 0:
                break

        elif i == right:
            if a[i] % a[left] == 0:
                break

        else:
            if a[i] % a[left] == 0 or a[i] % a[right] == 0:
                break

        left, right = left + 1, right - 1

    if left > right:
        ans += 1

print(ans)

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]]
bl=[]

def ok(wa,item,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,bl)
    return

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

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

"""
def ok(wa,item,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,bl)
    return

for item in a[1:]:
    ok(wa,item,bl)
"""

Submission status: Time Limit Exceeded

Solution code:
#! env/bin/local python3


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

    divisors.sort()
    return divisors


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

a_divisors = {ac: set(divisors_f(ac)) for ac in a}
counter = 0
for key, value in a_divisors.items():
    a.remove(key)

    if len(set(a) & value) > 0:
        counter += 1
    a.append(key)

print(len(set(a)) - counter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
idx = np.argsort(A)
A = np.sort(A)
Z = np.zeros(N)

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        for j in range(i):
            if Z[j] == 0 and A[i] % A[j] == 0:
                flag = False
                Z[i] = 1
                break
        if flag:
            result += 1
    return result

print(get_result())

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

        res = calc_divisors(A[i],st)
        if res:
            ans += 1
    
    print(ans)

def calc_divisors(n,st):
    res = False
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            res = func(i,st,n)
            if res:
                return False
            
            if (i*i != n):
                res = func(n//i,st,n)
        
        if res:
            return False

    return True

def func(i,st,n):
    if i == n:
        return False
    if i in st:
        return True
    else:
        return False

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a=list(map(int,input().split()))
a.sort(reverse = True)
from collections import deque
from collections import Counter as cnt
aaa = dict(cnt(a))

maa = a[0]//2
ma = maa+1


ans = []
a = deque(a)
while True:
    if len(a) <1:
        break
    i = a.pop()
    ans.append(i)

    b = deque()
    while len(a)>0:
        j = a.pop()
        if j%i !=0:
            b.appendleft(j)
    a = b.copy()

    if i >= ma:
        ans += a
        break





mans = 0
for i,v in aaa.items():
    if (i in ans) & (v == 1) :
        mans+=1

print(mans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

input()
a = []
r = 0
for k, g in groupby(sorted(map(int, input().split()))):
  for x in a:
    if k % x == 0:
      break
  else:
    a.append(k)
    if len(list(g)) == 1:
      r += 1
print(r)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

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

alist.sort()
blist=alist
blist=list(set(alist))

for i in range(n-1):
    for j in range(i+1,n):
        if alist[j]%alist[i]==0:
            if alist[j] in blist:
                blist.remove(alist[j])
'''
ans=0
for i in range(len(blist)):
    if blist[i]>0:
        ans+=1

print(ans)
'''
print(len(blist))

Submission status: Time Limit Exceeded

Solution code:
import sys
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
from collections import deque
a=ii()
l=list(mi())
l=sorted(l)
l=deque(l)
ans=[l.popleft()]
c=set()
while l:
  p=l.popleft()
  t=True
  if p==ans[-1]:
    c.add(p)
  else:
    for j in ans:
      if p<2*j:
        break
      elif p%j==0:
        t=False
        break
    if t:
      ans.append(p)
print(len(ans)-len(c))

Submission status: Time Limit Exceeded

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

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1

    for i in range(1,min(int(ai**(1/2)+7),ai)):
        if ai%i==0:
            if i in sa and i!=ai:
                ans-=1
                break
            if i>1 and ai//i in sa:
                ans-=1
                break
print(ans)

Submission status: Time Limit Exceeded

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

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

    N = LI()
    A = LI()

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

    ans = 0
    for i in A:
        if i > 1:
            if y[1] : continue
        if y[i] > 1: continue

        f = 1
        for j in range(2,int(math.sqrt(i))+1):
            if i % j == 0 and (y[j] or y[i//j]):
                f = 0
                break

        ans += f

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

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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

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

#print(A)
ans = 0

for i in reversed(range(N)):
    a = A[i]
    if L[a] != 1:
        continue
    jdg = 0
    index = bisect.bisect_right(A,a//2)
    #print(index,a)
    for k in range(index):
        if a % A[k] == 0:
            jdg += 1
            break
    if jdg == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

L = 0
for n,i in enumerate(a):
    H = 0
    if 2 in a and i!=2 and i%2 == 0:
        H=1
    elif 3 in a and i!=3 and i%3 == 0:
        H=1
    elif 5 in a and i!=5 and i%5 == 0:
        H=1
    else:
        for j in a[a.index(i)+1:]:
            if i % j == 0:
                H = 1
                break
    if H == 0:
        L+=1
print(L)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

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

count=N

if 1 in A:
  if A.count(1)>1:
    print(0)
  else:
    print(1)
  exit()

for i in range(N):
  n=A[i]
  B=A.copy()
  B.pop(i)
  for j in range(1, int(n**0.5)+1):
    if n % j == 0:
      if j in B:#count
        #print(n,j)
        count-=1
        break
      if j != n // j:
        if n//j in B:#count
          #print(n,n//j,"//")
          count-=1
          break

print(count)

Submission status: Time Limit Exceeded

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

A.sort()
ans=0

B=[1]*N

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

print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
_n = int(input())
_a = list(map(int, input().split(" ")))
_counter = 0

for _i in range(_n):
  for _j in range(_n):
    if _i != _j and _a[_i] % _a[_j] == 0:
      break
    elif _j == _n - 1:
      _counter += 1
print(_counter)

Submission status: Time Limit Exceeded

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

for i in a:
  c = a.count(i)
  lst = [i%j for j in a]
  if lst.count(0) == 1:
    iter = iter + 1
print(iter)

Submission status: Time Limit Exceeded

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

# if A.count(A[0])==N:
#     print(0)
#     exit(0)

flag = [0 for _ in range(N)]
for n in range(N):
    if flag[n] == 1: continue
    
    for i in range(n+1,N):
        if flag[i] == 1: continue
        if A[i]%A[n] == 0:
            flag[i] = 1
    if n < N-1 and A[n] == A[n+1]:
        flag[n] = 1

print(N-sum(flag))

Submission status: Time Limit Exceeded

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

ans = 0

A.sort()

for i in range(0, len(A)):

    if A.count(A[i]) >= 2:
        # 同じ値が存在すれば該当しない
        pass

    else:
        # 同じ値がないものについて
        # A[i]/2 以下で最大の要素のインデックスを探す
        for p in reversed(range(int(A[i]/2 + 1))):
            if p in A:
                j_max = A.index(p)
                break
        else:
            # 半分より小さい値がAにない数は割り切れない
            j_max = -1

        for j in range(j_max+1):
            if A[i] % A[j] == 0:
                break
        else:
            #print(A[i], j_max)
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

if (A.count(1) > 1):
    print(0)
    exit()
if (A.count(1) == 1):
    print(1)
    exit()

A.sort()
indexList = [1] * N
for i in range(N - 1):
    if (indexList[i] == 0):
        continue
    else:
        adopter = -1
        if (A.count(A[i]) > 1):
            for k in range(A.count(A[i])):
                indexList[i + k] = 0
                adopter += 1
        else:
            adopter = 0
        for j in range(i + 1 + adopter, N):
            if (A[j] % A[i] == 0):
                indexList[j] = 0

print(indexList.count(1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
P = set(A)
cnt = Counter(A)

def divisors(n):
    divisors = []
    R = int(n**(0.5)) + 1
    for i in range(1, R):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    # divisors.sort(reverse=True)  # ソート
    return divisors

ans = 0
for a in A:
    if cnt[a] > 1:
        continue
    for d in divisors(a):
        if d != a and d in P:
            break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#デフォルト
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

a.sort(reverse=True)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(cnt)

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

cnt = [0] * 1000001

for i in range(n):
    cnt[p[i]] += 1

p = sorted(p, reverse=True)

ans = n

for i in range(n):
    c = make_divisors(p[i])
    for j in range(len(c)):
        if (not (c[j] == p[i]) or cnt[c[j]]>1) and cnt[c[j]]:
            ans -= 1
            break
print(ans)

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)

while len(d):
    a, c = d.pop()
    if c == 1:
        count += 1
    if a == 1:
        break
    d = [elm for elm in d if elm[0] % a]

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

if N==1:
    print(1)
    exit()

A.sort()
ans=0

if A[0]!=A[1]:
    ans=1

if A[0]==1 and A[1]==1:
    print(0)
    exit()

elif A[0]==1 and A[1]!=1:
    print(1)
    exit()

for i in range(1,N):
    if A[i]==A[i-1] or ((i!=N-1) and (A[i]==A[i+1])):            
        continue
    D=make_divisors(A[i])
    if len(D)==2:
        ans+=1
        continue
    elif len(set(D)&set(A[0:i]))==0:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
d={}
ans=0
s1=0
d={i:0 for i in range(1,10**6)}
for i in arr:
    if i==1:
        s1+=1
    if i in d:
        d[i]+=1
    else:
        d[i]=1
if s1!=0:
    if s1>1:
        print(0)
        quit()
    else:
        print(1)
        quit()
for i in range(n):
    x=arr[i]
    if d[x]==1:
        f=1
        for j in range(2,int(x**0.5)+1):
            y=x//j
            if (d[j]>=1 and x%j==0) or ( d[y]>=1 and x%(y)==0):
                f=0
                break
        if f==1:
             ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
an = np.array([int(a) for a in input().split()], dtype=np.int64)
res = 0
for i in range(n):
    an_slice = np.copy(an)
    an_slice = np.delete(an_slice,i)
    # diveded = np.array([an[i] % a for a in an_slice])
    diveded = an[i] % an_slice
    if diveded[diveded != 0].size == an_slice.size:
        res+=1

print(res)

Submission status: Time Limit Exceeded

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


A.sort()
#print(A)


r = len(A)

t = 0

for i in range(N):
    r -= 1
    #print("r",r)
    if r <= 0:
        break
    #print("i", i)
    tmp = A[i]
    #print("tmp",tmp)
    l = len(A)
    #print("l", l)
    tmp2 = 0
    flag = 1
    for j in range(i+1 , l):
        j -= tmp2
        #print("j",j)
        #print("A",A)
        if A[j] == tmp and flag == 1:
            t += 1
            flag = 0
        if A[j] % tmp == 0:
            #print("A[j]", A[j])
            del A[j]
            tmp2 += 1
            r -= 1
print(len(A)-t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
    divide_flag = 0
    for j in range(N):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            divide_flag = 1
            break
    if divide_flag == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

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

ans=0

for i in range(N):
    add=1
    for j in range(N):
        if j!=i:
            if A[i]<A[j]:
                break
            if A[i]%A[j] == 0: 
                add=0
                break
    ans+=add

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=a[:]
b2=[]
b3=[]
for i in range(len(a)):
  if len(b)==0:
    break
  if a[i] not in b :
    continue
  for j in b:
    if j % a[i]!=0:
      b2.append(j)
  b=b2[:]
  b2.clear()
  b3.append(a[i])
c=0
for m in b3:
  if a.count(m)==1:
    c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = sorted([int(a) for a in input().split()])
bye = [x for x in set(A) if A.count(x) > 1]
A = np.array(A)
for a in A:
    A = np.where((A != a) & (A % a == 0), 0, A)
A = (set(A))
for x in bye:
    try:
        A.remove(x)
    except:
        pass

try:
    A.remove(0)
except:
    pass    
print(len(A))

Submission status: Time Limit Exceeded

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

while i < N:
    j = 1
    while i+j <= N-1 and A[i] == A[i+j]:
        j += 1
    if j > 1:
        ans += j 
        s.add(i)
        i += j
    else:
        border, sadd = A[i] // 2, True
        for j in s:
            if A[i] % A[j] == 0:
                ans += 1
                sadd = False
                break
            elif A[j] > border:
                break
        if sadd:
            s.add(i)
        i += 1

print(N - ans)