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:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

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

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

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

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 = sorted(list(map(int, input().split())))
cnt = 0
cnt1 = 0
for i in a:
    if i == 1:
        cnt1 += 1
        if cnt1 == 2:
            print(0)
            sys.exit()
# if cnt1 > 1:
    # print(0)
    # sys.exit()
if cnt1 == 1:
    print(1)
    sys.exit()
if n == 1:
    print(1)
    sys.exit()
for i in range(n):
    # d = make_divisors(a[i])
    # print(d)
    if i == 0 and a[i] == a[i + 1]:
        continue
    if i == n - 1 and a[i - 1] == a[i]:
        continue
    if i not in [0, n - 1] and (a[i - 1] == a[i] or a[i] == a[i + 1]):
        continue
    d = make_divisors(a[i])
    if len(d) == 2:
        cnt += 1
        continue
    d = d[:-1]
    for j in d:
        if a[bisect_left(a, j)] == j:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
B = []
for i in range(N):
  if A.count(A[i]) != 1:
    continue
  else:
    p = 0
    for j in B:
      if A[i] % j == 0:
        p = 1
    if p == 0:
      B.append(A[i])
      
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_ls=list(map(int, input().split()))
M=max(a_ls)

#a_derep=sorted(list(set(a_ls)))
a_set=set(a_ls)
ans=0

while len(a_set)>0:
	i=min(a_set)
	a_set=a_set-set(range(i,M,i))
	ans+=1
	print(a_set)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
A1 = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
N = A1[0]
new_list=[]
for i in range(N):
  for j in range(N):
    if i!=j and p[i] % p[j]==0:
      new_list.append(p[i])
      break
check = set(p) ^ set(new_list)
print(int(len(check)))

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]
for a in Alis:
    if Alis.count(a) > 1:
        Alis.remove(a)
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())
ns = list(map(int, input().split()))
ans = 0
from collections import Counter
c = Counter(ns)
dubbles = set([key for key, value in c.items() if value >= 2])
ns = sorted([i for i in ns if i not in dubbles])
n = len(ns)

def make_divisors(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

for i in range(n):
    if make_divisors(ns[i]) & dubbles:
        dubbles.add(ns[i])
        continue
    ans += 1
    dubbles.add(ns[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
z= 0
if A.count(1)==1:
    print(1)
elif A.count(1) >= 2:
    print(0)
else:
    for i in A:
        A = [x for x in A if (x == i or x % i !=0)]
    for j in A:
        if A.count(j)>1:
            z += 1
    print(len(A)-z)

Submission status: Time Limit Exceeded

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

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
for i in range(n):
    B[A[i]] += 1

for i in range(n):
    ok = 1
    if (A[i] != 1 and B[1] > 0) or B[A[i]] > 1:
        ok = 0
    if ok == 1:
        for j in range(2, int(A[i]**0.5)+1):
            if A[i] % j == 0 and (B[j] > 0 or B[A[i]//j] > 0):
                ok = 0
                break
    ans += ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
if N == 1:
  print(1)
  exit()
  
A=[int(_) for _ in input().split(" ")]

A.sort(reverse=True)
#print(A)

ans=[]

flg=0 
for i in range(N):
  flg=0
  if i == 0:
    if A[i]==A[i+1]:
      flg=1
  elif i==N-1:
    if A[i]==A[i-1]:
      flg=1
  else:
    if A[i]==A[i+1] or A[i]==A[i-1]:
      flg=1

  if flg == 0:
    for j in range(0,N-1-i):
      #print(i,j,A[i],A[N-1-j])
      if A[i] % A[N-1-j] == 0:
        flg=1
        break
      if A[i]/2 < A[N-1-j]:
        break
      
  if flg == 0:
    ans.append(i)
  else:
    flg = 0

#print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
b = [False] * (max_a + 1)
a.sort()
a = a + [0]
b[a[0]] = True
count = 0
for i in range(1, n):
    flg = True
    if b[a[i]]:
        continue
    for j in range(i - 1, -1, -1):
        if a[i] % a[j] == 0 or a[i] == a[i+1]:
            flg = False
            b[a[i]] = True
            k = 2
            while k*a[i] < max_a:
                b[k*a[i]] = True
                k += 1
            break
    if flg:
        count += 1

if a[0] != a[1]:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
iter = 0
"""
for i in a:
  lst = [i%j for j in a]
  if lst.count(0) == 1:
    iter = iter + 1
"""

#a.sort()
for i in a:
  lst = filter(lambda x: x<=i, a)
  lst = [i%j for j in lst]
  #print(lst)
  if lst.count(0) == 1:
    iter = iter + 1
print(iter)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())

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

a.sort()

if a[0] != 1:
    i = 0

    while i < len(a):
        a = [x for x in a if (not float.is_integer(x / a[i])) or ((x / a[i]) == 1)]

        i += 1

    num_dict = dict(collections.Counter(a))

    counts = num_dict.values()

    temp = dict(collections.Counter(counts))

    print(temp.get(1, 0))

elif (len(a) > 1) and (a[0] == a[1]):
    print(0)
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
line = input()
line = line.rstrip().split(' ')
n = int(line[0])

line = input()
line = line.rstrip().split(' ')
a = []
for i in line:
    a.append(int(i))

a.sort()

answer = 0

for i in range(len(a)):
    dividable = False
    for j in range(i + 2):
        if j >= len(a):
            pass
        elif i == j:
            pass
        elif a[i] % a[j] == 0:
            dividable = True
            break

    if dividable == False:
        answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections

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

C = collections.Counter(A)
C_keys = np.array(list(C.keys()))
C_values = tuple(C.values())

divisible = 0
for i, c in enumerate(C_keys):
    if 0 in set(c % C_keys[i + 1:]):
        divisible += C_values[i]
    else:
        if C_values[i] > 1:
            divisible += C_values[i]
        
print(N - divisible)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a_origin = sorted(inpl())
ans = 0
count = collections.defaultdict(int)
a = []
for i in range(n):
    count[a_origin[i]] += 1
    if count[a_origin[i]] < 3:
        a.append(a_origin[i])
n = len(a)


class Cell:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


prev = Cell(a[0])
now = prev
for i in range(1, n):
    new = Cell(a[i])
    prev.next = new
    new.prev = prev
    prev = prev.next
while now:
    if not now.next:
        ans += 1
        break
    target = now.next
    while target:
        if target.value == now.value:
            ans -= 1
            if target.next:
                target.next.prev = target.prev
                target.prev.next = target.next
            else:
                target.prev.next = None
        elif target.value % now.value == 0:
            if target.next:
                target.next.prev = target.prev
                target.prev.next = target.next
            else:
                target.prev.next = None
        target = target.next
    ans += 1
    now = now.next
print(ans)

Submission status: Time Limit Exceeded

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

if a[0]==1:
    if n>=2 and a[1]==1:
        print(0)
    else:
        print(1)
else:
    ans = 0
    for num in a:
        if a.count(num) >= 2:
            continue
        else:
            cands = [i for i in a if i<=num*(1/2)]
            for i in range(2, int(num**0.5)+1):
                if num % i == 0 and (i in cands or num//i in cands):
                    break
            else:
                ans+=1
            
    print(ans)

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:
            if 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:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()

    ans = 0
    temp = 0
    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    for i in range(N):
        if i == 0 and A[i+1] != A[i]:
            ans += 1
            continue

        temp = A[i]
#同じ数があるかどうか
        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue

        for j in range(N):
            if A[j] == -1:
                continue
            elif A[j] <= temp/2 and A[i]%A[j] == 0:
                A[i] = -1
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
a = input()
c = input()
l = c.split()
cc = [int(s) for s in l]
ccc =list(cc)
d = 0
for i in ccc:
    b =0
    for j in ccc:
        if i%j==0:
            b +=1
    if b == 1:
        d += 1
print(d)

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:
        if 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:
import collections

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

while len(A):
    cnt = 1
    target = A.pop(0)
    if counter[target] == 1:
        ans_list.append(target)
    tmp = target
    cnt = 1
    while len(A) != 0 and tmp * cnt <= A[-1]:
        if tmp*cnt in A:
            del A[A.index(tmp*cnt)]
        cnt += 1

print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def get_primes(n=10**3):
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def prime_factor(n):
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort()
    lst = []
    ans = []
    while aa:
        x = aa[0]
        lst = []
        flag=False
        for a in aa[1:]:
            if a%x!=0:
                lst.append(a)
            else:
                if a==x:
                    flag=True
        if not flag:
            ans.append(x)
        aa = lst
        # print(ans)
    print(len(ans))


if __name__ == '__main__':
    main()

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))
    B = deque([])
    ans = []
    S = True
    while True:
        if len(A) == 0:
            break
        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:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in a:
        cnt = 0
        for j in range(n):
            if i % a[j] == 0:
                cnt += 1
        if cnt == 1:
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)
    l = [False] * (10 ** 6 + 5)

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys():
        l[n] = True
        if A[n] == 1:
            lim = int(n ** 0.5) + 3
            for i in range(1, lim):
                if i * i > n: break
                if n%i != 0: continue
                e[n].append(i)
                if i != n//i: e[n].append(n//i)

    for n in A.keys():
        if A[n] >= 2: continue
        if len(e[n]) == 2:
            ans += 1
            continue
        for p in e[n]:
            if p in {1, n}: continue
            if l[p]: break
        else: 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()))
l=[0 for _ in range(n)]
mem=[0 for _ in range(n)]
a.sort()

for i in range(n):
    if mem[i]==1:
        continue
    for j in range(n):
        if a.count(a[i])>=2:
            l[i]=1
            break
        if ((a[i]//2)<a[j]):
            break

        if a[j]%a[i]==0:
            mem[j]=1
        if a[i]%a[j]==0:
            l[i]=1
            break

cnt=l.count(0)
print(cnt)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  tf=[1]*n
  n=n-1
#r=[]
#print(n)
#print(a)
  #notdiv=True
  #firstyn=0
  for i in range(n,-1,-1):
  #print(i)
  #notdiv=True
    if tf[i] ==0:
      continue
    for j in range(i):
    #print(a[j])
      if a[i]%a[j] == 0:
        tf[i]=0
        if a[i]==a[j]:
          for k in range(j,i):
            tf[k]=0
        break
  print(sum(tf))
main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

A.sort()
C = defaultdict(int)
ans = 0

for a in A:
    C[a] += 1

D = set()

B = []


for a in A:
    if C[a] == 1:
        for b in B:
            if a % b == 0:
                break
        else:
            ans += 1
            B.append(a)
    else:
        if a not in D:
            B.append(a)
            D.add(a)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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


A2 = list(set(A))
A2.sort()
basis = []

for a in A2:
    for b in basis:
        if a % b == 0:
            break
    else:
        basis.append(a)

ans = 0
c = Counter(A)
for b in basis:
    if c[b] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
# Nの入力
N = int(input())
A = list(map(int,input().split()))

C = [x for x in set(A) if A.count(x) > 1]

A.sort()
B = copy.deepcopy(A)
for i in range(len(A)):
    for j in range(10 ** 3):
        if j in B and A[i] in B:
            if A[i] != j and A[i] % j == 0:
                B.remove(A[i])
D = copy.deepcopy(B)
for i in range(len(B)):
    if B[i] in C: 
        D.remove(B[i])
print(len(D))

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)
d={}
ans=0
for i in range(n):
	if l[i] in d:
		d[l[i]]+=1
	else:
		d[l[i]]=1
if 1 in d:
	if d[1]>1:
		print(0)
	else:
		print(1)
	exit()

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 c==0:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def resolve():
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    N = int(input())
    A = list(map(int,input().split()))
    ans = np.ones(N,dtype=int)
    for i in range(N):
        for j in range(N):
            if A[i] % A[j] == 0 and i != j:
                ans[i] = 0
                break
    print(sum(ans))
resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
list_num = [int(_) for _ in input().split()]
list_num.sort(reverse=True)
# print(list_num)j

counter2 = 0
for i in list(set(list_num)):
    if list_num.count(i) > 1:
        counter2 +=1

counter = 0
if 1 in list_num:
    if list_num.count(1) == 1:
        print(1)
    else:
        print(0)
else:
    for i, num in enumerate(list_num):
        for num2 in list_num[i + 1:]:
            # print(num, num2)
            if num % num2 == 0:
                # print("-> NG")
                counter += 1
                break

    print(N - counter - counter2)

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    
    from collections import defaultdict
    d = defaultdict(int)
    
    for k in A:
        d[k] += 1
    
    ans = 0
    
    while(len(d)!=0):
      
        tmp = next(iter(d))
        if d[tmp] == 1:
            ans += 1
            
        a = iter(d)
        x = []
        for j in range(len(d)):
            tmp2 = next(a)
            if tmp2 % tmp == 0:
                x.append(tmp2)
                
        for tt in x:
            del d[tt]
                
    print(ans)


if __name__ == "__main__":
    main()

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)'''
def yakusuu(n):
    #約数リスト生成,バラバラに出るので.sort()を使う必要あるかも
    #PyPy推奨
    yakusuu_list = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yakusuu_list.append(i)
            if i != n // i:
                yakusuu_list.append(n//i)
    return yakusuu_list

n=int(input())
a=list(map(int, input().split()))
#print(sorted(a))
a.sort()
wa=[a[0]]
waaa=[False]*(10**6)
bl=[]

def ok(wa,waaa,item,bl):
    m=yakusuu(item)
    #print(m)
    if waaa[item-1]==True:
        bl.append(item-1)
        return

    waaa[item-1]=True

    for jtem in m:
        if jtem!=item and waaa[jtem-1]==True:
            bl.append(item-1)
            return

    waaa[item-1]=True
    #print(item,waaa[:25])
    return

for item in a:
    ok(wa,waaa,item,bl)

#import collections
print(waaa.count(True)-len(set(bl)))
#print(max(0,len(wa)-len(set(bl))))

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
  #print(han)
  if han ==0:
    t +=1
print(t)

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)
if len(set(a))==1 and len(a) != 1:
    print(0)
    sys.exit()

wa = 0
for i in range(len(a)):
    flg = 0
    for j in range(len(a)):
        if i != j and a[i]%a[j] == 0:
            flg = 1
            break
    if flg == 0:
          wa += 1
    
print(wa)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

count=0
isDividable=0

for i in range(n):
  isDividable=0
  for j in range(n):
    if i != j and a[i] >= a[j] and (a[i] == a[j] or a[i] % a[j] == 0):
      isDividable=1
      break
  if isDividable==0:
    count=count+1
print(count)

Submission status: Time Limit Exceeded

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

A.sort()
flag=[0]*N
ans=0
for i in range(N):
    if i!=N-1:
        if A[i]==A[i+1]:
            flag[i]=1
    
    for j in range(i+1,N):
        if flag[j]==1:
            continue
        else:
            if A[j]%A[i]==0:
                flag[j]=1
print(flag.count(0))

Submission status: Time Limit Exceeded

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

def main():
  from collections import Counter
  n = int(input())
  A = tuple(map(int, input().split()))
  C = Counter(A)
  def f(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

  ans = 0
  for a in A:
      for j in f(a):
          if j == a:
              if C[j] > 1:
                  break
          else:
              if C[j] > 0:
                  break
      else:
          ans += 1
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  if(a.count(a[i]) >= 2):
    continue
  if(2 in a and a[i] % 2 == 0):
    continue
  flg = False
  for j in range(i):
    if(a[i] % a[j] == 0):
      flg = True
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict

input()
A = np.fromstring(input(), int, sep=' ')


counter = defaultdict(int)
for x in A:
    counter[x] += 1

A = np.array(list(set(A)))
A.sort()

count = 0
f = np.ones_like(A, dtype=bool)
for i, x in enumerate(A):
    if not f[i]:
        continue
    # print(i, x, count, A, f)

    if counter[x] == 1:
        count += 1

    f[i+1:] &= (A[i+1:] % x != 0)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A.sort()
collect = collections.Counter(A)
count = 0

prime = [A[0]]
while len(A) > 1:
    A = [j for j in A if j % A[0] != 0]
    if len(A) >= 1:
        prime.append(A[0])

for p in prime:
    if collect[p] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import functools

def f(l, d):
    le = len(l)
    if le == 0:
        return []
    elif le == 1:
        if l[0] % d == 0:
            return []
        return l

    m = functools.reduce(lambda x, y: x*y, l)
    if m % d != 0:
        return l

    h = le//2
    return f(l[:h], d) + f(l[h:], d)


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

a.sort(key=lambda x: -x)
i = 0
p = []
while len(a) != 0:
    i = a.pop()
    if i in a:
        a.pop()
        while i in a:
            a.pop()
        continue
    p.append(i)

    a = f(a, i)

print(len(p))

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())
    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:
from bisect import bisect_left
from collections import Counter
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()))
a=sorted(a)
c=Counter(a)
x=set()
for i in range(n):
    x.add(a[i])
ans = 0
for i in range(n):
    if c[a[i]]>1:
        continue
    l=make_divisors(a[i])
    
    x.remove(a[i])
    #X=list(x)
    f=1
    for r in x:
        w=bisect_left(l,r)
        if w != len(l) and l[w]==r:#rがlの中にあるか
            f=0
            break
    if f:
        ans += 1
    x.add(a[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

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