Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

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

a_sorted = sorted(a)
divisible_list = [True] * n

for i in range(n-1):
    if not divisible_list[i]:
        continue
    for j in range(i+1, n):
        if a_sorted[j] == a_sorted[i]:
            divisible_list[i] = False
        if a_sorted[j] % a_sorted[i] == 0:
            divisible_list[j] = False
print(sum(divisible_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

div = set(A)
cnt = Counter(A)
ans = 0

def divisors(n):
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
for a in A:
    if cnt[a] >= 2:
        continue
    flg = True
    for d in divisors(a):
        if d == a:
            continue
        if d in div:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    div=[]
    i = 1
    ap=div.append
    while i*i <= n:
        if n % i == 0:
            ap(i)
            ap(n//i)
        i += 1
    return set(div)-{n}
def main():
    from collections import Counter
    n,*a=map(int,open(0).read().split())
    d=Counter(a)
    s=set(a)
    c=0
    for t in s:
        if d[t]<2:
            for t in make_divisors(t):
                if t in s:break
            else:c+=1
    print(c)
main()

Submission status: Time Limit Exceeded

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

def calc():
    n = int(input())
    a = [int(x) for x in input().split()]
    k = [0] * n
    cnt = 0
    for i in range(n):
        for j in range(i):
            if i == j:
                continue
            if k[i] == 0 and a[i] % a[j] == 0:
                cnt += 1
                k[i] = 1
            if k[j] == 0 and a[j] % a[i] == 0:
                cnt += 1
                k[j] = 1
    print(n - cnt)

calc()

Submission status: Time Limit Exceeded

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

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

        if count == N:
            li.append(i+1)

print(len(li))

Submission status: Time Limit Exceeded

Solution code:
def divisor(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0

for i,num in enumerate(A):
    if i > 0 and A[i-1] == num:
        continue
    if not divisor(num) & set(A[i+1:]):
        ans += 1

print(ans)

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):
    lower_divisors , upper_divisors = [], []
    i = 2
    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]
m = [0] * MAX
t = set()
for i in range(n):
  m[a[i]] += 1
  if m[a[i]] == 1:
    t.add(a[i])
  elif m[a[i]] == 2:
    t.discard(a[i])
#print(m[:30])
mx = max(a)
ans = 0
tlen = len(t)
for idx in range(tlen):
  i = t.pop()
  #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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
from collections import defaultdict

def main():
    n = int(input().strip())
    a_list = map(int, input().split())

    a_list = sorted(a_list)
    ans = set()
    dup_ans = set()
    ans_cands = set(a_list)
    for a in a_list:
        if a in ans:
            dup_ans.add(a)
            continue
        if a not in ans_cands:
            continue

        ans_cands.remove(a)
        new_cands = set(ans_cands)
        for cand in ans_cands:
            if cand % a == 0:
                new_cands.remove(cand)
        ans_cands = new_cands

        ans.add(a)

    print(len(ans) - len(dup_ans))

# def main():
#     n = int(input().strip())
#     a_list = map(int, input().split())
#
#     ans_set = set()
#     dup_set = set()
#     for a in sorted(a_list):
#         if a in ans_set:
#             dup_set.add(a)
#             continue
#
#         divs = set(make_divisors(a))
#         if divs.isdisjoint(ans_set):
#             ans_set.add(a)
#
#     print(len(ans_set) - len(dup_set))
#
#
# 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]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

k=0
while k<=len(alist)-1:
    unit = alist[k]
    ls =  [i for i in alist if i%unit!=0]
    alist = [unit] + ls
    k+=1

choufuku = 0
choufukulist = [x for x in set(alistold) if alistold.count(x) > 1]
for num in alist:
    if num in choufukulist:
        choufuku += 1

print(k-choufuku)

Submission status: Time Limit Exceeded

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

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]

divisors_list = {}
for i in A:
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    try:
      divisors_list[j].append(k)
    except:
      continue

pass_li = {}
for i in range(N):
  pass_li[i] = 1

for i in range(N):
  tmp = pass_li[i]
  for j in divisors_list[A[i]]:
    pass_li[j] = 0
  pass_li[i] = tmp 
  
  
print(sum(pass_li.values()))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
import copy
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
a = list(map(int, input().split()))
ans = 0
times = defaultdict(int)
for k in a:
    times[k] += 1
for j in a:
    if times[j] > 1:
        continue
    tmp = set(a)
    # tmp.remove(j)
    table_ = set(make_divisors(j))
    for i in tmp:
        if i == j:
            continue
        if i in table_:
            break
    else:
        ans += 1
    # for i in table_:
    #     if i == j:
    #         continue
    #     if i in tmp:
    #         break
    # else:
    #     ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    s_ba = ba//2+1
    index = bisect.bisect_right(li, s_ba)
    tmp_li = li[:index+1]
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

N, *A = map(int, read().split())
A = np.array(A)
cnt = np.zeros(N)
for i, a in enumerate(A):
    acc = (A % a) == 0
    cnt = cnt + acc

print(sum(cnt == 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = deque(map(int, input().split()))
ban = {x for x in set(A) if A.count(x) > 1}
D = deque(sorted(list(set(A))))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
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())
S = list(map(int,readline().split()))
A = sorted(set(S))
q = deque(A)
ans = 0
while q:
  t = q.popleft()
  if t == 1:
    if S.count(1) == 1:
      print(1)
      sys.exit()
    else:
      print(0)
      sys.exit()
  if S.count(t) ==1:
    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:
import sys

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

    return divisors


def main():

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

    d = dict()
    for i in range(N):
        if A[i] in d:
            d[A[i]] += 1
        else:
            d[A[i]] = 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.buffer.read


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    A.sort()
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A_set:
        if C[a] != 1:
            continue
        D = divisors(a)
        if all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(1, n+1):
    c = 0
    for j in range(1, n+1):
        if i == j:
            pass
        else:
            if a[i-1] % a[j-1] == 0:
                c += 1
    if c == 0:
        res.add(i)

print(len(res))

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:
    flg = True
    if A[i] > 1:
        continue
    for j in range(1,int(pow(i,0.5))+2):
        if not i%j:
            if A[j] and i != j:
                flg = False
                break
            if j != i//j and A[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

l = [[] for i in range(2*10**7+1)]

def waru(k,l):
    for i in range(1,int(math.sqrt(k))+1):
        if k % i == 0:
            l[i].append(k)
            l[k//i].append(k)
            
for i in a:
    waru(i,l)
ans_l = [0 for i in range(2*10**5+1)]
for i in a:
    for j in l[i]:
        ans_l[j] += 1

ans = 0
for i in a:
    if ans_l[i] == 1:
        ans += 1

print(ans)

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 and a[i] % a[j] == 0:
            break
        if j == n - 1:
            cnt += 1
 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = sorted(list(map(int, input().split())))
As_set = set(As)

i = 0
while i < N - 1:  
  j = i + 1
  while j < N:
    if As[j] % As[i] == 0:
      if As[j] in As_set:
        As_set.remove(As[j])
      As.pop(j)
      N -= 1
    else:
      j += 1
  i += 1
  
print(len(As_set))

Submission status: Time Limit Exceeded

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

a.sort()
p = []
k = set()

while a:
    prime = a[ 0 ]

    p.append( prime )

    i = 0
    flag = 0
    while i < len( a ):
        if a[ i ] == prime and flag == 1:
            k.add( prime )
        flag = 1
        if a[ i ] % prime == 0:
            a.pop( i )
            continue
        i += 1

# print( p, k )
print( len( p ) - len( k ) )

Submission status: Time Limit Exceeded

Solution code:
import sys,collections
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
x=list(set(l))
x.sort()
ans=0
s=set()
if len(x)==0:
  print(0)
else:
  for y in x: 
    if c[y]<2:
      memo=0
      for j in range(1,int(y**0.5)+1):
        if y%j == 0 :
          if y//j in s or j in s:
            memo-=1
            break
      if memo==0:
        ans+=1     
    s.add(y)
  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)
    z = []
    for i in A:
        y[i] += 1
        if y[i] == 1: z.append(i)


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


        f = 1
        for j in z:
            if i == j: continue
            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().strip())
A = [int(v) for v in input().strip().split(" ")]

A = sorted(A)
visited = {}
for i in range(N):
    visited[A[i]] = 0

counter = 0
for i in range(N):
    count_flag = True
    mark = 0
    if visited[A[i]] == 1:
        continue

    for j in range(N):
        if i == j:
            continue
        if A[i] < A[j]:
            break
        if A[i] % A[j] == 0:
            count_flag = False
            mark = j
            break
    if count_flag:
        counter += 1

    for j in range(mark, N):
        if A[i] % A[j] == 0:
            visited[A[j]] = 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  not_divisible_list = [True]*N
  not_divisible_count = N
  A = [int(x) for x in input().split(" ")]
  A.sort()
  # set_A = set(A)

  for i, a_t in enumerate(A):
    for j, a in enumerate(A[i+1:]):
      if a_t==a:
        not_divisible_list[i] = False
      if a%a_t==0:
        # print(a_t, ":", a)
        not_divisible_list[i+1+j] = False
  # print(A)
  print(not_divisible_list.count(True))

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

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

    from collections import deque
    from collections import Counter

    dq = deque(a)
    ans = []
    cnt = Counter(a)
    if cnt[1] == 1:
        print(1)
        return
    if cnt[1] > 1:
        print(0)
        return
    for i in range(n):
        if len(dq) == 0:
            break

        tmp = dq.popleft()

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

    print(len(ans))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def make_divisors(n):  # nの約数を列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def main():
    # 約数
    N = ir()
    A = lr()
    A.sort()
    answer = 0
    bl = [False] * (A[-1]+1)
    for i, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = True
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x]:
                flag = False
                break
        bl[a] = True
        if flag:
            answer += 1

    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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


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

a.sort()
a_max = a[-1]
div = [0]*(a_max+1)
c = Counter(a)
#print(c)
count = 0
already = []
for i in range(n):
    if c[a[i]] != 1:
        div[a[i]] = 1
        continue
    div_a = divisor(a[i])
    for j in div_a:
        if div[j] == 1:
            break
    else:
        count += 1
        div[a[i]] = 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
A_list = list(map(int, input().split()))
sorted_A_list = sorted(A_list)

ans = 0

#print(sorted_A_list)
i=0
while i<len(sorted_A_list):
#for i in range(N):
    ans = ans+1
    flg=0
    if not i == len(sorted_A_list)-1:
        if sorted_A_list[i] == sorted_A_list[i+1]:
            ans = ans-1
            i=i+1
            continue
    for j in range(i):
        if sorted_A_list[i]%sorted_A_list[j] == 0:
            ans = ans-1
            #print(sorted_A_list[i])
            sorted_A_list.pop(i)
            flg=1
            break
    if flg==0:
        i=i+1


print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

ans = n
selfpopflag = 0
i = 0
while i <= n - 1:
    j = i + 1
    while j <= n - 1:
        if a[j] % a[i] == 0:
            if a[j] == a[i]:
                selfpopflag = 1
            ans -= 1
            a.pop(j)
            n -= 1
            j -= 1
        j += 1
    if selfpopflag == 1:
        ans -= 1
        selfpopflag = 0
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
ans=0
List=[]
ans+=1
flag=0
List.append(a[0])

for i in range(1,n):
    m=len(List)
    for j in range(m):
        if (a[i]==List[-1]):
            if (flag==0):
                ans-=1
            flag=1
            break
        elif (a[i]%List[j]==0):
            flag=0
            break
        elif (a[i]<2*List[j]):
            List.append(a[i])
            flag=0
            ans+=1
            break
        elif(j==m-1):
            List.append(a[i])
            flag=0
            ans+=1
            break
print(ans)

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def Sieve(N, AList):
    AList.sort()
    N_NotDivisible = 0
    while( len(AList) > 0 ):
        if(len(AList) > 1):
            if(AList[0]!= AList[1]):
                N_NotDivisible+= 1
                value = AList[0]
                AList = [ i for i in AList if i % value != 0 ]
            else:
                index = 2
                while(index < len(AList) and AList[index-1] == AList[index]):
                    index += 1
                for i in range(index):
                    AList.pop(0)

        else:
            N_NotDivisible+= 1
            break
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
an = list(map(int, sys.stdin.readline().rstrip().split()))

count=0

for i in range(n):
    count += 1
    for j in range(n):

        if i == j:
            pass
        elif an[i]%an[j]==0:
            count -= 1
            break



print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = list(map(int,input().split()))
count = 0
n = 0
for l in L:
    L_s = L.copy()
    L_s.pop(n)
    n += 1
    for l_s in L_s:
        if l%l_s == 0:
            break
    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
len = len(A)
new = sorted(A, reverse=True)
cnt = 0
for i in new:
  cnt += 1
  cnt2 = 0
  for j in new:
    cnt2 += 1
    if cnt != cnt2 and i%j == 0:
      len =len - 1
      break
print(len)

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(pow(i,0.5))+2):
        if not i%j:
            if A[j] and i != j:
                flg = False
                break
            if j != i//j and A[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    q = deque(a)
    ans = 0

    while q:
        a = q.popleft()
        m = len(q)
        for i in range(m):
            b = q.popleft()
            if i == 0 and b == a:
                ans -= 1
            if b % a != 0:
                q.append(b)
        else:
            ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
line = input().split()
line=[int(i) for i in line]

ans=0
for m in range(num):
  for n in range(num):
    if m!=n:
      if line[m]%line[n]==0:
        ans-=1
        break
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    A.sort()
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A_set:
        if C[a] != 1:
            continue
        D = divisors(a)
        if all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    for i, div_num in enumerate(A):
        flag = 0
        if div_num in A[i + 1:]:
            flag = 1
        for num in A[i + 1:]:
            if num % div_num == 0:
                A.remove(num)

        if flag != 0:
            A.remove(div_num)

    print(len(A))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

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

    flag=0#warenai

    for i in range(1,math.floor(math.sqrt(x))+1):
        if x%i==0 and (i in Y or x/i in Y):
            flag=1
            break

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

print(len(Y)-onaji)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
A_counters = Counter(A)

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

nums = set()
ans = 0
for a in A:
    if make_divisors(a) and A_counters[a] == 1:
        ans += 1
    nums.add(a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [int(x) for x in input().split()]
A.sort()
n=0
index=[]
index_d=list(range(N-1))
 
for i in range(N):
  k=0
  if i==0:
    for j in range(N-i-1):
      if A[N-i-1]%A[j] == 0:
        n=n+1
        index.append(j)
        index_d.remove(j)
        if j!=N-i-2:
          index_d.remove(N-i-2)
        break
  elif A[N-i-1]==A[N-i]:
    n=n+1
  else:
    for j in index:
      if A[N-i-1]%A[j] == 0 and j<N-i-1:
        n=n+1
        k=1
        break
    if k==0:
      for j in index_d:
        if A[N-i-1]%A[j] == 0 and j<N-i-1:
          n=n+1
          index.append(j)
          index_d.remove(j)
          if j!=N-i-2:
            index_d.remove(N-i-2)
          break

        
print(N-n)
 
"""
10
33 18 45 28 8 19 89 86 2 4
5
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# import sympy
from collections import defaultdict, Counter
# def factors(N): #約数を全て求める。ただし、順不同
#     from collections import deque
#     ret = deque()
#     middle = int( N**(1/2))
#     for i in range(1, middle):
#         if N%i == 0:
#             ret.append(i)
#             ret.append(N//i)
            
#     if N%middle == 0:
#         ret.append(middle)
#         if middle != N//middle:
#             ret.append(N//middle)
#     return ret

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

    # divisors.sort()
    return divisors


def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    for a in A:
        if CA[a] > 1:
            continue
        for p in make_divisors(a):
            if p == a:
                continue
            if d[p]:
                break
        else:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

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


A = np.array(sorted(A))

i = 0
dd = 0

while len(A) > 0:
    a = A[0]
    i += 1
    double_ind, = np.where(A[1:] == a)
    dd += 1 if len(double_ind)>0 else 0
    new_ind = np.where(A[1:] % a!=0)
    A = A[1:][new_ind]

print(i-dd)