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:
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    Boo = [True]*len(B)

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

    for i in range(len(B)):
        for j in range(i+1,len(B)):
            if Boo[j] and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(len(B)):
        if Boo[i] and A.count(B[i])==1:
            cnt += 1

    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n = int(input())
As = list(map(int, input().split()))
table = [0] * (10 ** 6 + 1)
ans = n
for a in As:
    tmp = a
    table[tmp] += 1
    for _ in range((10 ** 6) // a - 1):
        tmp += a
        table[tmp] += 1
for a in As:
    ans -= (table[a] > 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def divisor(n):
    divisors = []
    if n%2 == 0:
        f = 2
        divisors.append(1)
    else:
        f = 1

    for i in range(f, n//2+1):
        if n % i == 0:
            divisors.append(i)
    divisors.append(n)
    return divisors

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

for i,num in enumerate(A):
    for div in divisor(num):
        FLG = True
        if div in A[:i] + A[i+1:]:
            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(" ")))

b=[i for i in a]
b.sort()
r=[]
for i in range(len(a)):
    f=0
    for j in range(len(a)):
        if a[i]%a[j]==0 and i!=j:
            f=1
    if f==0:
        r.append(i+1)
print(len(r))

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
def divisors(n):
    divisors = set()
    for i in range(1, int(sqrt(n))+1):
        q, r = divmod(n, i)
        if r == 0:
            divisors.add(i)
            divisors.add(q)
    return divisors

n, *A = map(int, open(0).read().split())
X = [0] * (10**6 + 1)
c = 0
for a in A:
    X[a] += 1
for a in A:
    B = divisors(a)
    X[a] -= 1
    c += all(X[b] == 0 for b in B)
    X[a] += 1
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
C = Counter(A)

if 1 in C:
    if C[1] == 1:
        print(1)
    else:
        print(0)
    exit()

B = []
for k, v in C.items():
    if v > 1:
        continue
    B.append(k)

ans = 0
for i, a in enumerate(B):
    for i in range(2, int(a**0.5)+1):
        if a % i == 0:
            if i in C:
                break
            if a // i in C:
                break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

A_list.sort()
div_list = [A_list[0]]
div_len = 1
ans_num = 1
reduce_flag = 1
for i in range(1, N):
    now_A = A_list[i]
    for j in range(div_len):
        if now_A % div_list[j] == 0:
            if now_A == div_list[j]:
                ans_num -= reduce_flag     
            reduce_flag = 0
            break
    else:
        div_list.append(now_A)
        div_len += 1
        ans_num += 1
        reduce_flag = 1

print(ans_num)

Submission status: Time Limit Exceeded

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

N=int(input())
A=list(map(int,input().split()))
A.sort()
count=0
while len(A)>0:
    x=A[0]
    if x in set(A[1:]):
        count-=1
    A=[i for i in A[1:] if i%x != 0]
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

count = 0
for i, Ai in enumerate(A):
  flag = 0
  for j, Aj in enumerate(A):
    if i == j:
      continue
    if (Ai % Aj) == 0:
      flag = 1
      break
  if flag == 0:
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(len(a)):
  b=[]
  for j in range(len(a)):
    b.append(a[i] % a[j])
    
  if b.count(0)==1:
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A = int(input())
P = np.array(list(map(int, input().split())))
ans = 0
for i in range(0,A):
    D = np.delete(P,i)
    if ((P[i]/D) == np.ceil(P[i]/D)).any():
        continue
    ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
Q=[]
a.sort()
t=0
for i in range(n):
    f=True
    if Q:
        for q in Q:
            if a[i]%q==0:
                f=False
                break
    if f and i<n-1 and a[i]==a[i+1]:
        f=False
        Q.append(a[i])
    if f:
        Q.append(a[i])
        t+=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    a_set = set(a)

    a_cnt = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        if a_cnt[n] > 1:
            return True

        # divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i in a_set and i != n:
                    return True
                if i != n // i:
                    if n // i in a_set and n//i != n:
                        return True

        return False

    ans = 0
    for ai in a_set:
        if not make_divisors(ai):
            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()
import numpy as np
def update(dt):
    t = dt[0]
    is_f = False
    if t in dt[1:]:
        is_f = True
    dtu = filter(lambda x: x % t != 0, dt[1:])
    if is_f:
        return list(dtu), False
    else:
        return list(dtu), t

res = []
resid = 0
while True:
    if len(A) <= 1:
        resid = len(A)
        break
    A, t = update(A)
    if t:
        res.append(t)

print(len(res) + resid)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
tmp=list(map(int,input().split()))
tmp.append(10**9+7)
ans=0
while len(tmp)>1:
    A=tmp.copy()
    
    A.sort(reverse=True)
    MAX=max(A)
    tmp=[]
    a=A.pop()
    
    if A[-1]!=a:
        ans+=1
    for m in A:
        if m%a==0:
            continue
        else:
            tmp.append(m)
print(ans)

Submission status: Time Limit Exceeded

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

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

print(num_ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)

ans = 0

for i,a in enumerate(B):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            continue
        elif d in keys:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(n):
    divisible = False
    for j in range(n):
        if i != j:
            if A[i] % A[j] == 0:
                divisible = True
                break
    if not divisible:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


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 solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    a_set = set()
    memo = set()
    for ai in A:
        if ai in a_set:
            memo.add(ai)
            if ai == 1:
                print(0)
                return
        else:
            a_set.add(ai)
    if 1 in a_set:
        print(1)
        return
    
    se = set()
    A.sort()
    ans = 0
    for ai in A:
        flg = True
        divs = make_divisors(ai)
        for div in divs:
            if div in se:
                flg = False
                break
        if ai in memo:
            flg = False
        se.add(ai)
        ans += flg
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
dic=Counter(a)
def make_divisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
		if n % i == 0 and n!=i:
			divisors.append(i)
			if i != n // i and n!=n//i:
				divisors.append(n//i)
	return divisors
ans=0
for i in a:
	yakusu=make_divisors(i)
	for j in yakusu:
		if j in dic:
			break
	else:
		if dic[i]==1:
			ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import Counter
    import sys
    input = sys.stdin.readline
    _ = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    ans = 0
    for i in (x for x, y in c.items() if y == 1):
        for j in range(1, int(i ** 0.5) + 1):
            if i % j == 0:
                if j in c and j != i:
                    break
                if j != i // j:
                    if i // j in c and i // j != i:
                        break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = list(map(int, input().split()))
A.sort()
done = []
ans_set = set()
done.append(A[0])
ans_set.add(A[0])

before = A[0]
for a in A[1:]:
    if before == a:
        if a in ans_set:
            ans_set.remove(a)
        continue
    flag = True
    for b in done:
        if a % b == 0:
            flag = False
            break
        if a < b*2:
            break
    if flag:
        done.append(a)
        ans_set.add(a)
    before = a

print(len(ans_set))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
a = list(filter(lambda x: a.count(x) == 1, a))
# print(a)

for i in range(len(a)):
    if a[i] == 0:
        continue
    for j in range(i + 1, len(a)):
        if a[j] % a[i] == 0:
            a[j] = 0
print(len(list(filter(lambda x : x != 0, a))))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(v, pp):
	if v == pp[-1]:
		return False, -1
	#print(pp)		
	for p in pp:
		if v % p == 0:
			return False, 0
		if v < 2*p:
			return True, 0
	return True, 0
			

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp)
		if tf:
			pp.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len(A)):
  flg = 0
  for j in range(len(A)):
    if (i != j):
      if (A[i] % A[j] == 0):
        flg = 1
        break
  if (flg == 0):
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

from functools import lru_cache
@lru_cache(maxsize=None)
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table

@lru_cache(maxsize=None)
def mySolve(n):
    flag = True
    da = divisor(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    return flag

ans = 0
for a in A:
    if mySolve(a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2020/06/14
# AtCoder Beginner Contest 170 - D

# Input
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.append(10**7)

# Calc
ans = n

if a[0] == a[1]:
    ans = ans - 1

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

        if a[i] == a[i+1]:
            ans = ans - 1
            break

# Output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A_i/A_j False
num = int(input())
A = [int(x) for x in input().split()]
i = 0
result = 0
for i in range(num):
    devide = 0
    for j in range(num):
        if j == i:
            continue
        else:
            ans = A[i]/A[j]
            if (ans.is_integer()):
                devide += 1
                break
    if (devide==0):
        result+=1
print(result)

Submission status: Time Limit Exceeded

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

for i in range(a):
    for j in range(a):
        if(j == i): continue
        if(A[i]%A[j] == 0):
            d_num -= 1
            break
print(d_num)

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)

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 A[i] % A[j] == 0:
                flag = False
                break
        if flag:
            result += 1
    return result

print(get_result())

Submission status: Time Limit Exceeded

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

while len(a) >= 1:
  ans += 1
  temp=a.pop(0)
  if len(a) >= 1:
    if a[0] == temp:
      ans -= 1
    a = list(filter(lambda x: x % temp != 0, a))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

def main():

    input = sys.stdin.readline

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

    ans = 0
    sort_A = sorted(set(A))

    c = collections.Counter(A)

    keisan_set = set()

    for a in sort_A:
        for k in keisan_set:
            if (a % k == 0):
                break
        else:
            if c[a] == 1:
                ans += 1

            keisan_set.add(a)

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right


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()))
    A.sort()
    ans = 0
    B = set(A)
    for a in B:
        flag = False
        left = bisect_left(A, a)
        right = bisect_right(A, a)

        if right-left > 1:
            continue

        divs = make_divisors(a)
        for d in divs:
            left = bisect_left(A, d)
            right = bisect_right(A, d)
            if left != right and d != a:
                flag = True
                break

        if flag == False:
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
ans=0
for i in range(N):
    if c[A[i]]>1:
        continue
    for j in range(N):
        if A[i]/2<A[j]:
            ans+=1
            break
        if A[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

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
    for i in range(N):
        a=A[i]
        p=1
        if d[a]>1:
            continue
        for j in range(2,int(a**0.5)+1):
            if a%j==0:
                if j in d or a//j in d:
                    p=0
                    break
        ans+=p

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):
    flag = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            flag = False
            break

    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
NotD = 0
for T in range(0,N):
    Target = A[T]
    Count  = 0
    for TT in range(0,N):
        BY = A[TT]
        if Target%BY!=0:
            Count += 1
    if Count==N-1:
        NotD += 1
print(NotD)

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    a= list(map(int, input().split()))
    a.sort()
    flag = [1]*(10**6+1)
    for i in range(n):
        if (flag[a[i]]==1):
            for j in range(2*a[i],10**6+1,a[i]):            
                flag[j] = 0
    x = collections.Counter(a)
    ans = 0
    for i in a:
        if (flag[i]==1):
            ans += 1
            flag[i]=0
            if (x[i]>1):
                ans -=1
    print(ans)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

X = [0]*(10**6+10)
Y = [0]*(10**6+10)
for i in list(set(A)):
    for j in range(i,max(A)+1,i):
        X[j] += 1

ans = 0
for i in A:
    Y[i] += 1
for i in A:
    if X[i] == 1 and Y[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#f = open('./input_D.txt')
#
#N = int(f.readline())
#A = list(map(int, f.readline().split()))

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

A_array = np.array(A)
A_array = np.sort(A_array)
A_list = A_array.tolist()

cnt = 0

while len(A_list)>1:
    num = A_list.pop(0)
    if num != A_list[0]:
        cnt+=1
    A_array = np.array(A_list)
    len_mae = len(A_array)
    A_amari = A_array%num
    A_array = A_array[A_amari!=0]
    A_list = A_array.tolist()

if len(A_list) == 1:
    cnt+=1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N):
    B=A.copy()
    t=B[i]
    B.pop(i)
    arr=[]
    if all(list(map(lambda x: t%x!=0, B))):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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


A.sort()

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

    for j in range(i):
        if A[i] % A[i - 1 - j] == 0:
            count += 1
            break


print(N - count)

Submission status: Time Limit Exceeded

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

A = sorted(A, reverse= True)

counter = N

for i in range (0, N):
	for j in range (A.index(A[i])+1, N):
		if A[i]%A[j]==0:
			counter-=1
			break

print(counter)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
sm=0
for i in range(n):
    var=l[i]
    for j in range(n):
        if i==j:continue
        if var%l[j]==0:
            break
    else: sm+=1
print(sm)

Submission status: Time Limit Exceeded

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

A =sorted(A)

C = Counter(A)
ans=0
while A:
    d = A[0]
    if C[d]==1:
        ans+=1
    A = [a for a in A if a%d!=0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        j = 0
        while j < i or a[j] <= 0.5 * a[i]:
            if a[i] % a[j] == 0:
                break
            j += 1
        else:
            if not (n > 1 and i < n - 1 and a[i] == a[i + 1]):
                ans += 1
    print(ans)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
A = np.array(A)
res_list = np.zeros(N)
for j in range(N):
    A_copy = A.copy()
    A_copy = A_copy % A[j]
    A_copy[j] += 1
    A_copy = np.where(A_copy > 0, 1, 0)
    res_list += A_copy
res_list /= len(A)
print(np.count_nonzero(res_list == 1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import sqrt
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)
    A = set(A)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)

    ans = 0
    for a in A:
        if a in bl:
            continue
        ok = True
        for i in range(2, int(a**0.5)+1):
            if a % i == 0:
                if i in A:
                    ok = False
                if a//i in A:
                    ok = False
            if not ok:
                break
        if ok:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def prime_factorize(n):
    '''prime_factorize(12) → [2,2,3]
    '''
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())
A = list(map(int, input().split()))
from collections import Counter
c = Counter(A)
sorted_key = sorted(c.keys(),reverse=True)
res = [0]*len(sorted_key)
#print(sorted_key)
for i,key in enumerate(sorted_key):
    for j in range(i+1,len(sorted_key)):
        #print(i,key,j,sorted_key[j])
        if (key/sorted_key[j]>=1) and (key%sorted_key[j])==0:
            res[i] = 1
            #print('===========',)
            break

#print('res', res)
#print(c)
ans = 0
for i,v in enumerate(sorted_key):
    if res[i]:
        ans += c[v]
    else:
        if c[v] >1:
            ans += c[v]
print(n-ans)

Submission status: Time Limit Exceeded

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

max_A = max(A)
table = [False]*(max_A+1)
for i in A:
    if table[i] == False:
        table[i] = True
    else:
        table[i] = -1

mem = []        
for i in A:
    if table[i] == -1:
        table[i] = True
        mem.append(i)

for i in range(1, max_A+1):
    if table[i] == True:
        n = 2
        while i*n < max_A+1:
            table[i*n] = False
            n += 1

for i in range(max_A+1): 
    if i in mem and table[i] == True:
        table[i] = False
        
print(table.count(True))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

from itertools import count
def test():
    n = int(input())
    a = [int(i) for i in input().split()]
    r = [True for i in range(1, n+1) if all([a[i-1] % a[j-1] != 0 for j in range(1, n+1) if i != j])]
    print(len([i for i in r if i]))

test()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    A.sort()
    nums = list()
    for a in A:
        is_target = True
        for n in nums:
            if a % n == 0:
                is_target = False
                break
        if is_target:
            nums.append(a)
    print(len(list(filter(lambda n: counter[n] == 1, nums))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
A = [int(v) for v in input().strip().split(" ")]

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

print(counter)

Submission status: Time Limit Exceeded

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

# process
A.sort()

B = [False]*N
for i in range(N):
    for j in range(i+1, N):
        if B[j]:
            continue
        
        elif A[j]%A[i] == 0:
            B[j] = True
            if A[i] == A[j]:
                B[i] = True

# output
print(B.count(False))

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 = sorted(inpl())
check = [False] * n
ans = 0
for i in range(n):
    if check[i]:
        continue
    FLAG = True
    for j in range(i + 1, n):
        if check[j]:
            continue
        if FLAG and a[j] == a[i]:
            FLAG = False
            ans -= 1
        if a[j] % a[i] == 0:
            check[j] = True
    ans += 1
print(ans)