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

num = 0
A = sorted(A)

for i in range(N):
    flag = True

    if i > 10:
        if A[i] % A[0] == 0:
            flag = False
        if A[i] % A[1] == 0:
            flag = False
        if A[i] % A[2] == 0:
            flag = False
        if A[i] % A[3] == 0:
            flag = False
        if A[i] % A[4] == 0:
            flag = False

    if 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(map(int,input().split()))
p=[[] for i in range(n)]
ans=n

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]

for i in range(n):
    p[i]+=make_divisors(a[i])

#print(p)
#print(a)
dp=[0]*n
from collections import deque
que = deque([])
for i in range(n):
    que.append(a[i])
    s=que.popleft()
    for j in range(n):
        if i!=j:
            if s in p[j] and dp[j]!=1:
                dp[j]=1
                #print(a[i],p[j],dp)
print(dp.count(0))

Submission status: Time Limit Exceeded

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

for val in A:
    if count[val] >= 2:
        ans += 1
        happend.append(val)
        continue
    for j in happend:
        if val % j == 0:
            ans += 1
            break
    happend.append(val)

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    A.sort()
    
    A=deque(A)

    escape=deque([])
    while len(A)>0:
        minute=A.popleft()
        tmp=deque([])

        flag=0
        while len(A)>0:
            maximum=A.pop()
            if maximum==minute:
                flag=1
            if maximum%minute!=0:
                tmp.appendleft(maximum)

        if flag!=1:
            escape.append(minute)
        A=tmp

    print(len(escape))




if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

lst.sort()

visited = [0 for _ in range(n)]
ans = n
for i in range(n):
  if visited[i] == 0:
    for j in range(i+1,n):
      if lst[j] % lst[i] == 0 and visited[j] == 0:
        ans -= 1
        visited[j] = 1
        if lst[j] == lst[i] and visited[i] == 0:
          ans -= 1
          visited[i] = 1
             
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    A = set(A)

    ans = 0
    while(A):
        x = min(A)
        if d[x] == 1:
            ans += 1
        next = set()
        for y in A:
            if y % x != 0:
                next.add(y)
        A = set()
        A |= next

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def func(alist,num):
    rl=[]
    if alist.count(num)==1:rl.append(num)
    for di in alist:
        if di%num!=0:rl.append(di)
    return sorted(rl)

n=int(input())
a=sorted(map(int,input().split()))
i=0
while(True):
    a=(func(a,a[i]))
    i+=1
    if len(a)<=i:break
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alis = list(map(int, input().split()))
Alis.sort()
Alis = [a for a in Alis if Alis.count(a) == 1]

ans = 0
while Alis:
    ans += 1
    lis2 = []
    for j in range(1, len(Alis)):
        if Alis[j] % Alis[0]:
            lis2.append(Alis[j])
    Alis = lis2

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
  han =1
  for j in range(N):
    if A[i] % A[j] ==0:
      han -=1
      if han <0:
        break
  if han ==0:
    t +=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np
from numba import jit, void, i8


# 標準入力の取得
def get_input() -> tuple:
    N = int(input())
    A = list(map(int, input().split()))
    A = list(sorted(A))
    A = np.array(A)
    return N, A


@jit(nopython=True, cache=True)
def main(N: int, A: np.ndarray) -> None:
    # 求解処理
    result = 0
    for i in range(N):
        A_i = A[i]
        if np.sum(A == A_i) > 1:
            continue
        can_divide = False
        for j in range(i):
            A_j = A[j]
            if A_i % A_j == 0:
                can_divide = True
                break
        if not can_divide:
            result += 1

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, A = get_input()
    main(N, A)

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()
# from bisect import bisect_left
# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#         break
#     tmp.add(v)
# #     na = []
# #     ii = bisect_left(a, v*2)
# #     for 
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

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

tmp = set(tmp) - s
print(len(tmp))

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
#A = [i for i in range(2, N+2)]

def is_prime(n):
  if n == 1:
    return False
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      return False
  return True

D = []
E = []

for i, x in enumerate(A):
  Flag = True

  if i >= 1 and x == D[-1]:
    E.append(x)
    continue

  if i >= 5000 and D[0] != 1 and is_prime(x):
    D.append(x)
    continue
    
  for j in D:
    if x%j == 0:
      Flag = False
      if x == j:
        E.append(x)
      break
    
  if Flag:
    D.append(x)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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 <= 10 ** 6:
        d = [elm for elm in d if elm[0] % a]
    else:
        d = [elm for elm in d if elm[1] == 1]
        count += len(d)
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
"""
Created on Sun Jun 14 21:51:57 2020

@author: arisa
"""
#from sympy import isprime

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tmp = list(map(int, input().split()))
ans = 0
a = sorted(tmp)
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()
double = set(a)
for i in double:
    if not tmp.count(i) == 1:
        ans -= tmp.count(i)

# a.sort()


check = True
loop = list(range(len(a)))
for i in loop:
    for j in range(0, i):
        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(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 A:
        count_flag = True
        now_num = i
        half_num = i/2
        if now_num == last_num:
            if flag:
                count -= 1
                flag = False
        else:
            for j in A[:i]:
                if j > half_num:
                    break
                if now_num % j == 0:
                    count_flag = False
                    break
            if count_flag:
                if not flag:
                    flag = True
                count += 1
            last_num = i
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    div=set()
    i = 1
    ap=div.add
    while i*i <= n:
        if n % i == 0:
            ap(i)
            ap(n//i)
        i += 1
    return 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:
N=int(input())
a=map(int,input().split())
A=sorted(a)
answers=[]
if N==1:
    print(1)
else:
     for a in A:
         number=0
         if A.count(a)!=1:
             continue
         else:
             for b in answers:
                 if a%b==0:
                     number=1
                     break
             if number==0:
                 answers.append(a)
     print(len(answers))

Submission status: Time Limit Exceeded

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




print(len(set(p)))

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))
    if len(tmp & table_) <= 1:
        ans += 1
    # 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:
def check_prime(k):
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0
    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()
if a[0] == 1:
    if n == 1 or a[1] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


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


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = list(input().split())
A = sorted([int(A[i]) for i in range(N)])
A_count = Counter(A)
count = 0

for i in reversed(range(N)):
    tmp = A[i]
    if A_count[tmp] != 1:
        continue
    else:
        for j in range(N):
            if A[j] > (tmp // 2):
                count += 1
                break
            elif tmp % A[j] == 0:
                break

print(count)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
A = A[:N] # 一応

def calc(b, A):
    new = []
    count = 1
    for a in A:
        if a % b > 0: # bで割れなければ続投
            new.append(a)
        if b % a == 0: # bがaで割り切れてしまったら強い方に交代
            count = 0
    # count と 新しいAを返す
    return count, new

count = 0
while len(A) > 0:
    a = A.pop(0)
    
    c, A = calc(a,A)  
    count += c

print(count)

Submission status: Time Limit Exceeded

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

from numba import jit


@jit(nopython=True, parallel=True, cache=True, nogil=True)
def divisors(n):
    res = set()
    for i in range(1, n + 1):
        if i * i > n:
            return res
        d, m = divmod(n, i)
        if m == 0:
            res.add(i)
            res.add(d)
    return res


def count_nondivisors(n, bs):
    ctr = {b: 0 for b in bs}
    for b in bs:
        ctr[b] += 1
    ds = {k: sum(ctr.get(k, 0) for k in divisors(k)) for k in ctr.keys()}
    num_div_elems_table = [ds[bs[i]] for i in range(n)]
    res = sum(num_div_elems_table[i] == 1 for i in range(n))
    return res


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    res = count_nondivisors(n, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

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

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

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

    return arr

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
#rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    #rootA=math.sqrt(ListA[i])
    MaxVal=ListA[i]/factorization(ListA[i])[0][0]

    # if(ListA[i]%2==0):
    #     Maxval=ListA[i]/2
    # if(ListA[i]%3==0):
    #     Maxval=ListA[i]/3
    # if(ListA[i]%5==0):
    #     Maxval=ListA[i]/5
    # if(ListA[i]%7==0):
    #     Maxval=ListA[i]/7


    for j in range(i):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>MaxVal):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


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


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

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
 
N=int(input())
A=list(map(int,input().split()))
list.sort(A,reverse=True)

count=N
if 1 in A:
  if A.count(1)>1:
    print(0)
  else:
    print(1)
  exit()
 
for i in range(N):
  B=A.copy()
  B.pop(i)
  if A[i] in B:
    count-=1
    continue
  for j in range(i+1,N):
    if A[i]%A[j]==0:
      count-=1
      break
 
print(count)

Submission status: Time Limit Exceeded

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

for i in range(len(A)):
  for j in range(i+1,len(A)):
    if tmp_A[i] == tmp_A[j]:
      A[i] = 0
      A[j] = 0
      
    if tmp_A[j] != 0 and tmp_A[i] != 0:
      A[j] = 0 if tmp_A[j] % tmp_A[i] == 0 else tmp_A[j]
 
print(len([i for i in A if (i > 0)]))

Submission status: Time Limit Exceeded

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

for i in range(n):
    a[i] = int(a[i])
a.sort()
a.append(10**6 + 1 )
count = 0
for i in range(n):
    flag = 0
    for j in range(i):
        if a[i]%a[j] == 0:
            flag += 1 
            break
    if flag == 0:
        if i == n or a[i] != a[i+1]:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N = II()
    A = LI()

    cost = {}
    for a in A:
        if cost.get(a, -1) == -1:
            cost[a] = 1
        else:
            cost[a] = 0

    A = sorted(A)

    memo = [0] * (A[-1] + 1)
    ans = 0
    for a in A:
        for i in range(1, int(a ** 0.5) + 1):
            if a % i: continue
            if memo[i] or memo[a//i]:
                break
        else:
            ans += cost[a]

        memo[a] = 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

#Adic = {}

#for i in range(N):
#	Adic[A[i]] = i + 1

Asorted = sorted(A)
divlist = []
dup = [x for x in set(Asorted) if Asorted.count(x) > 1]
Asorterd = set(Asorted)

count = 0
for i in range(len(Asorted)):
	divflag = False
	#for j in range(i):
	for div in divlist:
		#if Asorted[i] % Asorted[i - j - 1] == 0:
		if Asorted[i] % div == 0:
			divflag = True
			break
	if divflag == False:
		divlist.append(Asorted[i])

print(len(set(divlist)-set(dup)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input(''))
alist = list(map(int,input('').split(' ')))
 
alist.sort(reverse=True)
results = [True for i in range(n)]
 
for i in range(len(alist)):
    if results[i]!=False:
        ai = alist[i]
        result = False
        for j in reversed(range(i,len(alist))):
            result = True
            aj = alist[j]
#            print("{}[{}] {}[{}] {}/{}".format(ai,i,aj,j,(ai==aj),(ai%aj==0)))
            if i!=j and (ai==aj):
                results[j] = False
            if i!=j and (ai%aj  == 0):
                result = False
                break
        results[i] = result
 
print(results.count(True))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
aaa=list(map(int,input().split()))
aaa.sort()
aa=deque(aaa)
count=0
while aa:
    a=aa.popleft()
    if len(aa)!=0:
        b=aa.popleft()
    else:
      b=float("inf")
    if a!=b:
        count+=1
    if b!=float("inf"):
      aa.appendleft(b)
    k=len(aa)
    for t in list(aa):
        if t%a==0:
          aa.remove(t)
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)

ans = []
double = []

s = 0
while len(a) > 0:
    ans.append(a.popleft())
    if len(a) > 0 and ans[s] == a[0]:
        double.append(ans[s])
    a = deque([i for i in a if i % ans[s] != 0])
    s += 1

for k in double:
    if k in ans:
        ans.remove(k)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    uni = sorted(list(set(a)))
    dup = [x for x in set(a) if a.count(x) > 1]

    ans = 0
    for i in range(len(uni)):
        if uni[i] in dup:
            continue

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_lst = list(map(int, input().split()))
store_a_lst = a_lst.copy()
cnt = 0
for i in range(0, n):
    a_lst = store_a_lst.copy()
    # new_a_lst = []
    # listの自身の数
    # print(a_lst)
    # print(i)
    mynumber = a_lst[i]
    # listから自身 を取り除いたlistをnew_a_lstとする
    # new_a_lst = list(a_lst.pop(i))
    # a_lst.pop(i)
    del a_lst[i]
    
    # newcheck = [mynumber % n for n in new_a_lst]
    newcheck = [mynumber % n for n in a_lst]

    if 0 not in newcheck:
        cnt += 1 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np
from numba import jit, void, i8


# 標準入力の取得
def get_input() -> tuple:
    N = int(input())
    A = list(map(int, input().split()))
    A = list(sorted(A))
    A = np.array(A)
    return N, A


@jit(nopython=True)
def main(N: int, A: np.ndarray) -> None:
    # 求解処理
    result = 0
    for i in range(N):
        A_i = A[i]
        if np.sum(A == A_i) > 1:
            continue
        can_divide = False
        for j in range(i):
            A_j = A[j]
            if A_i % A_j == 0:
                can_divide = True
                break
        if not can_divide:
            result += 1

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, A = get_input()
    main(N, A)

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()
# from bisect import bisect_left
# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#         break
#     tmp.add(v)
# #     na = []
# #     ii = bisect_left(a, v*2)
# #     for 
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

tmp = [a[0]]
ss = 0
for i in range(1, n):
    num = a[i]
    for j in range(min(len(tmp), ss+10)):
        item = tmp[j]
        if num%item==0:
            break
        if item*2>num:
            ss = j
#             print(item, num, ss)
            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())
A=sorted(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:
            break
        #if i >= i2:
            #break
        if a % a2 == 0:
            
            flg = 1
            break
    if flg == 0:
        
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
#A = [i for i in range(2, N+2)]

def is_prime(n):
  if n == 1:
    return False
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      return False
  return True

D = []
E = []

for i, x in enumerate(A):
  Flag = True

  if i >= 1 and x == D[-1]:
    E.append(x)
    continue

  if i >= 1000 and D[0] != 1 and is_prime(x):
    D.append(x)
    continue
    
  for j in D:
    if x%j == 0:
      Flag = False
      if x == j:
        E.append(x)
      break
    
  if Flag:
    D.append(x)

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

Submission status: Time Limit Exceeded

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

for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1
        
if 1 in d:
    if d[1]==1:
        ans=1
    else:
        ans=0

else:
    ans=0
    m=min(A)
    for i in d:
        if d[i]>1 or (i!=m and i%m==0):
            continue
        p=1
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                if j in d or i//j in d:
                    p=0
                    break
        ans+=p

print(ans)

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